MadeEasy Test Series: Theory Of Computation - Identify Class Language

Question

ww^r complement is CSL

Is this right or wrong

If right please how can we prove

Comments

@Praveen Sir can you check this qus.How to find complement ww^r.what will the language after finding complement.

Answer 1

Correct

ww^r is CFL . CFl not  closed under complement so move up to chomsky hirarchy . since every CFL is CSL and Compliment of CSL is CSL.

Comments

But here ww^r is language

Complement is ∑*-(WW^r)

so it be CFL hence CSL too

---

So what Complement never be above CSL .

---

WW^R complement =CFL or not??

Answer 2

$WW^{r}$ complement is either an "odd length string" or "even length string xy such that $x^{r} != y$". Because of 2^nd requirement it is CFL because we can check for all string xy such that $x^{r} != y$