Theory of Computation

Question

Please explain, what is the intersection of Context free language and Context Free language

intersection of context free and recursive

intersection of context sensitive and recursive

Answer 1

CFL is not closed under intersection

1)$CFL\cap CFL$ = may or may not be CFL but recursive

2) $CFL\cap Recursive$ = every CFL is recursive and recursive is close under intersection then Recursive.

3) $CSL\cap Recursive$ = every CSL is recursive and recursive is close under intersection then Recursive.

Comments

every CSL is recursive enumerable this is true

but

every CSL is recursive this is open question

---

Source- Peter Linz

Can you give some proof which satisfy your statement?

Answer 2

• Intersection of CFL is not closed under intersection i.e if we intersect two CFL then it may not be CFL . Look at the example

• CFL$\bigcap$ recursive = recursive 

• CFL$\bigcap$ CSL = CSL