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.
$\begingroup$
$\endgroup$
-
1$\begingroup$ Try (i) proving that it's not regular, (ii) coming up with a different description of $L$ from which one it is easy to see that $L$ is regular. Hopefully one of these will work. $\endgroup$ – Yuval Filmus Sep 6 '13 at 1:57
-
$\begingroup$ One of the typical ways to prove a language is irregular is the pumping lemma; since you've already included that as a tag, you are probably aware of that. $\endgroup$ – G. Bach Sep 6 '13 at 2:42
-
$\begingroup$ i said it was nonregular. I used the string 0^p10^p. by pumping lemma, it says we can split the string into xyz. y can only be zeros. So xy^2z would not be in the languge. Thus not regular. (note this is just a sketch) $\endgroup$ – user678392 Sep 6 '13 at 3:21
-
3$\begingroup$ Fundamentally, the pumping lemma fails if you try to use the description $xyx$ because the arbitrary $y$ in the middle absorbs the bit that can be pumped. See another example with the same phenomenon — but here you can't simplify the end bits in the same way. The complexity of this language seems to be a function of the parity of the number of cups of coffee one has had today. $\endgroup$ – Gilles 'SO- stop being evil' Sep 6 '13 at 8:29
$\begingroup$
$\endgroup$
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}1\cdot 1 \cdot 0^p1$ with $q\neq p$, hence $w'\not\in L$.
@Gilles: This came after an even number of cups of coffee :-).
$\begingroup$
$\endgroup$
Recall that the Myhill-Nerode indistinguishability relation $\sim_L$ is defined on the set $\{0,1\}^{*}$ of all inputs as $u \sim_L v$ iff for all $w$, $uw \in L \Leftrightarrow vw \in L$. The Myhill-Nerode Theorem states that $\sim_L$ has finitely many blocks iff $L$ is regular.
Let $\alpha_i = 1^i0^i1$ for each $i\ge 1$. I claim that $[\alpha_i]_{\sim_L} = [\alpha_j]_{\sim_L} \Rightarrow i = j$. Hence $\{[\alpha_i] \mid i=1,2,\dots\}$ forms an infinite subset of the blocks of $\sim_L$. Therefore $\sim_L$ must have infinitely many distinct blocks, so $L$ cannot be regular.
To prove the claim, suppose that $[\alpha_i]_{\sim_L} = [\alpha_j]_{\sim_L}$ for some $i,j \ge 1$. Then $\alpha_i \sim_L \alpha_j$, so for any suffix $w$, $1^i0^i1w \in L \Leftrightarrow 1^j0^j1w \in L$. In particular this must hold for $w=1^j0^j$, and since $1^j0^j11^j0^j \in L$, it must hold that $1^i0^i11^j0^j \in L$. Hence $i=j$.
(Finding an infinite subset that worked required an odd number of cups of tea. But using Myhill-Nerode means not having to remember the various pumping lemmas.)
Edit 2015-10-28: was answering the question about $\{xyx\mid x\in\{0,1\}^{+},y\in\{0,1\}^{*}\}$, now fixed.
answered Sep 6 '13 at 12:17
