Project ForgeConsider the transition diagram of a PDA with input alphabet Σ={a,b} and stack alphabet Γ={X,Z} (Z the initial stack symbol). The start state q0 (itself accepting) has self-loops on (a,X/XX) and (a,Z/XZ), and a transition to state q1 on (b,X/ε). State q1 has a self-loop on (b,X/ε), and a transition to a final accepting state q2 on (ε,Z/Z). Let L denote the language accepted by the PDA. Which one of the following is TRUE?
- AL={aⁿbⁿ|n≥0} and is not accepted by any finite automata
- BL={aⁿ|n≥0}∪{aⁿbⁿ|n≥0} and is not accepted by any deterministic PDA
- CL is not accepted by any Turing machine that halts on every input
- L={aⁿ|n≥0}∪{aⁿbⁿ|n≥0} and is deterministic context-free
Explanation
Since q0 itself is accepting, reading only a's (self-loop, staying in q0) accepts aⁿ for any n≥0 directly. Alternatively, after some a's, reading b's transitions to q1, popping one X per b; once all X's are popped (n a's matched by n b's), an ε-move on exposing Z reaches the final accepting state q2 — accepting aⁿbⁿ. So L={aⁿ|n≥0}∪{aⁿbⁿ|n≥0}. Since every state's transitions are unambiguous (no two transitions apply to the same input+stack-top configuration), this automaton, exactly as given, IS a valid deterministic PDA — so L is deterministic context-free.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.