Trying to figure what language this PDA (pushdown automata) accepts

Question

I have the following PDA and I can't figure our what words it accepts, would like to get some help with figuring this out.

Of course it only accepts if that stack is empty in the accepting state.

Answer 1

The first thing to note is that $a^n$ ends up in the acceptor state if and only if $n=3m+2$ for some integer $m\ge 0$. Next, every time you go around the circuit the parity of the number of $a$s on the stack changes, and the parity also changes when you read two $a$s to go from the initial state to the acceptor state. In order to end up with an empty stack at the acceptor state, therefore, $m$ must be odd. It’s easy to check that $m=1$ doesn’t work: $a^5$ is not in the language. With a bit more work one can discover that $m=3$ does work: $a^{11}$ is in the language. I’ll leave it to you to discover the appropriate path.

Now suppose that we’re in the acceptor state with an empty stack. Since the parity of the stack size changes every time we go round the circuit, we’ll have to go round an even number of times in order to have any hope of returning to the acceptor state with an empty stack. Show that it’s possible to do so by reading $a^6$ (and going round the circuit twice). This shows that the language at least includes the set $\{a^{6k+11}:k\ge 0\}=\{a^{6k+5}:k\ge 1\}$. Can it include anything else?

We already know that if $a^n$ is in the language, then $n=3m+2$ for some $m\ge 0$. Moreover, we found that $m$ must be odd, so $n=3(2k+1)+2=6k+5$ for some $k\ge 0$. I leave it to you to verify by brute force if necessary that $a^5$ is not in the language, so in fact $k\ge 1$, and therefore $a^n\in\{a^{6k+5}:k\ge 1\}$. Thus, the language accepted by the PDA is $\{a^{6k+5}:k\ge 1\}$.