The important point then is that:
not every context-free language is determinstic
To see this, consider the language
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 and . 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:
This is a PDA over the alphabet . To see what language it
recognises, consider its actions on an input of for some
Initially it will move from the start state to a final state of
while consuming the input . Because it is deterministic,
there is no other state which it could reach while consuming this
input. But we know that by its construction can now also go on
to accept more copies of
; therefore if we run the new
PDA on the rest of the input, it will consume more copies of
as it moves through .
Thus the constructed PDA accepts the language
- 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.