Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why is this language involving reversal regular?

, , No Comments
Problem Detail: 

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 By : aviran

Answered By : Gilles

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13956

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback