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?
Asked
Active
Viewed 247 times
5
-
1I'm pretty sure that it's not regular. What makes you think it is? – Joey Eremondi Aug 27 '13 at 07: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 07: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 08:35
-
Scratch my comment, I missed the nuance of the language. – Joey Eremondi Aug 27 '13 at 16:42
2 Answers
9
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.
Gilles 'SO- stop being evil'
- 43,613
- 8
- 118
- 182
-
To complete Gilles's answer, the minimal DFA for $L$ has 15 states and 4 final states. – J.-E. Pin Aug 27 '13 at 08:32
4
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 \} $
Tpecatte
- 361
- 1
- 7