# The language accepted by the nondeterministic pushdown automaton is___.

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).$

• Maybe your confusion is with the Kleene star operator. Do you understand that $b^* = \{\lambda, b, bb, bbb, \dots\}$? Mainly, do you understand that $b^*$ means $0$ or more $b$s? – Enrico Borba Dec 20 '16 at 13:45
• @EnricoBorba, there is difference between $bb^*=b^+$ and $b^*$. Am I right? – 1 0 Dec 20 '16 at 17:01
• Yes. $bb^* = b^+ = \{b, bb, bbb, \dots\}$. However, $b^* = \{\lambda\} \cup b^* = \{\lambda, b, bb, bbb, \dots\}$. See the Kleene Star wikipedia page for more info. – Enrico Borba Dec 20 '16 at 17:35

Note: The Kleene Star also includes the empty string. i.e. $b^* = \{\lambda, b, bb, bbb, \dots\}$.
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?