5
$\begingroup$

This particular language:

$$L = \{ u u^R v \,:\, u, v \in \{0, 1\}^+\}$$

is giving me a lot of trouble. I highly suspect that its non-regular, considering that $\{ u u^R : u \in \{0, 1\}^+\}$ is non-regular, and I can't seem to reason out a DFA for it.

However, trying to achieve a contradiction with the pumping lemma is giving me a lot of trouble. because of the arbitrary $v$ in the construction. In particular, if the string starts with $00$ or $11$ it is automatically in the language because we can pick $v$ as the remainder and the first two characters are trivially the reverse of each other.

Issues like this seem to thwart my every attempt at applying the pumping lemma. With $p$ as the pumping length, I tried something like $(01)^p (10)^p 1$ but you can simply pump up the starting character to obtain a string that starts with $00$ (and pumping down also works), so this string doesn't work for contradicting the pumping lemma.

I'm pretty stuck on ideas for strings that will contradict the pumping lemma, so I could appreciate a hint on the problem. (Perhaps it is regular? That's still in the back of my mind too)

$\endgroup$
  • 1
    $\begingroup$ Nice example of nonregular language, given that $\{uvu^R \mid u,v \in \{0,1\}^+\}$ is regular. $\endgroup$ – J.-E. Pin Oct 13 '15 at 8:37
  • 3
    $\begingroup$ @J.-E.Pin But that's mostly because $\{uvu^R : u,v \in \{0,1\}^+\}$ is another way of writing $\{uvu : u \in \{0,1\} \wedge v \in \{0,1\}^+\}$. $\endgroup$ – G. Bach Oct 13 '15 at 20:03
3
$\begingroup$

You can also use another approach: suppose that your language $L$ is regular; then you can intersect it with another regular language:

$L_R = (01)^* (10)^* 1$

and - by the closure properties of regular languages - you get another regular language:

$L' = L \cap L_R = \{ (01)^n\,(10)^m1 \mid m \geq n > 0 \}$.

Now it is easier to prove that $L'$ is not regular using the pumping lemma (just pick $n = p$, the pumping length), leading to a contradiction.

$\endgroup$
  • $\begingroup$ This is really nice! I was close to something like this but couldn't quite pin down a nice language to intersect with $\endgroup$ – cemulate Oct 13 '15 at 20:18
  • $\begingroup$ $n = m$ in the definition of $L'$. $\endgroup$ – Renato Sanhueza Nov 8 '15 at 18:46
5
$\begingroup$

When you are stuck in a place like this, it pays to check if the method can work at all. That is, try to prove the opposite. Since the Pumping lemma does not characterise REG, this is actually possible.

Claim: Your language $L$ fulfills the conditions of the Pumping lemma with $p=1$.

Let $w = uu^Rv$ for $u, v \in \Sigma^+$; say $|w|=n$ and $|u|=m$. With the (canonical) notation from the Pumping lemma, pick $x = \varepsilon$, $y=w_1$ and $z = w_2\cdots w_n$.

By definition, $|y| \geq 1$ and $|xy| \leq p$. Furthermore,

  • $xy^0z = (u_2\cdots u_m) \cdot (u_2\cdots u_m)^R \cdot u_1 v \in L$,
  • $xyz = w \in L$, and
  • $xy^iz = u_1 u_1^R (u_2 \cdots u_m) u^R v \in L$, for $i \geq 2$.

Q.e.d. -- $L$ has the Pumping property.

That is, the Pumping lemma can not be used here, you need other methods.

$\endgroup$
  • $\begingroup$ Yes, I had reached this conclusion myself a while after I made the post. It certainly pays to check. $\endgroup$ – cemulate Oct 13 '15 at 20:19
4
$\begingroup$

Use the Myhill–Nerode criterion instead. I claim that the words $(01)^n$ for $n \geq 1$ are pairwise indistinguishable. Indeed, consider $(01)^n$ and $(01)^m$, where $n > m$. Clearly $(01)^m(10)^m0$ is in your language. I claim that $(01)^n(10)^m0$ isn't. If it was, then we could write $(01)^n(10)^m0=uu^Rv$ for non-empty $u,v$. Note that the two symbols at the center of $uu^R$ are either $00$ or $11$. Neither cases can happen since the occurrences of $11$ and $00$ lie to the right of the center of $(01)^n(10)^m0$.

$\endgroup$
2
$\begingroup$

Use closure properties. Assume $L$ is regular. Take the regular language $L_R = (0 1)^* (1 0)^* 1 1$, the language $L \cap L_R = \{ (0 1)^n (1 0)^n 1 1 \colon n \ge 1\}$ is also regular. Consider the homomorphism:

$\begin{align} h(a) &= 0 1 \\ h(b) &= 1 0 \\ h(c) &= 1 1 \end{align}$

then you have that $h^{-1}(L \cap L_R) = \{a^n b^n c \colon n \ge 1\}$ is again regular. Now use the homomorphism:

$\begin{align} g(a) &= 0 \\ g(b) &= 1 \\ g(c) &= \epsilon \end{align}$

and so $g(h^{-1}(L \cap L_R)) = \{ 0^n 1^n \colon n \ge 1\}$ is regular. But this last one is the canonical example of a non-regular language, so our assumption that $L$ is regular is wrong.

$\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.