Give pushdown automata for the following languages Note that

Give pushdown automata for the following languages. (Note that you do not need to prove that your automata are correct, merely produce them.) {w omega {a, b}* | w has the same number of as and bs}. {a^m b^n | 0 lessthanorequalto 2m lessthanorequalto n}.

Solution

1) PDA that takes the second approach. This machine actually needs three states since it needs two states for
processing b\'s to allow for the case where two b\'s are read but only a single a is popped. So M = ({s, f, g}, {a, b},
{a}, , s, {f, g}), where
= { ((s, a, ), (s, a)), /* Read an a and push one onto the stack */
((s, , ), (f, )), /* Jump to the b reading state */
((f, b, a), (f, )), /* Read a single b and pop an a */
((f, b, a), (g, )), /* Read a single b and pop an a but get ready to read a second one */
((g, b, ), (f, ))}. /* Read a b without popping an a */

2)
PDA in a single state. But, because we\'re using the bottom of stack symbol #, we need two additional states:
the start state, in which we do nothing except push # and move to the working state, and the final state, which we
get to once we\'ve popped # and can then do nothing else. Considering all these issues, we get M = ({s, q, f}, {a,
b}, {#, a, b}, , s, {f}), where
= { ((s, , ), (q, #)), /* push # and move to the working state q */
((q, a, #), (q, a#)), /* the stack is empty and we\'ve got an a, so push it */
((q, a, a), (q, aa)), /* the stack is counting a\'s and we\'ve got another one so push it */
((q, b, a), (q, )), /* the stack is counting a\'s and we\'ve got b, so cancel a and b */
((q, b, #), (q, b#)), /* the stack is empty and we\'ve got a b, so push it */
((q, b, b), (q, bb)), /* the stack is counting b\'s and we\'ve got another one so push it */
((q, a, b), (q, )), /* the stack is counting b\'s and we\'ve got a, so cancel b and a */
((q, , #), (f, ))}. /* the stack is empty of a\'s and b\'s. Pop the # and quit. */