Give a DETERMINISTIC pushdown automaton that recognizes all

Give a DETERMINISTIC pushdown automaton that recognizes all strings where the number of a\'s is exactly twice the number of b\'s.

Solution

(Number of a\'s read so far) - 2*(Number of b\'s read so far)

= (Number of a\'s on stack) - (Number of b\'s on stack)

We can do all this with 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, aa), (q, )), /* the stack is counting a\'s and we\'ve got b, so cancel aa and b */

((q, b, a#), (q, b#)), /* the stack contains a single a and we\'ve got b, so cancel the a and b

and start counting b\'s, since we have a shortage of one a */ ((q, b, #), (q, bb#)), /* the stack is empty

and we\'ve got a b, so push two b\'s */ ((q, b, b), (q, bbb)), /*

the stack is counting b\'s and we\'ve got another one so push two

*/ ((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. */