Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{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.
Is {wxw^r} a regular language?
formal languages;regular languages;finite automata
$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,x\in \{0,1\}^+\} = \{WxW : W\in\{0,1\} , x\in \{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.