patternMinor
Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
Viewed 0 times
irregularitymidneqw_2w_1
Problem
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!
$$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!
Solution
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.
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.
Context
StackExchange Computer Science Q#138502, answer score: 7
Revisions (0)
No revisions yet.