Problem 1

Draw the PDA defined by the 6-tuple below:

\[ \left( \{q_0,q_1,q_2,q_3\},\{a,b\},\{$,X\}, \left\{ \begin{array}{c} (q_0,\lambda,\lambda,q_1,\$), (q_1,a,\lambda,q_1,X), (q_1,b,X,q_2,\lambda),\\ (q_2,b,X,q_2,\lambda), (q_2,\lambda,\$,q_3,\lambda) \end{array} \right\}, q_0,\{q_0,q_3\} \right) \]

Problem 2

Use JFLAP to build a PDA accepting the language of all strings over the alphabet {a,b} having the same number of a's as b's. Notice that in this language the a's and b's can appear in any order! I recommend the Input/Fast Run ... option to test with. If there's no accepting computation, it tells you so. If there is, it list one accepting computation. Of course, since the machine is non-deterministic, there could be many. Note: While you don't actually need it for this problem, remember that you can push and pop arbitrary strings from the stack. Turn In a screen capture / printout showing your machine!

Problem 3

Read the formal PDA definition from the class notes and write down the 6-tuple representing your machine from Problem 2.

Problem 4

Write a grammar for language $\{a^m b^n\ |\ m = 2n\}$.