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

## 3 Answers

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