$a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?

Question

$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\neq$ into smaller and larger. You will have four sets. You can give CFG's for each. Then since CFGs are closed under union, you have your proof.

Now how can I go around proving that $L$ is not regular? If you prove that the each of these four sets are not regular, you still can not prove that the union is not regular, can you?

Answer 1

Lets assume towards contradiction that L is regular. Then, by closure properties, we have $\bar L$ is regular, and thus also $\bar L \bigcap (a^*b^*c^*)$ is regular. But calculating it, we find out $\bar L \bigcap (a^*b^*c^*)=\{a^nb^nc^n\}$ is not regular.

Answer 2

Suppose that $L$ is regular. Take the complement of $L$ and intersect it with $a^*b^*c^*$. You are left with $M = \{a^n b^n c^n \mid n \ge 0\}$. Due to the closure properties of regular languages, $M$ is also regular.

Let $n_0$ be the pumping length of $M$. By the pumping lemma there is some $x \in \{1, \dots, n_0\}$ such that all words $a^{(n_0-x)+ix} b^{n_0} c^{n_0}$ for $i \ge 0$ belong to $M$.

Pick $i=0$ to obtain $a^{n_0 - x} b^{n_0} c^{n_0} \in M$, a contradiction.

Answer 3

Suppose that $L$ is regular, and let $p$ be the pumping lemma constant. Let $w = a^p b^{p+p!} c^{p+p!} \in L$. By the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, the subword $y$ is composed entirely of $a$'s, say $y = a^t$, where $t \neq 0$. Then $xy^{1+n!/t}z = a^{p+p!} b^{p+p!} c^{p+p!} \notin L$, contradicting the pumping lemma.