1,966 views
4 votes
4 votes
Let A and B be two languages over alphabet  ∑ . which of the following are true ?  (more than one options may be correct)

(a) if A is regular and B is CFL then A∩B is also CFL.

(b) if A is regular and B is CFL then A∪B is also CFL.

(c) if A is not CFL  and B is CFL then A∩B will not be a CFL.

(d) if A is not CFL  and B is CFL then A∪B will not be a CFL.

2 Answers

1 votes
1 votes

1. True

A trivial example is that A∗ is regular, and if L is context-free but not regular then

 L∩A∗=L

is context-free but not regular.

So L ∩A is CFL.

https://cs.stackexchange.com/questions/18642/intersection-of-context-free-with-regular-languages

2. True. We cannot get non cfl by this intersection.

3. Neednt be non cfl. Phi intersection any non cfl = phi, which is CFL.

4. False.

Phi union non cfl is phi which is CFL.

 

0 votes
0 votes
For D:-

 if A is not CFL  and B is CFL then A∪B will not be a CFL.

A= $a^nb^nc^n$:- Its not CFL

B= Sigma*

A union B=Sigma* which is regular hence CFL

So it can be CFL

For C:-

A= $a^nb^nc^n$ :- Its not CFL

B= phi

A intersection B is phi,which is regular hence CFL,

These are just counter examples to prove c and d are false.

A and b are true

Related questions

5 votes
5 votes
1 answer
1
Parshu gate asked Nov 16, 2017
671 views
Let L={ai bj ck ┤|if j is odd then i=k} where i,j,k>0. Which of the following option is true about L? L is CSL but not CFL L is CFL but not DCFL L is regular L is D...
1 votes
1 votes
1 answer
2
0 votes
0 votes
0 answers
3
saptarshiDey asked Jan 22, 2019
525 views
L = {a^(p+q) b^(p+q) a^p , p,q>=0}Which one of the following is true about L?L is a regularL is CFL but not regularL is not a CFL
1 votes
1 votes
1 answer
4