GATE CS 2016 Set 2 Q17 — Regular and Context-free Languages

To determine the correctness of statements P and Q, let us analyze the languages generated by the two grammars.

1. Analysis of Language $L_1$

The grammar for $L_1$ is given by:

By repeatedly applying the production rules, we generate strings with nested, matching pairs of $a$'s and $b$'s:

• $S_1 \Rightarrow \varepsilon$
• $S_1 \Rightarrow a S_1 b \Rightarrow ab$
• $S_1 \Rightarrow a S_1 b \Rightarrow aa S_1 bb \Rightarrow aabb$

In general, the language generated is:

Since recognizing $L_1$ requires keeping track of the exact count of $a$'s to match with the same number of $b$'s, it requires infinite memory. Thus, $L_1$ is a non-regular context-free language. Therefore, statement P is false.

2. Analysis of Language $L_2$

The grammar for $L_2$ is given by:

This is a right-linear grammar where the non-terminal $S_2$ always appears at the rightmost end of the production. Let's trace the derivations:

• $S_2 \Rightarrow \varepsilon$
• $S_2 \Rightarrow ab S_2 \Rightarrow ab$
• $S_2 \Rightarrow ab S_2 \Rightarrow abab S_2 \Rightarrow abab$

In general, the language generated consists of any number of repetitions of the string "$ab$":

Since $L_2$ can be defined by the regular expression $(ab)^*$, it is a regular language. Therefore, statement Q is true.

Conclusion

Since P is false and Q is true, the correct option is C.