What language is accepted by the pushdown automaton \(M=(\{q_0 , q_1 , q_2\},…
2021
What language is accepted by the pushdown automaton
\(M=(\{q_0 , q_1 , q_2\}, \{a, b\}, \{a, b, z\}, δ, q_0 , z, \{q_2 \})\)
with \( δ(q_0 , a, a) =\{ (q_0 , aa) \}; δ(q_0 , b, a) =\{(q_0 , ba)\}\)
\(δ(q_0 , a, b) =\{ (q_0 , ab) \}; δ(q_0 , b, b) =\{ (q_0 , bb) \}\)
\(δ(q_0 , a, z) =\{ (q_0 , az) \}; δ(q_0 , b, z) =\{ (q_0 , bz) \}\)
\(δ(q_0 , λ, b) =\{ (q_1 , b) \}; δ(q_0 , λ, a) =\{ (q_1 , a) \}\)
\(δ(q_1 , a, a) =\{ (q_1 , λ) \}; δ(q_1 , b, b) =\{ (q_1 , λ) \}\)
\(δ(q_1 , λ, z) ={ (q_2 , z) }\) ?
- A.
\(L = \{ w | n_a(w) = n_b (w), w \ Є \ \{a, b\}^+ \}\) - B.
\(L = \{ w | n_a(w) <= n_b (w), w \ Є \ \{a, b\}^+ \}\) - C.
\(L = \{ w | n_b(w) <= n_a (w), w \ Є \ \{a, b\}^+ \}\) - D.
\(L = \{ ww^R, w \ Є \ \{a, b\}^+ \}\)
Attempted by 59 students.
Show answer & explanation
Correct answer: D
Key idea: a pushdown automaton can decide a mirror-image (reversal) language of the form { w wR } by nondeterministically choosing a split point: it pushes an unbounded prefix onto the stack in a first phase, then switches to a second phase where every remaining input symbol must exactly match (and pop) the current stack top. The string is accepted only if the stack unwinds all the way back to its bottom marker exactly when the input is exhausted — this forces the second half to be the exact reverse of the first half. This specific machine (states q0, q1, q2) implements exactly that pattern:
While in q0, on reading each input symbol (a or b) the machine pushes that same symbol onto the stack (so the stack holds the first segment in order).
At any point after at least one push (the top is a or b, not z), the PDA can take an epsilon transition to q1, leaving the stack unchanged.
In q1, for each remaining input symbol the PDA requires that it equals the stack top and pops that top. This forces the remaining input to be the reverse of the pushed prefix.
When the stack returns to the bottom symbol z and no input remains, the PDA moves to the accepting state q2.
Consequences: the machine accepts exactly strings formed by some nonempty w followed by its reverse.
Formal language: L = { w wR | w ∈ {a,b}+ }.
Example accepted string: "abba" (take w = "ab"). Example rejected string: "ab" (equal counts but not of the form w wR).
A video solution is available for this question — log in and enroll to watch it.