Prove that this language is not regular (Pumping Lemma) Prove that the following language is not regular. I have no clue where to start.
$$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
 A: The Myhill-Nerode theorem shows this immediately.
The infinitely many prefixes $a^ib^i$ are all pairwise distinguishable. (If $i\ne k$, then $c^i$ is a distinguishing extension: $a^ib^ic^i \in L$ but $a^kb^kc^i\notin L$). Therefore the language cannot be regular.
A: Suppose $L$ is regular. Let $n \in \mathbb{N}$ be the number mentioned in Pumping lemma (PL). Now, let us take $\alpha=a^nb^nc^n$. According to PL, we can choose $u,v,w$ such that $\alpha=uvw$, $|uv| \leq n$ and $|v| \geq 1$. Then, since $|uv| \leq n$, the word $v$ consists of $a$'s only. And so, for example, $uv^2w$ contains $n+|v|$ letters $a$, while the number of $b$'s and $c$'s do not change. Hence, $uv^2w \not\in L$ that contradicts PL.
A: Suppose $L$ were regular. According to the Pumping Lemma, every sufficiently long word in $L$ can then be written as $xyz$ with $y \neq \epsilon$ such that $xy^iz \in L$ for all $i$. Now, take a sufficiently long word in $L$ and write it that way. If $y$ consists of two or three different types of letters (e.g., both $a$'s and $b$'s in $y$), then $xy^2z \not\in L$ because it doesn't even belong to $L(a^*b^*c^*)$. If $y$ consists of all the same letters, then $xy^2z$ doesn't have the same number of $a$'s, $b$'s and $c$'s, so then $xy^2z \not\in L$ either.
