Context Free Language – GATE CSE Theory Of ComputationPractice Questions & PYQs

Context-Free Languages (CFLs) are not closed under intersection or complementation, making options C and D false. Option A is false because deterministic Push-Down Automata (PDAs) only accept a proper subset of CFLs, known as Deterministic Context-Free Languages (DCFLs). For option B, if $L_1$ and $L_2$ are CFLs with grammars having start symbols $S_1$ and $S_2$, their union $L_1 \cup L_2$ is generated by a new grammar with the start rule $S \to S_1 \mid S_2$. This constructive proof demonstrates that the union of two CFLs is always a CFL.

The grammar $S \to 0S0 \mid 00$ recursively generates strings by adding a $0$ on both sides of a previously generated string, starting from the base case $00$. This produces the set of strings $L = \{0^{2n} \mid n \ge 1\} = \{00, 0000, 000000, \dots \}$. Since $L$ can be described by the regular expression $00(00)^*$, $L$ is a regular language. Comparing $L$ to $0^+ = \{0^n \mid n \ge 1\}$, we observe that $L$ only contains strings of even length, while $0^+$ contains all strings of zeros (including odd lengths). Thus, $L$ is regular but $L \neq 0^+$.

Context-Free Languages (CFLs) are closed under Union because if $L_1$ and $L_2$ are CFLs with grammar start symbols $S_1$ and $S_2$, their union $L_1 \cup L_2$ is generated by the new production $S \rightarrow S_1 | S_2$. Similarly, CFLs are closed under Kleene closure ($L^*$); if $L$ has grammar start $S_1$, then $L^*$ is generated by $S \rightarrow S_1 S | \epsilon$. Conversely, CFLs are not closed under Intersection or Complement, as demonstrated by the intersection of two CFLs resulting in non-context-free languages like $\{a^n b^n c^n \mid n \geq 0\}$. Therefore, the only correct pair listed is Union and Kleene closure.

Since $L_2$ is regular, its complement $\sim L_2$ is also regular. The set difference is $L_1 - L_2 = L_1 \cap (\sim L_2)$. Because context-free languages (CFLs) are closed under intersection with regular languages, $L_1 - L_2$ must be a CFL, making statement A false. Conversely, CFLs are not closed under complementation, so $\sim L_1$ is not necessarily a CFL, making statement C false. Statements B and D represent known closure properties (CFL $\cap$ Regular is a CFL, and Regular is closed under complement), so they are true.

[CORRECT_OPTION: A, C]

Context-Free Languages (CFLs) are closed under operations like union ($L_1 \cup L_2$), concatenation ($L_1.L_2$), and intersection with a regular set ($L_1 \cap R$). However, they are not closed under intersection with each other ($L_1 \cap L_2$). For example, let $L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$ and $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$, which are both CFLs. Their intersection is $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$, a language known to be non-context-free by the Pumping Lemma for CFLs. Therefore, $L_1 \cap L_2$ is not necessarily a context-free language.

The language $L$ is defined as $\{w \in \{0, 1\}^+ \mid n_0(w) = n_1(w)\}$. For any arbitrary binary string $u \in \{0, 1\}^*$, let $d = n_1(u) - n_0(u)$. To ensure $uv \in L$, we require a suffix $v$ such that the total number of $0$'s and $1$'s are equal, meaning $n_1(v) - n_0(v) = -d$. If $d \ge 0$, we can choose $v = 1^d$ if $d > 0$ (or a valid nonempty string like $01$ if $u = \varepsilon$ and $d=0$); if $d < 0$, we can choose $v = 0^{|d|}$. Since we can always find such a suffix $v$ for any $u$ to form a string in $L$, $\text{init}(L)$ contains every possible binary string, including the null string $\varepsilon$.

The language $L = \{x^n y^n \mid n \geq 1\}$ is a classic non-regular context-free language.
Definition I ($E \rightarrow xEy \mid xy$) is a context-free grammar that generates strings by adding one $x$ and one $y$ at each recursive step, starting from $xy$. This process yields $xy, xxyy, xxxyyy, \dots$, which exactly matches $L$.
Definitions II ($xy \mid x^+xyy^+$) and III ($x^+y^+$) are regular expressions that describe the language $\{x^n y^m \mid n, m \geq 1\}$. These definitions allow strings where the number of $x$'s differs from the number of $y$'s (e.g., $xxy \in L(\text{II, III})$ but $xxy \notin L$).
Since $L$ requires the count of $x$'s and $y$'s to be equal and non-regular, only the recursive grammar in Definition I generates the correct language.

Context-free languages (CFLs) are closed under union because one can construct a new grammar with $S \rightarrow S_1 \mid S_2$ to generate $L_1 \cup L_2$.
They are also closed under Kleene closure, as adding the production $S \rightarrow S S \mid \epsilon$ to the existing grammar for $L$ generates $L^*$.
However, CFLs are not closed under intersection; for example, the intersection of $L_1 = \{a^n b^n c^m\}$ and $L_2 = \{a^m b^n c^n\}$ is $\{a^n b^n c^n\}$, which is famously non-context-free.
Consequently, by De Morgan's Law, $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$, since CFLs are not closed under intersection, they cannot be closed under complementation.

[CORRECT_OPTION: A, D]

Regular languages are closed under Union, Intersection, Concatenation, and Complementation.
Context-free languages (CFLs) are closed under Union and Concatenation, but are NOT closed under Intersection or Complementation.
Since both language families are closed under Union ($L_1 \cup L_2$) and Concatenation ($L_1 L_2$), these are the shared operations.
Intersection ($L_1 \cap L_2$) and Complementation ($\overline{L}$) fail closure for CFLs, making them invalid as shared properties.
Therefore, both language classes satisfy closure exclusively under Union and Concatenation.
[CORRECT_OPTION: A, C]