3
$\begingroup$

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!

$\endgroup$
2
  • 3
    $\begingroup$ Your question suggests you are looking for applicable closure properties. One approach probably is to restrict to strings of the form $b^*aab^*$. $\endgroup$ Apr 4 '21 at 1:08
  • $\begingroup$ 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. $\endgroup$
    – D. Petrov
    Apr 4 '21 at 1:26
7
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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! $\endgroup$
    – D. Petrov
    Apr 4 '21 at 1:21
  • 1
    $\begingroup$ @D.Petrov. I added an alternative solution. $\endgroup$
    – Steven
    Apr 4 '21 at 1:31
  • 1
    $\begingroup$ 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! $\endgroup$
    – D. Petrov
    Apr 4 '21 at 1:35
  • $\begingroup$ 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$"? $\endgroup$
    – justhalf
    Apr 4 '21 at 11:03
  • $\begingroup$ @justhalf, yes. Thanks $\endgroup$
    – Steven
    Apr 4 '21 at 11:06
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Now that's a clever idea, thank you! $\endgroup$
    – D. Petrov
    Apr 4 '21 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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