The Gateway to Computer Science Excellence
+19 votes

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

in Theory of Computation by Veteran (52.2k points) | 2.8k views

5 Answers

+28 votes
Best answer

$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.

by Veteran (57k points)
edited by
Both L1 and L2 are DCFL right??

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

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

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.

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......}

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

Surely L1 U L2 will be a CFL.

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

It is asked that which of the following is false...but u r saying that intersection of two languages is context that case option A must be right bro???
how the option D is correct????

is  CFL intersectionn CFL = CSL  ????
Same doubt
+5 votes
A. CFL's are not closed under intersection.
by Boss (19.9k points)

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.

0 votes
Answer Option A]

counter example of A= since m and n can be greater than 0 so it is possible case that they can be equal i.e. m=n in this case we can not  construct pda bcz it is not cfl therefore A is false
by (175 points)
–1 vote
A is false as CFG is not closed under intersection
by Loyal (7.3k points)
–2 votes
Option A
by (443 points)
reshown by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
105,022 users