Problem Detail: Let $L = {xyx mid text{ for some }x,y in {0,1}^+}$. Is this language regular? So I was trying to construct a DFA, but I don’t how to do this with this language.
Asked By : user678392
Answered By : Timot
You can indeed use the pumping lemma to answer this. Assume $L$ is regular, and let $p$ be its pumping length. Let $w = 0^p1 cdot 1 cdot 0^p1 in L$. By the pumping lemma (well, a strong form of it), you can pump from the first $p$ letters, and obtain $w’ = 0^{q}1cdot 1 cdot 0^p1$ with $qneq p$, hence $w’notin L$. @Gilles: This came after an even number of cups of coffee :-).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14159
