1.7k views

Consider the languages:

$L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$  and $L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$

Which one of the following statements is FALSE?

1. $L_1 \cap L_2$ is a context-free language

2. $L_1 \cup L_2$ is a context-free language

3. $L_1 \text{ and } L_2$ are context-free languages

4. $L_1 \cap L_2$ is a context sensitive language

$L_1$ is CFL   [ put $a$'s in stack , and pop $a$ with each $b$]]

$L_2$ is CFL   [put $b$'s in stack and pop $b$ with each $c$ ]

C) is True.

B) is True  CFL is closed under Union    [ $S \rightarrow S_1 \mid S_2$    where $S_1$ is grammar for $L_1$ and $S_2$ for $L_2$]

CFL is not closed under Intersection, so intersection of two CFLs may or may not be CFL. Lets examine:

$L_1 \cap L_2 = \{ a^ib^ic^i , i>0 \}$ which is Context sensitive but not context free [can't match $a$'s,$b$'s and $c$'s with one stack]

So A) is False

D) is True

edited by
0
Both L1 and L2 are DCFL right??

And DCFL are not under union. So how 'b' is true??
0
CFL are always closed under Union [ it doesn't matter they are DCFL or Not ] we can have CFG for Union S-> S1 | S2
0
+9
it means Union of DCFL will not be DCFL [bcoz of S->S1|S2 ]
but it will be CFL [ we have cfg for that]
0
How is it a csl?cn't get how b power n intersection b power m is b power i.plz xplain
0

Intersection is not about bn intersection bm = bi, it is about the string common in L1 and L2.

+2
Can someone explain how  $a^n b^n c^m \cap a^n b^m c^m = a^i b^i c^i.$ with some example.
+7

take the set of stings in both language you will find common only when all are equal
{abc , aabbc , abcccc , aabbcc..........} ∩ {abc , abbcc , aaaabbcc , aabbcc.....}= {abc , aabbcc......}

0
is intersection of any two CFLs CSL? Or is there are CFLs whose intersection is not CSL but recursive or recursively enumerable?
0

Surely L1 U L2 will be a CFL.

L1 U L2 = { ai bj ck | i=j or j=k}

A. CFL's are not closed under intersection.
0

This is not the reason. CFL's are not always closed under intersection,so it may be or may not be. So we can say in general : "CFL's are not closed under intersection". But given 2 particular CFLs you have to check it. For example if it were L1 = L2 = (0+1)^* . Then see both are RL & consequently CFL,also L1 intersection L2 = (0+1)^* which is CFL too. So you cant make the argument that since CFL's are not closed under intersection, then intersection of every 2 CFLs will result in non CFL.

–1 vote
A is false as CFG is not closed under intersection
Option A
reshown