The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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

asked in Theory of Computation by Veteran (69k points) | 1.6k views

4 Answers

+24 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 

answered by Veteran (55.2k points)
edited ago 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}

+5 votes
A. CFL's are not closed under intersection.
answered by Veteran (19.8k 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.

–1 vote
A is false as CFG is not closed under intersection
answered by Boss (7.8k points)
–2 votes
Option A
answered by (479 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

33,646 questions
40,193 answers
38,664 users