Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2010
Hard
Consider the languages L1={0^i1^j | i≠j}, L2={0^i1^j | i=j}, L3={0^i1^j | i=2j+1}, L4={0^i1^j | i≠2j}. Which one of the following statements is true?
- AOnly L2 is context free.
- BOnly L2 and L3 are context free.
- COnly L1 and L2 are context free.
- All are context free.
Explanation
L2 is the classic context-free {0ⁿ1ⁿ}. L3 (i=2j+1) is a simple linear relation, directly generated by a CFG. L1 (i≠j) = (i<j case) ∪ (i>j case), and L4 (i≠2j) = (i<2j case) ∪ (i>2j case) — each of these cases is individually context-free (simple linear-count CFGs), and context-free languages are closed under union, so L1 and L4 are context-free too. All four are context-free.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.