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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ I'm pretty sure that it's not regular. What makes you think it is? $\endgroup$– jmiteAug 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$– AviranAug 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. PinAug 27, 2013 at 8:35
-
$\begingroup$ Scratch my comment, I missed the nuance of the language. $\endgroup$– jmiteAug 27, 2013 at 16:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Aug 27, 2013 at 7:56
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
42.1k7 gold badges112 silver badges175 bronze badges
-
$\begingroup$ To complete Gilles's answer, the minimal DFA for $L$ has 15 states and 4 final states. $\endgroup$ Aug 27, 2013 at 8:32
$\begingroup$
$\endgroup$
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 \} $
