# Why is this language involving reversal regular?

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?

• I'm pretty sure that it's not regular. What makes you think it is? – jmite Aug 27 '13 at 7:33
• it could be a mistake but I see it as a correct answer in a solved exam I have. – aviran Aug 27 '13 at 7:38
• 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$... – J.-E. Pin Aug 27 '13 at 8:35
• Scratch my comment, I missed the nuance of the language. – jmite Aug 27 '13 at 16:42

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.

• To complete Gilles's answer, the minimal DFA for $L$ has 15 states and 4 final states. – J.-E. Pin Aug 27 '13 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 \}$