Question

For a string w, we define $w^R$ to be the reverse of w. For example,if w=01101 then $w^R$=10110. Which of the following languages is/are context-free?

Answer 1

Option (a) : $\{wx{w}^R{x}^R|w,xϵ{\{0,1\}}^{\ast }\}$
By putting w as "$ϵ$" we will get {$x{x}^R|xϵ${0,1}$\ast$} which still has string matching. So,this will not be regular. Similary,by putting x as $ϵ$ it will be {w$w^Rϵ$ {0,1}$\ast$} which still has string matching and will not become regular.
So,we need to do string matching but alternate order string matching is not possible in PDA. So,it is a CSL.Option (a) is a CSL but not CFL.
Option (b) L: $\{wx{w}^R|w,xϵ{\{0,1\}}^{\ast }\}$
By putting w as "$ϵ$" we get $x|xϵ$ {0,1}$\ast$}=$(0+1{)}^{\ast }$
Since a subset of L is $(0,1{)}^{\ast }$. L itself must be $(0,1{)}^{\ast }$ which is regular and hence CFL.
Option (b) is a CFL.
Option (c) : $\{w{w}^{R}xxR|w,xϵ{\{0,1\}}^{\ast }\}$
Here by putting x or w as $ϵ$,we cannot remove string matching, So,it is not regular. But it is CFL since in a NPDA we can push w, pop for $w^R$ match it and then push x and pop for $x^R$ and match it again and so this language is a CFL.
option (d) : $\{wxx{w}^R{w}^R|w,xϵ{\{0,1\}}^{\ast }\}$
Here,also by putting w or x as $ϵ$,we cannot make it regular. NPDA can do this,push both w and x and then $x^R$ pop and $w^R$ pop and match. By push, push, pop, pop this can be accepted by NPDA. So,option (d) is CFL.