Consider the languages L1 = {0i 1j

Home » Theory of Computation » Theory of computation miscellaneous » Question

Consider the languages L₁ = {0ⁱ 1^j | i ≠ j}, L₂ = {0ⁱ 1^j | i = j}, L₃ = {0ⁱ 1^j | i = 2j + 1 j}, L₄ = {0ⁱ 1^j | i ≠ 2j}. Which one of the following statements is true?

1. Only L₂ is context-free
2. L₂ and L₃ are context-free
3. L₁ and L₂ is context-free
4. All are context free

Correct Option: D

These sort of languages are accepted by PDA, so all should be context free languages. L₂ & L₃ are definitely CFL since accepted by stockof PDA.
And also L₁ & L₄ are linear comparisons of i & j so can also be represented using PDA. So all are context free languages.