TOC

Question

Consider the language given below .Find the complement of these language and Explain Complementary language?

1.ww^r | w∈(a ,b)*

2.wxw^r| x,w∈(a,b)⁺

3.ww ∣ w∈(a,b)⁺

4.wxw∣ x,w∈(a,b)⁺

Comments

https://gateoverflow.in/278184/me-test-series

Answer 1

..........

Answer 2

1. ∑* - (ww^r)

ww^r ={∊,aa,bb,abba,abbbba..............}

then ∑* - (ww^r) = {a,b,aba,ab,ba,................}

ww^r is Regular. Complement of regular is regular

2.∑* - (wxw^r)

wxw^r=(aaa,aba,abba..........)

then ∑* - (wxw^r) = {a,b,aa,bb...................}

wxw^r is DCFL . DCFL closed under complement. ∑* - (wxw^r) is DCFL

3.∑* - (ww)

ww=(aa,bb,abab............)

∑* - (ww)=(a,b,abba,abaa.............)

ww is CSL. Complement of CSL can be CSL

4.∑* - (wxw)

wxw=(aaa,aba,abaab............)

∑* - (wxw)=(a,b,aa,ab......................)

wxw is CSL. Complement of CSL is also CSL,

Comments

@Praveen sir

ww^r how it is DCFL?

is it not NCFL?

---

^^ Right  , my mistake :(

---

@Praveen Saini Sir

Is $\left ( L_{ww} \right )'$ DCFL or NCFL??

I think it has $S_{odd}$ and $S_{even}$ two paths.

So, it will be NCFL.

right??

Answer 3

I am a bit confused by the answers here.

 

My understanding is as below

1. An Npda is required, hence it is N-CFL. So complement may or may not be CFL. We can say complement is CSL

2. A Dpda is enough so its D-CFL. Complement of a D-CFL is D-CFL

3 and 4 are both CSL so complement is CSL

 

For any of these cases an FSM is not possible as the number of states is not finite. So none of these is Regular.

 

Where am i going wrong pls