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

Question

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!

Answer 1

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.

Answer 2

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$.