GATE CS 2005 Q55 — Regular and Context-free Languages

Let us analyze the properties of the given languages:

$$L_1 = \{ a^nb^nc^m \mid n,m > 0 \}$$

$$L_2 = \{ a^nb^mc^m \mid n,m > 0 \}$$

• $L_1$ and $L_2$ are Context-Free Languages (CFLs):
  • For $L_1$, we can use a pushdown automaton (PDA) to push $a$'s onto the stack and pop them matching with $b$'s, while ignoring the count of $c$'s.
  • For $L_2$, we can ignore the count of $a$'s, push $b$'s onto the stack, and pop them matching with $c$'s.
  • Thus, both $L_1$ and $L_2$ are CFLs. Statement (C) is TRUE.
• $L_1 \cup L_2$ is a CFL:
  • Since the class of context-free languages is closed under union, and both $L_1$ and $L_2$ are CFLs, their union $L_1 \cup L_2$ is also a CFL.
  • Alternatively, a non-deterministic PDA can make an initial $\epsilon$-transition to either match $a$'s with $b$'s (for $L_1$) or match $b$'s with $c$'s (for $L_2$).
  • Thus, Statement (B) is TRUE.
• $L_1 \cap L_2$ is Context-Sensitive but NOT Context-Free:
  • The intersection of $L_1$ and $L_2$ is: $$L_1 \cap L_2 = \{ a^n b^n c^n \mid n > 0 \}$$
  • This is a classic non-context-free language because it requires comparing three counts ($n$ of $a$'s, $b$'s, and $c$'s) simultaneously, which cannot be done with a single stack.
  • However, it can be recognized by a Linear Bounded Automaton (LBA), making it a Context-Sensitive Language (CSL).
  • Thus, Statement (D) is TRUE, and Statement (A) is FALSE.

Therefore, the false statement is A.