General

Question

Let L ={wxw^R / w € (a+b)* , x€(a+b)} . The complement of language L is_______

(a) Regular

(b) DCFL but not regular

(c) CFL but not DCFL

(d) None of these

Answer 1

Since, the given language is a CFL and complement of CFL is CSL . so answer is D

Comments

its because we have no surity for the language to be cfl or not. but we can easily say its csl because csl is closed under complement as cfl is a strict subset of csl.

---

If option are given like

1. Cfl but not dcfl
2. Csl but not CFL.

Then what to do????

 

---

here the language L is an odd palindrome with two symbols. so its a cfl and not dcfl. because we cannot fix the centre here.

on complementing we are not sure that we will get a cfl only.

so its csl.

answer 2 in this case.

Answer 2

It should be D) either it will be csl or recursive

Comments

ans is C option is correct . because closure property satisfy mean  it always hold.

if not satisfy than depend on the particular case.

for this question we know that language is CFL means PDA possible.

than we can also make PDA for complement of this language same asa the Language but do some modification at tha final stage .

so complement of this language is CFL.(don't use closure property first go by own way like try to make PDA)

---

i think DCFL is closed under complement but NDCFL is not.above example is NDCFL.can you show your pda for above example

---

How can we say that pda for the complement of the language is a PDA.

i think its ambiguous to say that it will be a PDA because it will have

1)wxw

2)ww

3)wwR

and i dont think we can make a pda that will satisfy the three property..