# Proving $L=\{wvw|v\in \{0,1\}^*, w\in \{0,1\}^+\}$ is not regular using the myhill-nerode and pumping lemma [duplicate]

Firstly, I've tried assuming $$L$$ is regular and find a contradiction with help of the pumping lemma's 3 conditions, I was not able to get to a contradiction.

I've tried thinking of a word $$z\in \{0,1\}^*$$ to attach to $$wv^i$$ and $$wv^j$$ for some $$i\neq j$$, and to combine that with the pumping lemma's $$xy^2z\in L, k\geq 1$$ yet I got stuck on the way.

I'm looking for a direction of thought, a colleague suggested looking at the example word $$10000000110000000$$ , yet I cant see the how this example promotes what I'm trying to prove.

• Does this answer your question? Determine if this language is regular The language is slightly different, but the accepted answer seems to apply. (And is similar to what your colleague suggested.) Commented Mar 25, 2023 at 13:33

This language is regular. Denote $$L = \{wvw\mid v,w\in\{0,1\}^*\}$$.

I claim $$L = \{0,1\}^*$$. Indeed, the inclusion $$\subseteq$$ is clear. Conversely, let $$u\in \{0,1\}^*$$. Then $$u = \varepsilon u\varepsilon \in L$$.

• Apologizes, I've forgot to mention the fact that $\epsilon \notin L$ I've also saw how it is regular when $\epsilon \in L$. Commented Mar 25, 2023 at 10:07
• What you say makes no sense: the language $\{wvw\mid v,w\in\{0,1\}^*\}$ is uniquely defined and it contains $\varepsilon$. Commented Mar 25, 2023 at 10:11
• Even if you consider $L = \{wvw\mid v,w\in\{0,1\}^*\}\setminus\{\varepsilon\}$, it is still regular, because regular languages are closed under set difference. Commented Mar 25, 2023 at 10:13
• double apologizes, it was my misunderstanding of the instructions I was given. after further clarifications from my instructor, instead of $\epsilon \notin L$, what I've meant is that the $w$ in $w,v\in \{0,1\}^*$ satisfies $w\neq \epsilon$ Commented Mar 25, 2023 at 10:29
• Then just write $L = \{wvw\mid v\in \{0,1\}^*, w\in \{0,1\}^+\}$ so that there is no ambiguity. Commented Mar 25, 2023 at 10:52

Of course it is regular, because it contains the complete set {0,1}*.

Note: This was the correct answer to the question before it was edited.