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

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

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.
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.
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.
• While proving irregularity, finding just one $w$ that can not be pumped is enough, right? E.g. we can write some other $w$ using the $p$, like $w=a^{p+1}b^pc^p$ that can be pumped, but that does not change the fact $L$ is irregular. – Zargo May 31 '20 at 8:56
• The pumping lemma states that if $L$ is regular then there exists $p$ such that for each word $w \in L$ of length at least $p$ there exists a decomposition $w = xyz$ satisfying certain conditions. If for each $p$ you find a word $w \in L$ of length at least $p$ which cannot be decomposed in a way that specifies all the conditions, then you show that the conclusions of the pumping lemma do not hold. Therefore the premise of the lemma must fail, that is, $L$ cannot be regular. – Yuval Filmus May 31 '20 at 10:06