GATE 2010 CS (CS1) – Question 50
For nonnegative i,j, let $L_1=\{0^i1^j:i\ne j\}$, $L_2=\{0^i1^j:i=j\}$, $L_3=\{0^i1^j:i=2j+1\}$ and $L_4=\{0^i1^j:i\ne2j\}$. Which is true?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) All are context-free
Explanation
A pushdown automaton can compare zeros and ones one-for-one for L₂ and two-for-one with one extra zero for L₃. For L₁, split into i<j and i>j; each comparison is context-free and their union is context-free. Similarly split L₄ into i<2j and i>2j using two-for-one stack comparison. Thus all four are context-free, D.