retagged by
1,608 views
4 votes
4 votes
Problem :- intersection of 2 CFL's is CFL. Is this decidable ?
retagged by

3 Answers

1 votes
1 votes

Intersection of two CFL's is CFL is undecideable.

Lets take example suppose we have 2 CFL 

L1=( a^n b^n c^m |m,n0)

L2=(a^m b^m c^n |m,n0)

Then L1 L2

L3=(a^n b^n c^n |m,n0) is csl

But

L1=( a^m b^m c^n |m,n0)

L2=(a^m b^n c^n |m,n0)

L3=(a^p b^q c^r |m,n0)

Is cfl

 

so sometimes it may be cfl or sometimes it may be non cfl

hence we can say that intersection of two cfl is cfl is undecideable.

0 votes
0 votes
1.it is not decidable because intersection of two CFL need to be CFL

2.In intersection operation you can get 'fi'(Ø) which is regular so u can say that it is undecidable
0 votes
0 votes
DCFL and Non-deterministic CFL both are not closed under intersection, and thus makes the problem undecidable.

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
1 answer
2
learner_geek asked Aug 15, 2017
1,375 views
Is complement of language same type or not decidable by CFL and recursive language or not???Grammar is ambiguous or not?Grammar in regular/CFL/rel decidable or not?
3 votes
3 votes
0 answers
3
Nymeria asked Jan 10, 2018
826 views
a) L is decidableb) L is undecidablec) L is regulard) None of these
3 votes
3 votes
2 answers
4
amrendra pal asked Aug 22, 2017
1,020 views
C = { <G,k | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be-a) decidableb) Turing unrecognizablec) Recursive enumerabled) undecidab...