edited by
13,496 views
41 votes
41 votes

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}$
  1. I only
  2. II only
  3. I and II
  4. Neither I nor II
edited by

6 Answers

Best answer
53 votes
53 votes

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.
edited by
8 votes
8 votes
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
2 votes
2 votes

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.

0 votes
0 votes
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
Answer:

Related questions

44 votes
44 votes
6 answers
2
Arjun asked Feb 14, 2017
11,481 views
If $G$ is a grammar with productions$S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$where $S$ is the start variable, then which one of the following strings is not g...
74 votes
74 votes
8 answers
3