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

I. A context-free language ($L_1$) is a subset of recursive languages. Since recursive languages are closed under complementation, the complement $\bar{L_{1}}$ is also recursive. This statement is true.
IV. As established, $\bar{L_{1}}$ is recursive, which implies it is also recursively enumerable (RE). The language $L_2$ is given as RE. The set of RE languages is closed under the union operation. Therefore, $\bar{L_{1}} \cup L_{2}$ is necessarily recursively enumerable. This statement is also true.
Statements II and III are not necessarily true.

A language is context-free if it can be recognized by a pushdown automaton (PDA).

• For $L_3 = \{a^m b^n | m=2n+1\}$, a PDA can be constructed. For each 'a' read, it can push two symbols onto the stack, and for each 'b' read, it can pop one symbol. An initial 'a' can handle the "+1".
• For $L_1 = \{a^m b^n a^n b^m | m,n \ge 1\}$, a PDA can be constructed to recognize it. It can push the initial $a^m b^n$ string and then pop symbols to match the subsequent $a^n b^m$ part.
• $L_2$ is not context-free as it requires matching two independent counts, which cannot be done with a single stack.

A language is a Deterministic Context-Free Language (DCFL) if it can be recognized by a Deterministic Pushdown Automaton (DPDA).

For $L_1 = \{0^n1^n | n \ge 0\}$, a DPDA can push '0's onto the stack and then pop '0's for each '1' encountered. The transition is deterministic as it changes states based on the input symbol from '0's to '1's. Thus, $L_1$ is a DCFL.

For $L_2 = \{wcw^r | w \in \{0,1\}^*\}$, a DPDA can push 'w' onto the stack until 'c' is read. After 'c', it deterministically matches the input $w^r$ with the string on the stack. The 'c' acts as a clear marker, making the transitions deterministic. Thus, $L_2$ is a DCFL.

For $L_3 = \{ww^r | w \in \{0,1\}^*\}$, there is no central marker to deterministically identify the middle of the string 'w'. A DPDA would need to guess the middle of the string to push 'w' and then pop for 'w^r'. This non-deterministic guessing makes $L_3$ a Context-Free Language (CFL) but not a DCFL.

Therefore, only $L_1$ and $L_2$ are deterministic Context-Free languages.

Let's analyze each statement:

1. $L_1 = \{0^p1^q0^r | p,q,r \ge 0\}$ is a regular language. It can be written as $0^*1^*0^*$. The complement of a regular language is always regular, and thus also context-free. So, $L_1^C$ is regular and context-free.
2. $L_2 = \{0^p1^q0^r | p,q,r \ge 0, p \ne r\}$: This is a context-free language. A pushdown automaton can count 'p' and compare it with 'r' to ensure $p \neq r$. So, statement A is TRUE.
3. $L_1 \cap L_2$: Since $L_1 = 0^*1^*0^*$ and $L_2 = \{0^p1^q0^r | p,q,r \ge 0, p \ne r\}$, their intersection is simply $L_2$. Since $L_2$ is context-free, $L_1 \cap L_2$ is context-free. So, statement B is TRUE.
4. The complement of a context-free language is generally not context-free, but it is always recursive. Since $L_2$ is context-free, its complement $L_2^C$ is recursive. So, statement C is TRUE.
5. Complement of $L_1$: As established, $L_1$ is regular, so its complement $L_1^C$ is also regular. A regular language is always context-free. Therefore, the statement "Complement of $L_1$ is context-free but not regular" is FALSE because $L_1^C$ is regular.

Let's analyze each language and the statements:

1. L1 = $\{0^p1^q | p,q \in N\}$: This language accepts any number of $0$s followed by any number of $1$s. It can be represented by the regular expression $0^*1^*$. Since it can be represented by a regular expression, it is a regular language. Regular languages can be recognized by Finite Automata (FA) and therefore also by Pushdown Automata (PDA) and Turing Machines (TM).

2. L2 = $\{0^p1^q | p,q \in N \text{ and } p=q\}$: This simplifies to $\{0^n1^n | n \in N\}$. This is a classic example of a context-free language that is not regular. It can be recognized by a Pushdown Automaton (PDA).

3. L3 = $\{0^p1^q0^r | p,q,r \in N \text{ and } p=q=r\}$: This simplifies to $\{0^n1^n0^n | n \in N\}$. This is a classic example of a context-sensitive language that is not context-free. It can be recognized by a Linear Bounded Automaton (LBA) or a Turing Machine (TM), but not by a PDA.

Now let's evaluate the options:

• A. Push Down Automata (PDA) can be used to recognize L1 and L2: L1 is regular (and thus context-free), and L2 is context-free. PDAs can recognize context-free languages. This statement is TRUE.
• B. L1 is a regular language: As analyzed above, L1 can be represented by $0^*1^*$, which is a regular expression. Thus, L1 is a regular language. This statement is TRUE.
• C. All the three languages are context free: L1 and L2 are context-free. However, L3 = $\{0^n1^n0^n\}$ is a context-sensitive language and not context-free. Therefore, this statement is FALSE.
• D. Turing machines can be used to recognize all the languages: Turing Machines are the most powerful model of computation and can recognize all recursively enumerable languages, which include regular, context-free, and context-sensitive languages. This statement is TRUE.

The question asks for the statement that is NOT TRUE.

A language is context-free (CFL) if it can be accepted by a Pushdown Automaton (PDA). Let's analyze each language:

• $L2 = \{0^i1^j \| \; i=j\}$: This is a classic example of a CFL. A PDA can push a symbol onto the stack for each '0' it reads. Then, for each '1' it reads, it pops a symbol. If the stack is empty exactly when the input string ends, the string is accepted. Thus, L2 is context-free.

• $L3 = \{0^i1^j \| \; i=2j+1\}$: This language also involves comparing counts, which a PDA can handle. A PDA can push a symbol for each '0'. Then, for each '1', it can pop two symbols. After reading all '1's, if there is exactly one symbol remaining on the stack, the condition $i=2j+1$ is met, and the string is accepted. Thus, L3 is context-free.

• $L1 = \{0^i1^j \| \; i \neq j\}$: This language is the union of two other languages: $L_{i>j} = \{0^i1^j \| \; i>j\}$ and $L_{i<j} = \{0^i1^j \| \; i<j\}$.

  • For $L_{i>j}$, a PDA can push for '0's and pop for '1's. It accepts if the input ends and the stack is not empty.
  • For $L_{i<j}$, a PDA can push for '0's and pop for '1's. It accepts if the stack becomes empty but there are still '1's left in the input.
    Both $L_{i>j}$ and $L_{i<j}$ are context-free. Since CFLs are closed under union, L1 is also context-free. A PDA for L1 would non-deterministically guess whether $i>j$ or $i<j$ and follow the appropriate logic.

• $L4 = \{0^i1^j \| \; i \neq 2j\}$: Similar to L1, this language is the union of $L_{i>2j}$ and $L_{i<2j}$. A PDA can handle the $i=2j$ comparison (as shown for L3). By slightly modifying the acceptance condition (accepting if the stack is not empty when it should be, or vice-versa), we can create PDAs for both $i>2j$ and $i<2j$. Since L4 is the union of these two CFLs, L4 is also context-free.

Since all four languages are context-free, the statement 'All are context free' is true.

To determine $L = L_1 \cap L_2$, we examine the constraints imposed by both languages.

1. $L_1 = \{a^m b^m c a^n b^n \mid m,n\geq 0 \}$
2. $L_2 = \{a^i b^j c^k \mid i,j,k\geq 0 \}$

For a string $w$ to be in $L_1 \cap L_2$, it must satisfy the structure of both languages.
From $L_2$, a string must be of the form $a^i b^j c^k$, meaning all 'a's come first, followed by all 'b's, followed by all 'c's.
From $L_1$, a string is of the form $a^m b^m c a^n b^n$.
For $a^m b^m c a^n b^n$ to match the $a^i b^j c^k$ form, the $a^n b^n$ part must be empty. If $n>0$, there would be 'a's and 'b's after 'c', which is not allowed by $L_2$.
Therefore, we must have $n=0$. This simplifies the form of strings from $L_1$ to $a^m b^m c$.

Now, let's verify if $w = a^m b^m c$ is in $L_2$.
If $w = a^m b^m c$, then it matches $a^i b^j c^k$ with $i=m$, $j=m$, and $k=1$. This is valid for all $m \geq 0$.
So, $L = \{a^m b^m c \mid m \geq 0 \}$.

Now we classify $L$:

• $L$ is not Regular: This language requires comparing the count of 'a's to the count of 'b's before a 'c', which cannot be done by a finite automaton (by the Pumping Lemma for Regular Languages).
• $L$ is Context-Free: This language can be generated by a Context-Free Grammar (CFG) such as $S \to Xc$, $X \to aXb \mid \epsilon$, or recognized by a Pushdown Automaton (PDA).
• All Context-Free languages are Recursive.

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

The language $L = \{ a^p \mid p \text{ is a prime} \}$ is not regular because the Pumping Lemma for regular languages fails; an arithmetic progression $p + ki$ cannot consist solely of prime numbers for all $i \ge 0$. Similarly, $L$ is not context-free because the Pumping Lemma for context-free languages demonstrates that pumping a string of length $p$ results in lengths that eventually form composite numbers. However, $L$ is decidable; a Turing machine can count the number of $a$'s in the input string and execute a primality test algorithm to determine if the length is prime. Consequently, the language is accepted by a Turing machine but is neither regular nor context-free.

$L_1 = \{a^i b^i c^k \mid i \geq 0, k \geq 1\}$ is a non-regular context-free language because it requires a stack to match the count of $a$'s and $b$'s. Similarly, $L_2 = \{a^i b^{2i} \mid i \geq 0\}$ is a context-free language.

To determine the intersection $L_1 \cap L_2$, a string must satisfy $i=j$ (from $L_1$) and $j=2i$ (from $L_2$). This implies $i=2i$, so $i=j=0$. For $i=0$, the string in $L_1$ is $c^k$ ($k \geq 1$), but $L_2$ contains only strings consisting of $a$'s and $b$'s (e.g., $\epsilon, abb$). Thus, $L_1 \cap L_2 = \varnothing$. Since $L_1$ is non-regular and the intersection is empty, Option B is true.

For $G1$, the grammar is $S \rightarrow x \mid z \mid xS \mid zS \mid yB$ and $B \rightarrow y \mid z \mid yB \mid zB$. The strings generated are of the form $(x \mid z)^* (y(y \mid z)^* )?$. Once the transition to $B$ occurs via a $y$, only $y$'s and $z$'s can be produced, meaning no $x$ can appear after a $y$. Thus, no $y$ appears before any $x$.

For $G2$, the grammar is $S \rightarrow y \mid z \mid yS \mid zS \mid xB$ and $B \rightarrow y \mid yS$. Any $x$ is introduced exclusively through the production $xB$, and $B$ must produce a $y$ immediately. Therefore, every $x$ is followed by at least one $y$.

These properties correspond to:

1. $G1$: No $y$ appears before any $x$
2. $G2$: Every $x$ is followed by at least one $y$

The language $L=\{0^{i}21^{i}|i\geq 0\}$ is a Context-Free Language (CFL) because it can be generated by the CFG: $S \to 0S1 | 2$. This grammar clearly matches the count of $0$s and $1$s separated by a '2'.

It is a Deterministic Context-Free Language (DCFL) because a Deterministic Pushdown Automaton (DPDA) can recognize it:

1. Push each '0' onto the stack.
2. Upon reading '2', change state.
3. For each '1', pop a '0' from the stack.
4. Accept if the stack is empty when the input ends.
   This DPDA is deterministic as there is no ambiguity in transitions for any input symbol.

Since all CFLs are recursive, and DCFLs are a subset of CFLs, $L$ is also recursive. Therefore, it is both recursive and a deterministic CFL.

Let $L$ be a context-free language recognized by a pushdown automaton (PDA) $P = (Q_P, \Sigma, \Gamma, \delta_P, q_0, Z_0, F_P)$, and let $M$ be a regular language recognized by a deterministic finite automaton (DFA) $D = (Q_D, \Sigma, \delta_D, q'_0, F_D)$.
We can construct a product PDA $P' = (Q_P \times Q_D, \Sigma, \Gamma, \delta', (q_0, q'_0), Z_0, F_P \times F_D)$ that tracks the states of both automata simultaneously.
The transition function $\delta'$ is defined such that for any state $(q, p) \in Q_P \times Q_D$ and input $a \in \Sigma \cup \{\epsilon\}$, $P'$ performs the transition dictated by $P$ while updating the state in $D$ according to $\delta_D(p, a)$ if $a \in \Sigma$, or keeping $p$ unchanged if $a = \epsilon$.
Since this product machine $P'$ is a PDA, it accepts the intersection of the two languages.
Therefore, $L \cap M$ is recognized by a PDA and is thus a context-free language.

Language $L_{1}=\{0^{n+m}1^{n}0^{m}\}$ is context-free, generated by the grammar $S \to 0S0 \mid A$ and $A \to 0A1 \mid \epsilon$, which constructs the string as $0^m(0^n 1^n)0^m$.
Language $L_{2}=\{0^{n+m}1^{n+m}0^{m} \mid n,m \ge 0\}$ is not context-free because a PDA matching $0^{n+m}$ with $1^{n+m}$ clears its stack, leaving no way to compare $m$ with the previous $n+m$ count.
Language $L_{3}=\{0^{n+m}1^{n+m}0^{n+m} \mid n,m \ge 0\}$ is equivalent to $\{0^k 1^k 0^k \mid k \ge 0\}$, a classic non-context-free language requiring comparisons across three dependent groups.
Since Pushdown Automata cannot track multiple independent dependencies or compare overlapping counts simultaneously, both $L_{2}$ and $L_{3}$ are not context-free.
Therefore, the correct classification is that $L_{2}$ and $L_{3}$ are not context-free.

Both $L_1$ and $L_2$ are context-free languages (CFLs) because they can be generated by simple context-free grammars, making Option C true. The union of two CFLs ($L_1 \cup L_2$) is also a CFL, making Option B true. The intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n > 0\}$, which is a well-known non-context-free language; is FALSE. Since $\{a^n b^n c^n \mid n > 0\}$ is a context-sensitive language, Option D is true.

Given that $L$ is a regular language and $M$ is a context-free language, their intersection $K = L \cap M$ is always a context-free language. By De Morgan's Law, the union of their complements is $L^c \cup M^c = (L \cap M)^c = K^c$. Since the complement of a context-free language is not necessarily context-free, statement B is false. Furthermore, $K^c$ is not necessarily non-regular (if $K = \Sigma^*$, $K^c = \emptyset$, which is regular), making C false, and not necessarily regular (if $K = \{a^n b^n \mid n \ge 0\}$, $K^c$ is not context-free), making A false. Because none of the statements are universally true, the correct answer is D.

$L_{1}=\{ww^{R}|w\in \{0,1\}*\}$ is a non-deterministic CFL because a PDA cannot determine the midpoint of the string without non-deterministically guessing where $w$ ends. $L_{2}=\{w\#w^{R}|w\in \{0,1\}*\}$ is a deterministic CFL because the marker $\#$ explicitly identifies the midpoint, allowing a deterministic PDA to push $w$ onto the stack and compare it with the remaining input after encountering $\#$. $L_{3}=\{ww|w\in \{0,1\}*\}$ is not a CFL, as it can be proven using the Pumping Lemma for context-free languages. Therefore, $L_{2}$ is the only deterministic CFL among the choices.

The language $L = \{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ consists of a finite number of strings because the exponent $n$ is bounded by a constant ($10^6$). In formal language theory, any language that contains a finite number of strings is classified as a finite language. All finite languages are regular because a Deterministic Finite Automaton (DFA) can be constructed to accept the finite set of strings by explicitly representing the path for each valid string in the set. Since $L$ is finite, it satisfies the criteria for a regular language.

The language $L = \{a^m b^n c^{m+n} \mid m,n \geq 1\}$ can be generated by the context-free grammar with productions $S \rightarrow aSc \mid X$ and $X \rightarrow bXc \mid bc$. This grammar derives strings of the form $a^m X c^m$, where $X$ generates $b^n c^n$, resulting in $a^m b^n c^n c^m = a^m b^n c^{m+n}$. Since a context-free grammar exists, the language is context-free. It is not regular because a finite automaton lacks the memory to track two independent counts ($m$ and $n$) required to ensure the total number of $c$'s matches the sum $m+n$. Thus, the language is context-free but not regular.

A language $L$ that can be effectively enumerated in lexicographic order allows for a decision procedure to determine if any string $w \in \Sigma^*$ belongs to $L$. By enumerating strings of $L$ in lexicographic order, we compare each against $w$; if we reach a string lexicographically greater than $w$ without finding $w$, we conclude $w \notin L$. Since membership is decidable, $L$ is recursive. Recursive languages are not restricted to the regular or context-free classes, as demonstrated by non-context-free languages like $L = \{a^n b^n c^n \mid n \geq 0\}$. Therefore, $L$ is necessarily recursive but not necessarily context-free.

The Chomsky Hierarchy categorizes languages based on their grammatical complexity. While portions of C syntax appear to be context-free, the language requires complex semantic validation-such as type checking and ensuring identifiers are declared before use-which exceed the capabilities of Context-Free Grammars ($Type 2$). These specific requirements depend on the surrounding context within the source code. Consequently, C is formally classified as a Context-Sensitive Language ($Type 1$), distinguishing it from simpler Regular ($Type 3$) or Context-Free languages.