Topics

• How many languages are there?
• Nondeterministic Pushdown Automata.
• Deterministic Pushdown Automata.
• Converting Context Free Grammars to Pushdown Automata.

Problems to work on

Languages

1. Could I ever write a computer program that enumerated (listed) all the possible languages? What about one that enumerated all the regular languages? What about one that enumerated all the context-free languages?

   Pushdown Automata Warmup

2. What is the difference between a Nondeterministic Pushdown Automaton and a Deterministic Pushdown Automaton. Do you think they generate the same languages?
3. (Warm up) Construct a PDA that accepts the language {0,1}*.
4. (Warm up from last time:) Construct a PDA that accepts the language {0ⁿ1ⁿ | n >= 0}. Is your answer deterministic or not?
5. Construct a PDA that accepts the language {0ⁿ1ⁿ | n >= 2}.

   More Pushdown Automata

6. Construct a PDA that accepts the language { 0^m1ⁿ | n > m >= 0}
7. (From last time:) Construct a PDA that accepts the language {0ⁿ1^m0^m1ⁿ | n,m >= 0}.
8. Construct a PDA that accepts the language { w | w is not a palindrome}

   And/Or

9. Construct a PDA that accepts the language { w | w is not a palindrome and w ends with a zero}
10. Give a PDA that accepts the language {aⁱ b^j | i <= j <= 2i}

    Deterministic vs Nondeterministic PDA's

11. Construct a NPDA that accepts the language of strings with the same number of zeros and ones.
12. Construct a DPDA that accepts the language of strings with the same number of zeros and ones.

    Converting Grammars to PDA's

13. Convert the following Grammar to a PDA.

    S --> AB
    A -->  0
    B -->  1
    

14. Convert the following Grammar to a PDA.

    
    A --> BAB | B | epsilon
    B --> 00 | espilon