GATE CSE 2022 | Question: 38

Question

Consider the following languages:

$L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$

$L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$

$L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$

Which of the following statements is/are $\text{FALSE}?$

• A. $L_{1}$ is not context-free but $L_{2}$ and $L_{3}$ are deterministic context-free.
• B. Neither $L_{1}$ nor $L_{2}$ is context-free.
• C. $L_{2}, L_{3}$ and $L_{2} \cap L_{3}$ all are context-free.
• D. Neither $L_{1}$ nor its complement is context-free.

Comments

Similar Question : Theory of Computation: GATE CSE 2020 | Question: 32 (gateoverflow.in)

Useful Comment : https://gateoverflow.in/333199/gate-cse-2020-question-32?show=385717#c385717

Answer 1

Answer : B,C,D

$L_1 :$

$L_1 = \{ww \} | w \in \{a,b \}^*$

$L_1$ is standard example of Non-Context-Free-Language. $L_1$ is very famous language which is Non-CFL, but complement of $L_1 $ is CFL.

We can not have a PDA to recognize language $L_1.$

Informal idea :

Informal idea is that we need to match first half of string with the second half of the string. Assume that the input string is $s= abbab\,abbab$ So, we have to remember the first half of the string, so, we push the first half in the stack(PDA can non-deterministically determine the middle of the string), So, in stack we have $abbab$ in this order with the $a$ on bottom of the stack and the $b$ on the top of the stack. Now, we need to match the second half of the string $s$ with the first half, so, the first symbol of second half of string $s$ must be matched with the first symbol of the first half. But since the first symbol of first half is on Bottom of the stack, we(PDA) cannot do this matching.

Hence, No PDA can recognize the language $L_1.$

Formal Idea :

We can use “Pumping lemma of CFLs” to prove that $L_1$ is Not CFL. The proof of Non-CFLness of $L_1$ by “Pumping lemma of CFLs” is present in the comments of this answer.

But first, For understanding how to use Pumping lemma of CFLs to prove that a language is Non-CFL, refer my answer on the following GATE question :

https://gateoverflow.in/1506/Gate-cse-1999-question-7

The informal idea is clearly much simpler and intuitive.

https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec17.pdf

https://web.iitd.ac.in/~bspanda/pumpinglemmacfl.pdf

https://www.cs.swarthmore.edu/~sindhu/cs46/s16/TM.pdf

---

$L_2 :$

$L_2 = \{ a^nb^nc^m | n,m >=0 \}$ 

$L_2$ is DCFL. The idea for construction of DPDA for $L_2$ is :

Initially on the stack we have $z_0.$ Push all the $a’s$ of the input string on stack, then as soon as first $b$ appears, start popping $a’s$ from the stack (pop one $a$ for one $b$), then when the first $c$ appears, we must have $z_0$ on the top of the stack. If we have $z_0$ on the top of the stack when first $c$ appears in the input string, DPDA goes to final state and consumes all the $c’s$ of the input string, wihout bothering the stack.

$L_3 :$

$L_3 = \{ a^mb^nc^n | n,m >=0 \}$ 

$L_3$ is DCFL. The idea for construction of DPDA for $L_3$ is similar to the DPDA for $L_2$ :

Initially on the stack we have $z_0.$ Read all the $a’s$ of the input string without pushing anything on the stack (basically ignore all the $a’s$), then as soon as first $b$ appears, start pushing $b’s$ on the stack, then when the first $c$ appears, start popping $b’s$ from the stack (pop one $b$ for one $c$). At the end of the string, when we encounter the special “End-of-input” symbol $\$$, we must have $z_0$ on the top of the stack. If we have $z_0$ on the top of the stack when we encounter the special “End-of-input” symbol $\$$ in the input string, DPDA goes to final state.

---

$L = L_2 \cap L_3 = \{ a^nb^nc^n | n >=0 \} $ which is another standard example of Non-Context-Free-Language.(Can be formally proved using Pumping lemma of CFLs BUT the informal idea is much simpler and intuitive)

Informal Idea :

We cannot have a PDA to recognize the language $L$ because any PDA will have to match number of $a’s$ with number of $b’s$, then with number of $c’s.$ BUT as soon as we match number of $a’s$ with number of $b’s$ in the input string, we(PDA) do not have any memory of number of $a’s$ in the input string to match with number of $c’s.$ So, PDA cannot recognize the language $L.$

---

Option 4 :

$L_1$ is standard example of Non-Context-Free-Language. $L_1$ is very famous language which is Non-CFL, but complement of $L_1 $ is CFL.

https://cs.stackexchange.com/questions/19151/is-the-complement-of-ww-context-free
 

Comments

what would be the complement of L1?

---

Let $L = \{ ww \,\, | \,\, w \in \{a,b \}^* \}$

Notice that Every string in $L$ is of Even Length. So, Complement of L i.e. $L’$ will contain every string of Odd length, plus some even length strings which are not of form $ww.$

Let $L_o = \text{Set of all Odd length strings over a,b}$

Hence, $L’  = L_o \bigcup  \,\, \{ XY \,\, | \,\, X,Y \in \{a,b \}^*, |X| = |Y|, X \neq Y \}$

---

@Deepak Poonia $L_1$ is CSL then why is it not closed under complement operation for this example?

why does it’s complement give CFL? please clear my doubt.

---

@Hira Thakur 

Closed in complement means $\bar L_1$ is guaranteed to be CSL. But, does it say anything about not being a CFL? A “CSL” can be a CFL too.

$L_1$ is a CSL but when you complement $L_1$ you get a CFL, which must also be a CSL. Thus, maintaining closure property.

---

@DebRC good explanation as always♥, cleared my doubt too

Answer 2

This language is not CFL but its complement is CFL. It is a Standard language.

So L1 is not Context free language but L1 complement is Context free language.

 

$L2=\left \{ a^{n}b^{n} c^{m}|m,n\geqslant 0\right \}$

L2 is DCFL.

$L2=\left \{ a^{m}b^{n} c^{n}|m,n\geqslant 0\right \}$

L3 is DCFL.

Now come to the options,

Option a is true as it is already explained L1 is not context free and L2 and L3 is Deterministic context free.

Option B is false as it says L2 is not context free but L2 is context free.

Option C is false as $L2\bigcap L3=\left \{ a^{n}b^{n}c^{n} |n>=0\right \}$ which is not CFL as it is CSL.

Option D is false as it says L1 complement is not Context free language but it is context free language. So it is false as well.

https://stackoverflow.com/questions/34245141/is-the-complement-of-any-context-free-language-context-free#:~:text=Regular%20languages%20are%20closed%20under,%E2%88%88%7B0%2C1%7D*%7D%20

So correct answer is B,C,D.