What language does this Pushdown Automata (PDA) accept?

Question

Exam tomorrow and the prof let us know a question that would be on it :).

In the context of this diagram, L is epsilon (The empty string), and Z0 is the stack empty symbol.

I've made some progress in determining a few rules about the words the language generates, but haven't been able to pin down the entire language.

Thanks!

Answer 1

This PDA is not nearly as non-deterministic as it appears at first glance... Consider the following cases.

1. Suppose the input starts with ab. Then we go to state 2 with an empty stack, so the "L" rule does not match, so we are only in state 2.

2. Suppose the input starts with (a^n)b for n > 1. Then we go to state 2 with a^(n-1) on the stack, and the "L" rule triggers taking us back to state 1 with a^(n-2) on the stack. But since the stack in state 2 is a^(n-1) (and n>1), the loop-back arrows on state 2 cannot match... So here again, we are (effectively) only in one state: state 1.

3. Suppose the input starts with ba. Then again we go to state 2 with an empty stack, and as in case (1), the "L" rule does not match so we are only in state 2.

4. Finally, suppose the input starts with (b^n)a for n > 1. Then we go to state 2 with with b^n on the stack, so the "L" rule does not trigger and we are only in state 2.

In other words, any time the "L" rule creates a "fork" of the PDA into state 1, it only does so because "a" was on top of the stack... Which implies that the fork remaining in state 2 must die on the very next input symbol. So in effect there is no non-determinism here, and you can model this PDA as if it is always in just one state.

With this observation in hand, I think it is pretty easy to see that @Nayuki is correct: This PDA accepts any string with twice as many a's as b's.

First, show that when the PDA is in state 1, the stack always consists entirely of a's or entirely of b's (or is empty). And when the PDA is in state 2, the stack consists entirely of b's (or is empty). This is a simple case analysis similar to the four cases above; e.g. "state 1, stack=a^n, next character b => state 1, stack=a^(n-2)". (Taking care for the cases of n=0 or n=1.)

Think of each b as "wanting to be partnered with 2 as". State 1, stack=a^n means n as are waiting for partners. State 1, stack=b^n means n bs are waiting for partners. State 2, stack=b^n means one b was partnered with one a and n bs are still waiting for partners.

Prove that what I just wrote is true, and the result follows.