Over =\0,1,c\, let L 1=\0n1n:n0\, L 2=\wcwr:w\0,1\*\, L 3=\wwr:w\0,1\*\, where wr reverses w. Which languages are deterministic context-free?

GATE 2014 CS (CS3) – Question 46

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

Over $\Sigma=\{0,1,c\}$, let $L_1=\{0^n1^n:n\ge0\}$, $L_2=\{wcw^r:w\in\{0,1\}^*\}$, $L_3=\{ww^r:w\in\{0,1\}^*\}$, where $w^r$ reverses w. Which languages are deterministic context-free?

None
Only L₁
Only L₁ and L₂
All three

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Only L₁ and L₂

Explanation

A deterministic pushdown automaton recognises0ⁿ1ⁿby switching from push to pop at the first1. It also recognises wcw^Rbecause cexplicitly marks the midpoint. Inww^Rthere is no marker telling a deterministic machine when to switch. Hence **onlyL1andL2,C**.