Problem Detail: Is ${ WxW^{mathrm{R}} mid W,xin{0,1}^+}$ a regular language? If so, why? The notation $W^{mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, if the language is regular, then its FA should reject all strings not in the language. However, a string such as 0110100 would also be accepted by the FA, since it compares only the starting and end characters! Please explain.
Asked By : Somenath Sinha
Answered By : Renato Sanhueza
- $W^R$ means the reverse string of $W$.
- You are right about the DFA. If a DFA $A$ accepts the language $L$ then it rejects all the words that are not in $L$. But the word $sigma = 0110100$ is in the language!. Consider $W=0$ and $x=11010$.
- As G.Bach eloquently stated in his comment(a very interesting property of the language):
$${WxW^R : W,xin {0,1}^+} = {WxW : Win{0,1} , xin {0,1}^+}$$ ¿Why? Because there is little restriction to $x$. We can consider that $x$ is almost the whole word with the exception of the first and the last symbol(because in the original language $|W|>0$). The reverse string of any word with unitary size is the same word. So words like: $$sigma_1 = 01110000$$ $$sigma_2 = 11111101$$ Are in the language. All that matter is the first and the last symbol. This language is very interesting because it appears to be irregular at the first sight.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50689 Ask a Question Download Related Notes/Documents
