Question

Consider the following language

$I.\{w^R{x}^R{w}^R{y}^R|w,x,y\in (0,1{)}^{\ast }\}$
$II.\{xw{x}^R|w,x\in (0,1{)}^{\ast }\}$
$III.\{w,x^{R}w{y}^R|w,x,y\in (0,1{)}^{\ast }\}$
$IV.\{w{x}^R{w}^{R}x|w,x,y\in (0,1{)}^{\ast }\}$

Which languages above are regular ?

Answer 1

$I,II,III\to \text{regular}$
$IV\to \text{not regular}$
Try to avoid string matching by putting $w\text{as}\in$ and make $x\text{and}y\text{go to}(0+1).$ Therefore we're shown that the subset itself is ${\sum }^{\ast }$ and thus 1 is regular.

Similary For II we can put $x\text{as}\in$ and then put $w\text{as}(0+1{)}^{\ast }.$
Therefore II is also regular.

Now in III, put $w\text{as}\in$ and make $x^R\text{and}{y}^R$ goto ${\sum }^{\ast }$ (note that between $x\text{and}y$ there's no string matching ). So III is also regular.

But IV is not regular let 's see why.
Try getting rid if string matching by putting $w\text{as}\in$.
So it we start all over again by putting $x\text{as}\in$, we are again $w{w}^R$, another string matching. So we cannot got rid of string matching at all here, as even it both $w$ and $x$ are made $\in$ the subset is $\in$, but this proves nothing only says that a subset of thus language is regular, but that doesn't say anything at all about the language itself.
So $IV$ is not regular