The Equivalence of Context-Free Grammars and PushDown Automata

Theorem:

• For every CFG , there is a PDA with .

• For every PDA , there is a CFG with .

Informal Proof:

Every CFL language is accepted by some PDA.

Let be the CFL in Chomsky Normal Form.

1. The corresponding PDA has the following states:

• • A start states and a secondary start state

  • A main "loop" state and additional states , for every will be used to "push productions" of the form onto the stack.

  • An accept state

2. The input alphabet is

3. The stack alphabet , where is some new nonterminal.

4. The transition rules are:

• and

  That is, push onto the stack.

   

• for all

  That is pop terminals from the stack if they match the next input symbol. Note; If you see non-matching terminals...failure no rule!

   

• for all rules of the form , and all rules of the form

  Either replace with some appropriate terminal , or begin replacing with on the top of the stack.

   

• for all

  Push the other nonterminal in the "Chomsky Production"

   

• 

  Pop the last symbol on the stack and go to the accept state.

   

Example: To be done in class:

A Chomsky Version:

________________________________________________________

Homework Due October 20

a. Problem 2.10 Page 129 from the Text.

b. Apply the above method to find a PDA equivalent to

.

_________________________________________________

Every PDA language is accepted by some CFL.

Some assumptions:

We can always find an equivalent PDA such that:

1. There is a single accept state ,

2. The stack is empty when a string is accepted.

3. Every stack operation is either a push or a pop. That is there are no replacement operations.

We now construct G:

• Add Variables: for all pairs .

• Let be the start variable.

Production Rules:

• For all pairs , add the rule .

• For all add the rule

• For states and add the rule

  if and