Which of the following language over {a, b, c} is accepted by a deterministic…
1997
Which of the following language over {a, b, c} is accepted by a deterministic pushdown automaton?
- A.
{ wcwR ∣ w ∈ {a,b}∗ }
- B.
{ wwR ∣ w ∈ {a,b,c}∗ }
- C.
{ anbncn∣n≥0}
- D.
{ w ∣ w is a palindrome over {a,b,c}}
Attempted by 41 students.
Show answer & explanation
Correct answer: A
A Deterministic Pushdown Automaton (DPDA) operates with strict state transitions. Option 0 defines the language {wcw^R | w ∈ {a,b}*}, where 'c' serves as a deterministic center marker. The DPDA pushes input symbols until it encounters 'c', then switches to popping mode to verify the suffix matches the reverse of the prefix. Options 1 and 3 describe unmarked palindrome languages (e.g., {ww^R}), which require non-determinism to locate the midpoint, making them context-free but not deterministic. Option 2 describes a language requiring multiple independent counters (e.g., {a^n b^n c^n}), which is not context-free and exceeds PDA capabilities. Therefore, only Option 0 is accepted by a DPDA.
A video solution is available for this question — log in and enroll to watch it.