GATE CS 2010 Q40 — Context-free Grammars and Push-down Automata

All four languages are context-free because we can construct either a Context-Free Grammar (CFG) or a Pushdown Automaton (PDA) for each of them:

• $L_2 = \{0^i 1^j \mid i = j\}$: This is the standard matching language. A PDA can push $0$'s onto the stack and pop them for each $1$. Thus, $L_2$ is context-free.
• $L_1 = \{0^i 1^j \mid i \neq j\}$: This can be written as the union of two context-free languages: $\{0^i 1^j \mid i > j\} \cup \{0^i 1^j \mid i < j\}$. Since context-free languages are closed under union, $L_1$ is context-free.
• $L_3 = \{0^i 1^j \mid i = 2j + 1\}$: We can easily write a CFG for this language: $$S \to 00S1 \mid 0$$ Since a CFG exists, $L_3$ is context-free.
• $L_4 = \{0^i 1^j \mid i \neq 2j\}$: Similar to $L_1$, this can be expressed as the union of two context-free languages: $\{0^i 1^j \mid i > 2j\} \cup \{0^i 1^j \mid i < 2j\}$. Thus, $L_4$ is context-free.

Therefore, all the given languages are context-free.