Consider the transition diagram of a PDA given below with input alphabet \(Σ =…
2016
Consider the transition diagram of a PDA given below with input alphabet \(Σ = \{a,b\}\) and stack alphabet \(Γ = \{X,Z\}\). \(Z\) is the initial stack symbol. Let \(L\) denote the language accepted by the PDA.
Which one of the following is TRUE?
- A.
\(L =\{a^nb^n\mid n \geq0 \}\)and is not accepted by any finite automata - B.
\(L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}\)and is not accepted by any deterministic PDA - C.
\(L\)is not accepted by any Turing machine that halts on every input - D.
\(L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}\)and is deterministic context-free
Attempted by 108 students.
Show answer & explanation
Correct answer: D
Key idea: the PDA accepts either only a's by staying in the start state, or equal numbers of a's followed by b's by switching states and popping the stack.
Step 1: Accepting a^n. The start state is accepting and has transitions on a that push X (a,Z→XZ and a,X→XX). By looping on the start state for n a's the machine accepts a^n.
Step 2: Accepting a^n b^n. On the first b the PDA must take the transition b,X→ε to the middle state (this requires an X on the stack). In the middle state it loops on b,X→ε, popping one X per b. When all X's are popped and the top is Z, an ε-transition ε,Z→Z moves to the final accepting state, so a^n b^n is accepted.
Step 3: Rejection cases. If a b appears when the top of the stack is Z (i.e., there were fewer a's than b's or the string starts with b), no transition is available, so such strings are rejected.
Step 4: Determinism. For each state, input symbol (or ε) and top-of-stack symbol there is at most one applicable transition. The two a-loops are distinguished by top-of-stack X versus Z, and the ε-transition is only possible when the top is Z. Thus the PDA is deterministic.
Conclusion: L = {a^n} ∪ {a^n b^n}, and this language is deterministic context-free.
A video solution is available for this question — log in and enroll to watch it.