GATE CS 2009 Q40 — Regular and Context-free Languages

To find the nature of the language $L = L_1 \cap L_2$, let us analyze the two given languages:

• $L_1 = \left\{ a^m b^m c a^n b^n \mid m, n \geq 0 \right\}$
• $L_2 = \left\{ a^i b^j c^k \mid i, j, k \geq 0 \right\}$

Note that $L_2$ is a regular language represented by the regular expression $\mathbf{a^* b^* c^*}$. This means any string in $L_2$ must have all $a$'s first, followed by all $b$'s, and then all $c$'s.

For a string $w \in L_1$ to also belong to $L_2$, it must satisfy the character ordering of $a^* b^* c^*$:

• The general form of a string in $L_1$ is $w = a^m b^m c a^n b^n$.
• If $n > 0$, the string contains $a$'s and $b$'s after the character $c$, which violates the pattern $a^* b^* c^*$.
• Therefore, we must have $n = 0$ for the string to be in $L_2$.

Substituting $n = 0$ into the expression for $L_1$, we get:

Now, let us analyze the language $L$:

1. Not Regular: It requires matching the number of $a$'s and $b$'s ($m$ of each), which requires infinite memory (a stack) and cannot be recognized by a Finite Automaton.
2. Context-Free: It can be generated by the following Context-Free Grammar (CFG):
   $S \to X c$
   $X \to a X b \mid \epsilon$
   It can also be easily accepted by a Pushdown Automaton (PDA) by pushing $a$'s onto the stack and popping them for each $b$, then reading $c$.

Thus, $L$ is context-free but not regular.