Consider the pushdown automaton (PDA) below which runs over the input alphabet…
2006
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.
(s, a, Z0) → (s, XXZ0)
(s, ϵ, Z0) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z0) → (f, ϵ)
The language accepted by the PDA is
- A.
{albmcn | l = m = n}
- B.
{albmcn | l = m}
- C.
{albmcn | 2l = m+n}
- D.
{albmcn | m=n}
Attempted by 11 students.
Show answer & explanation
Correct answer: C
The PDA pushes two X symbols for each 'a' read in state s, so the number of X's on the stack is 2l. It then pops one X for each 'b' and one X for each 'c', consuming exactly m + n X's. For the PDA to accept, all X's must be popped and only Z0 remains, requiring 2l = m + n. The final state f is reached when the stack contains only Z0, confirming that the language accepted matches option C.