COMS W3261 CS Theory
Lecture 9: CFG's and PDA's

1. From a CFG to an Equivalent PDA

2. From a PDA to an Equivalent CFG

3. Eliminating Useless Symbols from a CFG

4. Eliminating ε-productions from a CFG

5. Eliminating Unit Productions from a CFG

6. Putting a CFG into Chomsky Normal Form

7. Practice Problems

  1. Convert the following grammar
  2. to an equivalent PDA that accepts by empty stack.

  3. Convert your PDA from problem (1) to an equivalent PDA that accepts by final state.

  4. Convert your PDA from problem (1) to an equivalent CFG.

  5. Eliminate useless symbols from the following grammar:
  6. Put the following grammar into Chomsky Normal Form:

8. Reading


aho@cs.columbia.edu
verma@cs.columbia.edu