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

asked in Theory of Computation by Veteran (59.4k points) | 1.7k 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 (54.5k points)
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}

+5 votes
A. CFL's are not closed under intersection.
answered by Boss (19.7k points)
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
answered by Loyal (7k points)
–2 votes
Option A
answered by (415 points)
reshown by
Answer:

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

35,506 questions
42,827 answers
121,678 comments
42,181 users