Cfl

Question

If L1 is CfL and L2 is CfL then state true or false??
i)L1-L2 is CSL
ii)L1 intersection L2 is CSL..
Iii)L1 - L2 is Recursive
iv)L1(compliment) is CSL

Give the reason

Answer 1

1) true

L1 & L2  both are CFL and we know that...every CFL is also CSL..so L1 & L2  both are CSL

nowL1 - L2  can be written as below

L1 - L2 ====> L1 ∩ L2^C 

and we also know that CSL  is  closed under COMPLEMENT as per https://en.wikipedia.org/wiki/Immerman–Szelepcsényi_theorema.... so we can conclude  L2^C  is  CSL...

and hence L1 - L2 is also  CSL..

2) TRUE

L1 & L2  both are CFL and we know that...every CFL is also CSL..so L1 & L2  both are CSL

now CSL is closed under INTERSECTION operation....

hence .... L1 ∩ L2    is CSL.

3)TRUE

L1 & L2  both are CFL and we know that...every CFL is also RECURSIVE..so L1 & L2  both are RECURSIVE...

L1 - L2 ====> L1 ∩ L2^C 

and RECURSIVE language is closed under both INTERSECTION &  COMPLEMENT..hence L1 - L2 is RECURSIVE

4)true

L1(compliment)  ... is CSL because CSL is  closed as per https://en.wikipedia.org/wiki/Immerman–Szelepcsényi_theoremaunder complemention..

Comments

ohh sry, i didnt see tauhin's answer,

he has marked false...

---

@Tauhin your answer looking nice and with prove.Thats why i select it.

---

thanx manoj

Answer 2

All are correct.

Comments

$L=(L2-L1)\cap (L1-L3)^{C}$

    =$(RE-REC)\cap (REC-R)^{C}$

   =$(RE\cap REC^{C})\cap (REC)^{C}$

   =$(RE\cap REC↑)\cap (REC)$

   =$(RE\cap RE)\cap (REC)$

   =$RE\cap REC↑$

   =$RE\cap RE$

   =$RE$

---

H ow to decide which language to upgrade...is it like type 3 to type0

---

See this

$RE\cap Reg$

Since both language are closed under $\cap$ .As well as every regular language is recursively enumerable.So to get stronger solution  upgrade it.

$RE\cap Reg↑$=$RE\cap RE$=RE