The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2.1k 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.7k points) | 2.1k views

4 Answers

+25 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.4k 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.
+8

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?
+1

Surely L1 U L2 will be a CFL.

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

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

is  CFL intersectionn CFL = CSL  ????
+5 votes
A. CFL's are not closed under intersection.
answered by Boss (19.9k 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 (7.6k points)
–2 votes
Option A
answered by (433 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

44,298 questions
49,785 answers
164,376 comments
65,857 users