The automaton is depicted in the following figure.
The options given as the possibly recognizable strings are
- $\epsilon$
- $abb$
- $aabb$
- $aababb$
Now in my head the right answers are 1, 3 and 4. The empty string $\epsilon$ is acceptable, because the initial state $q_0$ is an accepting state. With option 2 we end up at a dead end with the following state transition chain: $$ \newcommand{\perm}[1]{\left\langle #1 \right\rangle} \newcommand{\trans}[1]{\overset{#1}{\longrightarrow}} \perm{ q_0, abb, \epsilon } \trans{\epsilon, \epsilon / p} \perm{ q_1, abb, p } \trans{a, \epsilon / bb} \perm{ q_1, bb, bbp } \,. $$ We can't transition to the state $q_2$ with the first letter $a$, as the contents of the stack limit this transition because of how the state transition function is defined. There are no letters $b$ to be replaced with $b$s at the top of the stack when we first reach the state $q_1$, so the only thing we can do is transition to $q_1$ and slap two $b$s on top of the stack. If we then received another $a$, we could transition to $q_2$ while keeping the stack unchanged (replacing a $b$ with another $b$ changes nothing).
This leads us to the last two options 3 and 4. They have (state) accepting transition chains \begin{align*} \perm{ q_0, aabb, \epsilon } &\trans{\epsilon, \epsilon / p} \perm{ q_1, aabb, p } \trans{a, \epsilon / bb} \perm{ q_1, abb, bbp } \trans{a, b / b} \perm{ q_2, bb, bbp } \\ &\trans{b, b / \epsilon } \perm{q_2, b, bp} \trans{b, b / \epsilon } \perm{q_2, \epsilon, p} \trans{\epsilon, p / \epsilon } \perm{q_3, \epsilon, \epsilon} \end{align*} and \begin{align*} \perm{q_0, aababb, \epsilon} &\trans{\epsilon, \epsilon / p} \perm{q_1, aababb, p} \trans{a, \epsilon / bb} \perm{q_1, ababb, bbp} \trans{a, b / b} \perm{ q_2, babb, bbp } \\ &\trans{b, b / b} \perm{ q_1, abb, bbp } \trans{a, b / b} \perm{q_2, bb, bbp} \trans{b, b / \epsilon} \perm{q_2, b, bp} \\ &\trans{b, b / \epsilon} \perm{q_2, \epsilon, p} \trans{\epsilon, p / \epsilon} \perm{q_3, \epsilon, \epsilon}\,. \end{align*} In fact, it looks like the languages recognized via accepting states and the emptying of the stack might be the same.
My problem however is that according to an automatic assessment system, my answer is incorrect. What did I miss here?
Edit
It occurred to me that since we have the possible transition $\perm{q_0, \epsilon, \epsilon} \trans{\epsilon, \epsilon / p} \perm{q_1, \epsilon, p}$, we might have a situation where we end up in a non-accepting state $q_1$ with the empty string. So non-determinism makes the empty string $\epsilon$ possibly unacceptable and therefore unacceptable in a non-deterministic setting. Am I right about this? I'm pretty certain my deductions about options 2, 3 and 4 are correct.