Next: Proving that a Language Up: PUSH-DOWN AUTOMATA Previous: Deterministic PDAs   Contents

Non-Deterministic CFLs

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:

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

This is a PDA over the alphabet . To see what language it recognises, consider its actions on an input of for some fixed .

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.

Next: Proving that a Language Up: PUSH-DOWN AUTOMATA Previous: Deterministic PDAs   Contents
James Power 2002-11-29