Language classification

Question

XWW  AND XWW^R    where X (0+1)*  AND W (0+1)*   are  what kind of languages  also in case of + instead of *  ?

Comments

In case of *  1)xww will be regular 2)xww^r will be regular.

In case of + 1)xww will be csl 2)xww^r will be cfl

Answer 1

Considering (a+b)*:

L = xww is regular. Since, w can be ϵ and x∈(a+b)∗, making L=Σ∗. i.e.; the set of strings generated by L is {ϵ,a,b,aa,ab,ba,bb,aaa,…}=Σ∗

L = xww^R is also regular.

Considering (a+b)+:

L = xww is CSL. Since x∈(a+b)+ , w cant be ϵ , so string comparison is required.

L = xww^R is NCFL.