The language accepted by the non-deterministic pushdown automaton M = ({q0,…
2013
The language accepted by the non-deterministic pushdown automaton
M = ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) with transitions
δ(q0, a, z) = { (q1, a), (q2, ε) }
δ(q1, b, a) = { (q1, b) }
δ(q1, b, b) = { (q1, b) }
δ(q1, a, b) = { (q2, ε) }
- A.
L(abb* a)
- B.
{a} ∪ L(abb* a)
- C.
L(ab* a)
- D.
{a} ∪ L(ab* a)
Attempted by 13 students.
Show answer & explanation
Correct answer: B
The NPDA accepts 'a' directly via δ(q0, a, z) → (q2, ε), reaching the final state q2 immediately. Alternatively, it enters q1 with stack 'a', requiring at least one 'b' to push 'b's, then an 'a' to pop a 'b' and reach q2. Thus, the language is {a} ∪ L(abb*a).
A video solution is available for this question — log in and enroll to watch it.