I am working on a problem
a) L1={XAB | X,A belongs to (0,1)^+ and B is Reverse of A}
i have to check whether this language is regular or not. I am trying to do it by intuition. The answer is not regular but i am not able to understand why because following language is regular
b) L2={XABY | X,A,Y belongs to (0,1)^+ and B is Reverse of A}
and i understand that this is regular and RE for this is (0+1)*11(0+1)* + (0+1)*00(0+1)*
can someone please explain why L1 is not regular ?
HINT: You can use the pumping lemma for regular languages. Suppose that $L_1$ is regular, and let $p$ be the pumping length. Let $w=0^p110^p$; clearly $w\in L_1$. The pumping lemma says that $w$ can be decomposed as $w=xyz$, where $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L_1$ for each $k\ge 0$.
We don’t know exactly what $x,y$, and $z$ are, but since $|xy|\le p$, we know that $x=0^r$ for some $r\ge 0$, and $y=0^s$ for some $s\ge 1$. Thus, $z=0^{p-r-s}110^p$. Now use this information to describe $xy^kz$, and show that in fact $xy^kz$ is not in $L_1$ when $k\ne 1$. Thus, $L_1$ cannot be regular.