Consider the pushdown automaton (PDA) P below, which runs on the input…
2023
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {⊥, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/γ, where c is an input symbol or , X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v. In the initial configuration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack.
Which one of the following options correctly describes the language accepted by P?
- A.
{am bn | 1 ≤ m and n < m}
- B.
{am bn | 0 ≤ n ≤ m}
- C.
{am bn | 0 ≤ m and 0 ≤ n}
- D.
{am | 0 ≤ m} ∪ {bn | 0 ≤ n}
Attempted by 83 students.
Show answer & explanation
Correct answer: A
Key insight: the PDA uses A symbols to count a's and pops one A per b; acceptance happens only if at least one A was pushed and strictly more a's than b's remain to be popped by ε-transitions.
Reading an a: the PDA pushes an A (so each a increases the A-count). The very first a is required to get an A on top of ⊥.
Reading a b: the PDA has transitions that consume one b and pop one A (so each b decreases the A-count). There is no b transition when the top is ⊥, so b's cannot appear before at least one a.
After reading input, the PDA may take ε-transitions that pop remaining A's and then pop ⊥ to accept by empty stack. To be able to reach those ε-transitions that pop A, there must be at least one A on the stack.
Conclusion: The PDA accepts exactly strings of the form {a^m b^n | 1 ≤ m and n < m}.