Yesterday I had a final exam in a formal languages and automata course. I got through most of it okay, but got stuck on a PDA (pushdown automaton [1]). The problem:

Design a PDA over language {a,b} such that count(a) = (2 * count(b)) + 1.

Only one stack allowed.

I stared at it for well over an hour, nearly twice as long as the rest of the test combined (tracing SLR(0) processing is fun!). Ultimately, as time was running out, and I hadn't come up with a solution, I went with something that at least solved several of the test strings that ruled out at least 6-8 other failed solutions.

[2]

I *think* this "two pops are better than one" strategy doesn't work on strings that are mixed up a lot. Like, "abaa" leaves an empty stack when input exhausts, which will be rejected.

Lazyweb corraboration/rejection of the hunch that this is wrong would be *greatly* welcome. The dot source is attached in case anybody wants to suggest a correction.

[Update (2006-05-17)] Tony's correct version, described in his comment below, looks like this:

[3]

Tweaked dotfile attached, too.