Consider the languages \(L1=\{0^i1^j\ \mid i \neq j\},\) \(L2=\{0^i1^j\mid…
2010
Consider the languages
\(L1=\{0^i1^j\ \mid i \neq j\},\)
\(L2=\{0^i1^j\mid i=j\},\)
\(L3=\{0^i1^j \mid i=2j+1\},\)
\(L4=\{0^i1^j \mid i\neq2j\}\)
Which one of the following statements is true?
- A.
Only
\(L_2\)is context free - B.
Only
\(L_2\)and\(L_3\)are context free - C.
Only
\(L_1\)and\(L_2\)are context free - D.
All are context free
Attempted by 99 students.
Show answer & explanation
Correct answer: D
Answer: All four languages are context-free.
L2 = {0^n1^n} is context-free. Example grammar: S -> 0 S 1 | ε.
L3 = {0^i1^j | i = 2j + 1} is context-free. Example grammar: S -> 0 | 00 S 1 (base j=0 gives '0'; each application adds 2 zeros and 1 one).
L1 = {0^i1^j | i ≠ j} equals 0^*1^* \ {0^n1^n}. The language {0^n1^n} is a deterministic CFL, so its complement over Σ* is a deterministic CFL; intersecting that complement with the regular language 0^*1^* yields a context-free language. Hence L1 is context-free.
L4 = {0^i1^j | i ≠ 2j} equals 0^*1^* \ {0^{2j}1^j}. The language {0^{2j}1^j} is context-free (example grammar: S -> 00 S 1 | ε) and in fact deterministic, so the same complement-and-intersect argument shows L4 is context-free.
Therefore every language listed is context-free.
A video solution is available for this question — log in and enroll to watch it.