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?

  • $\begingroup$ 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? $\endgroup$ – Enrico Borba Dec 20 '16 at 13:45
  • $\begingroup$ @EnricoBorba, there is difference between $bb^*=b^+$ and $b^*$. Am I right? $\endgroup$ – 1 0 Dec 20 '16 at 17:01
  • $\begingroup$ 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. $\endgroup$ – 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\}$.

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?

  • $\begingroup$ If this answers your question, please accept this as the answer. If not, is there anything I am missing? $\endgroup$ – Enrico Borba Dec 20 '16 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.