For a language to be regular it needs to be recognized by DFA/NFA.

Let $L = \{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \}$ over the alphabet $\{0,1\}$.

$x^r$ means the reverse of $x$.

A DFA has no memory, so how can it handle the reverse check?

  • 1
    $\begingroup$ I'm pretty sure that it's not regular. What makes you think it is? $\endgroup$ Commented Aug 27, 2013 at 7:33
  • $\begingroup$ it could be a mistake but I see it as a correct answer in a solved exam I have. $\endgroup$
    – Aviran
    Commented Aug 27, 2013 at 7:38
  • $\begingroup$ A more difficult exercise would be to find, for each word $u$ in $L$, the number of ways you can write $u$ as $xy^rzyx^r$ with $|x|, |y|, |z| \geqslant 1$... $\endgroup$
    – J.-E. Pin
    Commented Aug 27, 2013 at 8:35
  • $\begingroup$ Scratch my comment, I missed the nuance of the language. $\endgroup$ Commented Aug 27, 2013 at 16:42

2 Answers 2


Notice that big unconstrained $z$ in the middle. You don't need the DFA to check anything if there is a way to decompose the word that dumps almost everything into $z$.

In particular, any word of the form $a b z b a$ where $a$ and $b$ are letters and $z$ is an arbitrary non-empty word is in $L$ (with words of length 1 for $x$ and $y$).

Conversely, suppose that you have a word $w \in L$: it can be broken down as $x y^r z y x^r$ with $|x| \ge 1$ and $|y| \ge 1$. If $|x| \ge 2$ then write $x = a b x'$: we have $w = a b x' y^r z y x'^r b a = a b z' b a$ where $z' = x' y^r z y x'^r$. If $|x| = 1$ then write $y = b y'$ and do a similar decomposition.

Conclusion: another way of describing $L$ is $L = \{a b z b a \mid a,b \in \{0,1\}, z \in \{0,1\}^{+}\}$. This language is regular; a regular expression that matches it is 00..*11|01..*10|10..*01|11..*11. Intuitively, an autotomaton recognizing $L$ only needs a finite amount of memory, because it only needs to memorize the first two letters.

  • $\begingroup$ To complete Gilles's answer, the minimal DFA for $L$ has 15 states and 4 final states. $\endgroup$
    – J.-E. Pin
    Commented Aug 27, 2013 at 8:32

To complete Gilles's answer, another way to find the result : notice that if you set $y' = y^r$, you obtain (since $y = y'^r$) :

$ L = \{ xy'zxy'^rx^r : |x|,|y'|,|z| \geq 1 \}$

Thus setting $t = xy'$, since $t^r = y'^rx^r$, we end up with :

$ L = \{ tzt^r : |z| \geq 1, |t| \geq 2 \} $

And, as Gilles said, you can keep only two letters in $t$ and put all the remaining stuff in $z$, to finally obtain the same result :

$ L = \{ tzt^r : |z| \geq 1, |t| = 2 \} $


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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