doubt toc

Question

wxw ;w,x belongs to {a,b}^*

this regular or dcfl or cfl??? somewhere it is written as regular but dontknow why??

Comments

I think since w,x both belongs to {a,b}*, x can take upto the entire string leaving w with epsilon.

so any string can be like (epsilon)(a,b)*(epsilon). hence it is Regular.

---

yes it is regular. x can take up whole string then language will become start and end with same symbol.

---

no it is not the case of starting and ending with same symbol

---

ya i haven't checked correctly i thought it was +. so for this it will be (a+b)*.

Answer 1

Yes, the language is regular because

wxw = x only when w, x belong to {a,b}^*

Hence the language is (a+b)^* which is regular

Answer 2

R.E for above language=$a(a+b)^{*}a +b(a+b)^{*}b$ .so it is regular language.

Answer 3

Yes, the language is regular because you can eliminate the dependency between two w's by substituting epsilon in place of w. Once the dependency is over the language becomes regular.

Now, since language is regular it is also CFL & DCFL.

Comments

Isn't that just one case? w being replaced with ε. Also can you tell more about dependency?

---

yes it is the only reason (by maing w as epsilon ) , we can make

$L=\left \{ wxw | w,x \,\,\epsilon (a+b)^{*} \right \}$ as regular because making $w$ as $\epsilon $  our

$L$ will be nothing but $(a+b)^{*}$

if we try to make $w$ as any other string other than $\epsilon$ ,then we need to keep track of that string which will need a stack.

---

Thanks @Anand.