Context Free Language Practice Questions

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=\{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.