GATE CSE 2010 | Question: 40

Question

Consider the languages

$L1=\{0^i1^j\ \mid i \neq j\}, $

$L2=\{0^i1^j\mid i=j\},$

$L3=\{0^i1^j \mid i=2j+1\},$

$L4=\{0^i1^j \mid i\neq2j\}$

• A. Only $L2$ is context free.
• B. Only $L2$ and $L3$ are context free.
• C. Only $L1$ and $L2$ are context free.
• D. All are context free

Answer 1

Correct Answer: $D.$ All are context free.
$L1 \rightarrow$ Push $0$ on stack and when $1$ comes, start popping. If stack becomes empty and $1$'s are remaining start pushing $1$. At end of string accept if stack is non- empty.

$L2 \rightarrow$ Do the same as for $L1$, but accept if stack is empty at end of string.

$L3 \rightarrow$ Do, the same as for $L2$, but for each $1$, pop two $0$'s from the stack and don't do a push for the first $0$.

$L4 \rightarrow$ Do the same as for $L1$, but for each $1$, pop two $0$'s from the stack

All are in fact DCFL. Popping two $0$'s on stack might sound non-trivial but we can do this by popping one symbol and going to a new state. Then on this new state on empty symbol, pop one more symbol from the stack and come back to the original state.

Comments

L2 and L3 are DCFL but L1 and L4 are not. Am I Correct?

---

The explanation of L3 is wrong and It got me worked up for a long time. We have to pop 2 0's for each 1 or push one 0 for two 0's. But ya I guess the PDA can be made.

---

@Arjun sir, L4 is not dcfl

if we follow
$L4 \rightarrow\ $ Do the same as for $L1$, but for each $0$, push two $0$'s on stack

$w = 000011\epsilon\ $

before encountering the $1^{st} $, $1$ stack would have $8$, $0's$, and we'll pop $2$, $0's$ for 11,
now next symbol is epsilon and the stack is non-empty i.e, $w$ is accepted but \( w \notin L(L4)\) and is still accepted 

here non-determinism exists hence, $L4$ is $CFL$

Answer 2

The correct answer is D. All are context free.

A language is context-free if it can be recognized by a non-deterministic pushdown automaton (PDA). A PDA uses a stack to "count" or "match" symbols.

Here is the analysis for each language:

• $L2 = \{0^i 1^j \mid i = j\}$: This is the classic example of a context-free language. A PDA can push a symbol onto the stack for every 0 it reads, and then pop one symbol for every 1 it reads. If the stack is empty when the input ends, it accepts.

• $L3 = \{0^i 1^j \mid i = 2j + 1\}$: This is also context-free and even deterministic. A PDA can push all 0s onto the stack. Then, for every 1 it reads, it pops two 0s from the stack. If the input ends and there is exactly one 0 left on the stack, it accepts.

• $L1 = \{0^i 1^j \mid i \ne j\}$: This language is context-free. It is the union of two separate context-free languages:

  1. $i > j$: A non-deterministic PDA can push all 0s, pop one 0 for each 1, and accept if the input ends while the stack is not empty.

  2. $i < j$: A non-deterministic PDA can push all 0s, pop one 0 for each 1, and accept if the stack becomes empty before the input 1s have finished.

     Since $L1$ is the union of these two CFLs, it is also a CFL.

• $L4 = \{0^i 1^j \mid i \ne 2j\}$: This language is also context-free for the same reason as $L1$. It is the union of two CFLs:

  1. $i > 2j$: A PDA pushes all 0s, pops two 0s for each 1, and accepts if the input ends while the stack is not empty.

  2. $i < 2j$: A PDA pushes all 0s, pops two 0s for each 1, and accepts if the stack becomes empty before the input 1s have finished.

     This language is also context-free.

Since $L1$, $L2$, $L3$, and $L4$ are all context-free, the correct statement is D.