GATE CSE 2017 | Set 1 | Question: 38

Question

Consider the following languages over the alphabet $\Sigma = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}\mid m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}\mid m,n \geq 0 \right \}$.

Which of the following are context-free languages?

1. $L_{1} \cup L_{2}$
2. $L_{1} \cap L_{2}$

• A. I only
• B. II only
• C. I and II
• D. Neither I nor II

Comments

@tusharb You can use closure property to say “yes” – so first part is correct. But using it to say “no” is wrong as it depends on the given instance. Intersection of 2 CFLs can give another CFL.

---

Arjun sir yes I totally didn’t think about that case, thanks for the heads up

---

The intersection of the languages $L^1$ and $L^2$ is the set of strings that belong to both languages.
$L^1$ must have an equal number of 'a's and 'b's.
$L^2$must have an equal number of 'b's and 'c's.

$L^1\cap L^2$, it must satisfy both conditions simultaneously.  number of 'a's must equal the number of 'b's, which must also equal the number of 'c's.

Answer 1

Correct Option: A

1. Here, let's say $L= L_1 \cup L_2$. 
   Here as we see , $L_1$ and $L_2$ both are DCFLs. And hence CFLs.
   And from the Closure Properties of CFLs, we can conclude that CFLs are Closed under Union Operation.
   And hence, $L= L_1 \cup L_2$ is CFL. 
    
2. Now, let's take $L=L_1 \cap L_2$, and that can be expressed as,
   $L=\{a^ib^jc^k  \mid i=j \textsf{ AND }  j=k, i,j,k \geq 0\}$, in other words
   $L=\{a^nb^nc^n  \mid  n\geq 0\}$ 
   And we know that it comes under CSL (As we will require Two Stacks at a Time). So $L$ is CSL and also NOT a CFL.

Comments

Ok @Shaik Masthan sir got it.

Thanks.

---

NOTE: 

i)If we can construct a Context-Free Grammar (CFG) for a language, then that language is Context-Free (CFL) by definition.

ii) CFL U CFL == CFL

Now lets verify:
--------------------------------------------------------------------------------------------------------------------------------------------

CFG for Language \( L_1 \)

Language \( L_1 = \{ a^n b^n c^* \} \):

CFG for \( L_1 \): This language consists of strings with an equal number of \( a \)'s and \( b \)'s followed by any number of \( c \)'s.
\[
S \to AB \ 
\]
\[
A \to aAb \ \mid \ \epsilon
\]
\[
B \to cB \ \mid \ \epsilon
\]

CFG for Language \( L_2 \)

Language \( L_2 = \{ a^* b^n c^n \} \):  

This language consists of strings with any number of \( a \)'s followed by an equal number of \( b \)'s and \( c \)'s.

CFG for \( L_2 \)
\[
S \to AS' \ 
\]
\[
A \to aA \ \mid \ \epsilon
\]
\[
S' \to bS'c \ \mid \ \epsilon
\]

Here CFG ↔ CFL Equivalence exists.
 
Ans 'A'

---

both L1 and L2 are CFL so you intersection operation between CFL languages is not closed.

Answer 2

L1 requires only one comparison and can be implemented by single stack Clearly it is CFL

(push A's when B comes POP A's ..C comes pass...if stack is empty at end of string than ACCEPT)

L2 also is CFL because of same reason mentioned above

(same algorithm can be used just change of alphabets)

Now since CFLs are CLOSED under UNION but NOT CLOSED under INTERSECTION

hence only

OPTION (A) is CORRECT

Comments

Then how do you justify this?

L1={a^n b^n∣n>0} is a CFL, L2={b^n a^n∣n>0} is a CFL and L1∩L2=ϕL1∩L2=ϕ is also a CFL.

---

this is wrong approach for L2.

---

nt a correct explanation ...

Answer 3

Strings in L1 = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
Strings in L2 = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L1 ∪ L2 ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L1 ∪ L2) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L1 ∪ L2) is CFL.
Strings in L1 ∩ L2 = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L1 ∩ L2) will have (number of a’s = number of b’s = number of c’s)
i.e., (L1 ∩ L2) = {anbncn | n ≥ 0} which is CSL.

Answer 4

Since question is asked for this 2 particular Grammar so for UNION operation closure property will hold by default but we can not say about INTERSECTION.

Strings in L1 = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
Strings in L2 = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L1 ∪ L2 ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L1 ∪ L2) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s). which is accepted by N-PDA so CFG.

Strings in L1 ∩ L2 = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L1 ∩ L2) will have (number of a’s = number of b’s = number of c’s)

which can not be accepted by PDA so not CFG

Comments

who crossed this answer? what is wrong here?

Answer 5

Union and Intersection NPDA

 

L1 and L2 with NPDA and l1 union l2

Answer 6

The L1 is deterministic CFL  with final state accepted by both empty stack and final state. 

L2 is deterministic CFL with final state accepted by final state only. 

Union of two CFL is a CFL but intersection of two CFL can/cannot be CFL. Hence option A is correct