Problem Detail: This particular language: $$L = { u u^R v ,:, u, v in {0, 1}^+}$$ is giving me a lot of trouble. I highly suspect that its non-regular, considering that ${ u u^R : u in {0, 1}^+}$ is non-regular, and I can’t seem to reason out a DFA for it. However, trying to achieve a contradiction with the pumping lemma is giving me a lot of trouble. because of the arbitrary $v$ in the construction. In particular, if the string starts with $00$ or $11$ it is automatically in the language because we can pick $v$ as the remainder and the first two characters are trivially the reverse of each other. Issues like this seem to thwart my every attempt at applying the pumping lemma. With $p$ as the pumping length, I tried something like $(01)^p (10)^p 1$ but you can simply pump up the starting character to obtain a string that starts with $00$ (and pumping down also works), so this string doesn’t work for contradicting the pumping lemma. I’m pretty stuck on ideas for strings that will contradict the pumping lemma, so I could appreciate a hint on the problem. (Perhaps it is regular? That’s still in the back of my mind too)
Asked By : cemulate
Answered By : Vor
You can also use another approach: suppose that your language $L$ is regular; then you can intersect it with another regular language: $L_R = (01)^* (10)^* 1$ and – by the closure properties of regular languages – you get another regular language: $L’ = L cap L_R = { (01)^n,(10)^m1 mid m geq n > 0 }$. Now it is easier to prove that $L’$ is not regular using the pumping lemma (just pick $n = p$, the pumping length), leading to a contradiction.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48186 Ask a Question Download Related Notes/Documents
