4
$\begingroup$

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.

$\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 Sep 6 '13 at 8:29
4
$\begingroup$

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 :-).

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.