Homework 6: Pushdown Automata (12 Points)
Chris Tralie
Overview / Logistics
The purpose of this problem set is to get you experience designing pushdown automata, which will serve as a warmup to our ultimate destination in this course: Turing machines. What's neat about all of the languages in these problems is that they aren't regular (you could prove this with the pumping lemma), but they're still simple enough that just having a rudimentary stack for memory is enough to recognize them.
In all of the problems below, you should design and submit a JFLAP file. Be sure to only push or pop one character at a time.
Problem 1 (3 Points)
Design a pushdown automaton that recognizes the following language
\[ L = \{ a^{2n}b^{5n} | n \geq 0 \} \]
Below are some tests you can try in JFLAP (Click here to download them)
| Input | Result |
| aabbbbb | Accept |
| aabbbbbb | Reject |
| aaabbb | Reject |
| aaaaaabbbbbbbbbbbbbbb | Accept |
| aaaaaaaabbbbbbbbbbbbbbbbbbbb | Accept |
| aabb | Reject |
| aaaaaaaabbbbbbbbbbbbbbbbbbbbbb | Reject |
| aabbbbbbbbbb | Reject |
| aaabbbbb | Reject |
Problem 2 (3 Points)
Design a pushdown automaton that recognizes the following language
\[ L = \{ a^nb^mc^md^n | m, n \geq 0 \} \]
Below are some tests you can try in JFLAP (Click here to download them)
| Input | Result |
| aabbbbb | Reject |
| aaaddd | Accept |
| aaabcddd | Accept |
| abbbbccccd | Accept |
| abbbbccccdd | Reject |
| bbbbcccc | Accept |
| bbbbccccc | Reject |
| aabbbbccccdd | Accept |
| dcba | Reject |
Problem 3 (3 Points)
Design a pushdown automaton that recognizes the following language
\[ L = \{w\#x | w^R \text{ is a substring of } x \text{ for } w, x \in \{0,1\}^* \}\]
Below are some tests you can try in JFLAP that should all accept (Click here to download them). I'm showing w in red and wR, the reverse of w, in blue. The entire substring after the red portion is x. I'm separating these tests out because with nondeterminism, it's possible that JFLAP will warn you that a ton of configurations are being generated, so it's nice to do these ones separately.
| Input | Result |
| 10110#1111011011 | Accept |
| 00101#01010100 | Accept |
| 1110100#01000101110 | Accept |
| 01010#10100101001 | Accept |
| 01011100#0000001110100 | Accept |
| #0101 | Accept (Empty w) |
Below are some inputs that should be rejected (Click here to download them). These tests will run faster
| Input | Result |
| 00#111 | Reject |
| 01010#11001100 | Reject |
| 101100#10110 | Reject |
| 01010#10100101 | Reject |
| 01011100#01110100 | Reject |
Problem 4 (3 Points)
The following context free grammar generates the language of binary strings with the same number of 1s as 0s
- S → λ
- S → 0S1S
- S → 1S0S
Devise a pushdown automaton that recognizes the same language. Below are some tests you can apply in JFLAP (Click here to download them)
| Input | Result |
| 01011011 | Reject |
| 11001100 | Accept |
| 0111001100 | Accept |
| 0101110010 | Accept |
| 001111 | Reject |
| 000000110 | Reject |
| 10001 | Reject |
| 11001000 | Reject |
| 0101101001 | Accept |
| 00100111 | Accept |