5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I'm pretty sure that it's not regular. What makes you think it is? $\endgroup$ – jmite Aug 27 '13 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 Aug 27 '13 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 Aug 27 '13 at 8:35
  • $\begingroup$ Scratch my comment, I missed the nuance of the language. $\endgroup$ – jmite Aug 27 '13 at 16:42
9
$\begingroup$

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.

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

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

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