The language accepted by the nondeterministic pushdown automaton is___.

Question

The language accepted by the nondeterministic pushdown automaton $M= (\{q_0, q_1, q_2\}, \{a, b\}, \{a, b, z\}, δ, q_0, z, \{q_2\})$ with transitions $$δ (q_0, a, z) = \{ (q_1 a), (q_2 λ)\},$$ $$δ (q_1, b, a) = \{ (q_1, b)\},$$ $$δ (q_1, b, b) =\{ (q_1 b)\},$$ $$δ (q_1, a, b) = \{ (q_2, λ)\}$$ is_________.

1. $L(abb^*a) $
2. $ \{a\} \cup L(abb^*a)$
3. $ L(ab^*a)$
4. $ \{a\} \cup L(ab^*a)$

---

My attempt:

Given states $\{q_0, q_1, q_2\}$ with $q_0$ and $q_2$ are starting state and final state respectively. And, alphabet $\Sigma\{a, b\}$. I found that language should be $ \{a\} \cup L(ab^*a)$ But, official key is given option $(2).$

Can you explain it, please?

Answer 1

Note: The Kleene Star also includes the empty string. i.e. $b^* = \{\lambda, b, bb, bbb, \dots\}$.

Here is a representation of the automata

Where an edge labeled $(a, b, c)$ means to read character $a$ from the string, read (and pop) string $b$ from the top of the stack, and push string $c$ to the stack. With the diagram it should be pretty clear.

$a$ is accepted: since $(q_2, \lambda) \in \delta(q_0, a, z)$.

Can you see why $aa$ is not accepted? Can you see why $aba, abba, abbba, \dots$ are accepted?