# Is $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$ regular

The question asks to determine if any of the following languages above $$\Sigma=\left \{ 0,1 \right \}$$ is regular.

The languages are:

$$L_1=\left \{ \sigma_1u\sigma_2v\sigma_3:\begin{matrix} \sigma_1,\sigma_2,\sigma_2\in\Sigma \ , \ u,v\in \Sigma^{*}\\ |u|=|v|\\ \sigma_1=\sigma_2 \ and \ \sigma_1\neq \sigma_3 \end{matrix} \right \}$$

$$L_2=\left \{ \sigma_1u\sigma_2v\sigma_3:\begin{matrix} \sigma_1,\sigma_2,\sigma_2\in\Sigma \ , \ u,v\in \Sigma^{*}\\ |u|=|v|\\ \sigma_1=\sigma_2 \ xor \ \sigma_2\neq \sigma_3 \end{matrix} \right \}$$

About $$L_2$$ :

The words belonging to $$L_2$$ are of the following form:

$$\left \{ 0\Sigma^{n}0\Sigma^{n}0\ , 1\Sigma^{n}1\Sigma^{n}1\ ,\ 1\Sigma^{n}0\Sigma^{n}1\ ,\ 0\Sigma^{n}1\Sigma^{n}0 \right \}: n\geq 0$$

It holds that $$\forall w\in L_2 \ , \ |w|=2n+3 : n\in\mathbb{N} \cup\left \{ 0 \right \}$$.

I use the answer @codeR gave me to this question and came with the follow automaton:

About $$L_1$$ :

The words belonging to $$L_1$$ are of the following form:

$$\left \{0\Sigma^{n}0\Sigma^{n}1 \ , \ 1\Sigma^{n}1\Sigma^{n}0 \right \} : n\geq 0$$

It holds that $$\forall w\in L_1 \ , \ |w|=2n+3 : n\in\mathbb{N} \cup\left \{ 0 \right \}$$.

I think that this language is not regular.

Intuitively, I need to ensure that $$\sigma_1=\sigma_2 \ and \ \sigma_1\neq \sigma_3$$

but $$\sigma_2\in(0+1)^{2n+1}$$ and I can't control it's value.

I also used the pumping lemma for regular languages for $$w=1^{n+2}0^{n+1}\in L_1$$ and it gave me that $$L_1$$ is not regular.

Probably I'm doing something wrong, but I can use the pumping lemma for regular languages for $$w=1^{n+1}0^{n+1}1\in L_2$$ and I will get in the same way that $$L_2$$ is not regular as well.

I would really like to get some opinion on what I wrote.

• Do you mean $\sigma_1, \sigma_2, \sigma_3 \in \Sigma$ and $u, v \in \Sigma^*$ as before? Commented May 14 at 7:57
• @codeR Yes. I edited the post. Commented May 14 at 8:09

Yes, you are correct. Given $$\sigma_1, \sigma_2, \sigma_3 \in \Sigma$$ and $$u, v \in \Sigma^*$$, $$L_2$$ can be expressed as $$0(0+1)^{2n+1}0 + 1(0+1)^{2n+1}1$$, which is of course regular.
On the other hand, $$L_1$$ can be proven to be non-regular using the Pumping lemma. Hint: All strings in $$L_1$$ are of odd length. Take a string of the form $$\omega = 01^m01^m1$$, which is in $$L_1$$. Now take any decomposition $$w = xyz$$. Depending on your choice of $$y$$, when $$|y|$$ is odd, we can construct an even-length string $$\omega' = xy^iz$$ for any even $$i$$, which of course is not in $$L_1$$. When $$|y|$$ is even, we can force (by pumping with $$i$$) the middle $$0$$ to be shifted (either left or right). Simply letting $$i=0$$ causes the conditions $$\sigma_1 = \sigma_2$$ and $$\sigma_1 \ne \sigma_3$$ to be violated.
• Thank you. I'm wondering, $w=1^{n+1}0^{n+1}1\in L_2$. If I use the Pumping lemma with $w$, will it not contradict that $L_2$ is regular ? Commented May 14 at 8:35
• How? Be careful with $\forall$ and $\exists$ in the proof. It is better to play the pumping lemma proof as a two-player turn-based game. Commented May 14 at 10:04
• I made one mistake in $L_1$ though. I am rectifying that. Commented May 14 at 10:05