Which of the following languages over {a,b,c} is accepted by a deterministic…
1997
Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?
- A.
{w c w R ∣ w ∈ {a,b}∗}
- B.
{ w wR ∣ w ∈ {a,b,c}∗}
- C.
{an bn cn | n ≥ 0}
- D.
{w ∣ w is a palindrome over {a,b,c}}
Attempted by 6 students.
Show answer & explanation
Correct answer: A
The language {w c wR | w∈{a,b}*} is accepted by a deterministic pushdown automaton because the middle symbol 'c' acts as an unambiguous center marker. The PDA can push all symbols from w onto the stack, transition upon reading 'c', and then pop to match the reversed portion. In contrast, palindromes without a center marker require non-determinism to guess the midpoint.
Loading lesson…