Class Work 12: Pushdown Automata

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Grading Notes:

• Submit one answer per group.
• Make sure that the answer is legible.
• Include the full names of all group members on your submitted work (so all get credit).

1. Show that the language:

   L = {w | w contains more 1s than 0s}

   is not regular.
2. Give a context-free grammar for the language, L.
3. Design the state diagram for the pushdown automata that accepts the language, L.