regular and CFL language

Question

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.

Comments

a,b,d are true?

A) Intersection of a CFL and regular is a CFL -True

B) Follows CFL's closure propety - True

C) consider non-CFL to be a^nb^nc^n and CFL to be a^nb^n ..  intersection of this is CFL

D) considering the similar example above and others too .. I guess this is true as well

---

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

---

Ah yes, didn't consider an example like that for D. You're right.

Answer 1

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.

 

Answer 2

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