Non-Deterministic CFLs

The important point then is that:
not every context-free language is determinstic

To see this, consider the language $\{x^ny^n \;\mid\; n \geq 0\} \cup \{x^ny^{2n} \;\mid\; n \geq 0\}$ We can easily show that this context-free by giving its CFG. However, we will show that it is not deterministic context-free.

Proof: (by contradiction)

Suppose that this language is deterministic context-free; then it has a corresponding deterministic PDA.

Let us create two copies of this PDA called $M_1$ and $M_2$. Call any two states ``cousins'' if they are copies of the same state in the original PDA. Now we construct a new PDA as follows:

• The states of the new PDA is the union of the states in $M_1$ and $M_2$, where
  • the start state of $M_1$ is the new start state
  • the final states of $M_2$ are the new final states
• The transition relation is that of $M_1$ and $M_2$ with the following alterations:
  • Change any transition originating from a final state in $M_1$ so that it now goes to its ``cousin'' state in $M_2$
  • Change all those $\hbox{\lq }{y}\hbox{'}$ transitions which cause a move into some state from $M_2$ into $\hbox{\lq }{z}\hbox{'}$ transitions

This is a PDA over the alphabet $\{x,y,z\}$. To see what language it recognises, consider its actions on an input of $x^ky^kz^k$ for some fixed $k \geq 0$.

Initially it will move from the start state to a final state of $M_1$ while consuming the input $x^ky^k$. Because it is deterministic, there is no other state which it could reach while consuming this input. But we know that by its construction $M_1$ can now also go on to accept $k$ more copies of $\hbox{\lq }{y}\hbox{'}$; therefore if we run the new PDA on the rest of the input, it will consume $k$ more copies of $\hbox{\lq }{z}\hbox{'}$ as it moves through $M_2$.

Thus the constructed PDA accepts the language $\{x^ny^nz^n \;\mid\; n \geq 0\}$ - but this is impossible, as this language is not context free. Thus our assumption that the PDA for the original language could be deterministic is contradicted.
${\cal QED}$