# Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$

I'm currently struggling to come up with a proof that the following language is irregular: $$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$ where $$\Sigma = \{a, b\}$$.

Now quite intuitively, the language needs to know what $$|w_1|$$ was in order to compare against $$|w_2|$$, so it has to be irregular, but I'm failing to formally prove that.

I was able to solve the previous problem from the book, which was proving that (similarly) $$L_1 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| = |w_2|\}$$ is irregular, which was relatively simple using the pumping lemma.

So I thought maybe there was some kind of connection between the two problems, given that $$L_1\cup L_2$$ is regular, but there doesn't seem to be any kind of closure property I can robustly employ in order to prove that $$L_2$$ is irregular.

Any ideas are welcome and many thanks in advance!

• Your question suggests you are looking for applicable closure properties. One approach probably is to restrict to strings of the form $b^*aab^*$. Apr 4, 2021 at 1:08
• Hm, I didn't think such a restriction could prove fruitful. I don't get the implications of it yet, but I will have a thought. Apr 4, 2021 at 1:26

## 2 Answers

For $$i \ge 0$$ define $$w_i = b^i aa$$. For any $$i,j \ge 0$$ with $$i \neq j$$ you have that $$b^i$$ is a distinguishing extension for $$w_i$$ and $$w_j$$. Indeed, $$w_i b^i \not\in L_2$$ but $$w_jb^i \in L_2$$.

Then the number of equivalence classes of the set $$\{ w_i \mid i \ge 0\}$$ with respect to the equivalence relation "having a distinguishing extension" is not finite and, by the Myhill-Nerode theorem, $$L_2$$ is not regular.

Here is an alternative solution that uses closure properties and the pumping lemma following the hint of Hendrik Jan.

Suppose that $$L_2$$ is regular. Then so is $$L' = \overline{L}_2 \cap \{b^i aa b^j\} = \{b^i aa b^i\}$$, which is easily shown to be non-regular using the pumping lemma.

Indeed, suppose that $$L'$$ was regular, and let $$p$$ be its pumping length. For some $$k \in \{1, \dots, p\}$$, the word $$b^p aa b^p \in L'$$ can be written as $$b^k b^{p-k} aa b^p$$ such that $$b^{ki} b^{p-k} aa b^p \in L'$$ for every $$i \ge 0$$. Nevertheless, for $$i=0$$ we have $$b^{p-k} aa b^p \not\in L'$$, yielding a contradiction.

• That's the first time I hear of that theorem, I will have a look at it. But since we haven't learned it yet, I guess the proof is achievable in a more, so to speak, simplistic manner. Thank you! Apr 4, 2021 at 1:21
• @D.Petrov. I added an alternative solution. Apr 4, 2021 at 1:31
• Thank you a hundredfold! That's exactly what I was looking for! Also reveals the implications of @HendrikJan's suggestion as well. Also, your proof for the irregularity of $L'$ is exactly the same as mine, which is another nice confirmation that I've got it right! Apr 4, 2021 at 1:35
• For your first line, did you mean to say that "Indeed, $w_ib^i\not\in L_2$ but $w_jb^i\in L_2$"? Apr 4, 2021 at 11:03
• @justhalf, yes. Thanks Apr 4, 2021 at 11:06

You can also use the pumping lemma directly. Let $$p$$ be the pumping length, and consider the word $$w = b^paab^{p+p!} \in L_2$$. According to the pumping lemma, there is a decomposition $$w = xyz$$ such that $$|xy| \leq p$$, $$y \neq \epsilon$$, and $$xy^tz \in L_2$$ for all $$t \geq 0$$. Thus $$y = b^q$$ for some $$q \in \{1,\ldots,p\}$$. If we take $$t = 1 + p!/q$$ then $$xy^tz = b^{p+p!}aab^{p+p!} \notin L_2$$.

• Now that's a clever idea, thank you! Apr 4, 2021 at 22:20