GATE CS 2013 Q32 — Regular and Context-free Languages

To find the FALSE statement, let us analyze the properties of the languages $L_1$ and $L_2$:

1. Analysis of $L_1$:

$$L_1 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0 \right \}$$

• There are no constraints or dependencies between the powers $p$, $q$, and $r$.
• Thus, $L_1$ can be represented by the regular expression $0^*1^*0^*$.
• Since $L_1$ is a regular language, its complement $\overline{L_1}$ must also be regular (as regular languages are closed under complementation).
• Therefore, the statement "Complement of $L_1$ is context-free but not regular" is FALSE.

2. Verification of other options:

• Option A: $L_2 = \left \{ 0^p1^q0^r \mid p \neq r \right \}$ requires comparing the count of $0$s before and after the $1$s. This single comparison ($p < r$ or $p > r$) can be easily performed using a Pushdown Automaton (PDA). Thus, $L_2$ is a context-free language (CFL). This statement is TRUE.
• Option B: Since $L_2 \subseteq L_1$, we have $L_1 \cap L_2 = L_2$. Since $L_2$ is a CFL, their intersection is also a CFL. (Alternatively, the intersection of a regular language $L_1$ and a CFL $L_2$ is always a CFL). This statement is TRUE.
• Option C: Every context-free language is recursive. Since $L_2$ is a CFL, it is recursive. Since recursive languages are closed under complementation, the complement of $L_2$ is also recursive. This statement is TRUE.