Question

Let B=$\left\{a^i{b}^j{c}^k\overline{)i,j,k\ge 0andi=jori=k}\right\}$. Prove that B is not a DCFL.

Short answer

It can be proved that B is not a deterministic Context-free Language.

Step-by-step solution

Explain DCFL.

Deterministic Context Free Languages are accepted by the deterministic pushdown automaton. DCFL is an unambiguous and accept an unambiguous grammar. Deterministic Pushdown Automata is used to recognizes the DCFL.

Prove that B is not a DCFL.

Consider that the language B is a context free and if it is deterministic context free then$\overline{B}=\left\{a,b,c\right\}*-B$ is deterministic context free.

Thus, $B=\left\{a^i{b}^j{c}^k\overline{)i,j,k\ge 0andi=jori=k}\right\}$is not context free.

Consider $\overline{B}\cap \left\{a,b,c\right\}*-B_i$,If $\overline{B}$is a DCFL, then it must be a CFL. If$\overline{B}$ is CFL, then by intersection the regular language is a CFL. This, in contradiction shows that B is not a Deterministic Context free language.

Therefore, It has been proved that is B not a deterministic Context-free Language.