0
$\begingroup$

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:

enter image description here

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – Daniel
    Commented May 14 at 8:35
  • $\begingroup$ 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. $\endgroup$
    – codeR
    Commented May 14 at 10:04
  • $\begingroup$ I made one mistake in $L_1$ though. I am rectifying that. $\endgroup$
    – codeR
    Commented May 14 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.