# Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

Prove that $$L=\{a^ncb^n| n \in \mathbb{N}\}$$ is not regular.

Here is my try, I would really appreciate if someone could tell me if this is a correct proof.

Proof: Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma. So let p the pumping number.

Let $$w=a^pcb^p$$. $$w$$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $$|y|>0,|xy|\leq p,xy^iz$$ is in L $$\forall i \in N$$. Because $$|xy|\leq p$$ $$y$$ can only contain the symbol $$a$$(If $$y$$ would contain a symbol different from a it would imply that $$|xy|>p$$, which is not possible). Therefore $$y$$ must be in the form $$y=a^{p-k},0\leq k. So the word w equals $$w=a^ka^{p-k}cb^p$$, if we set i=2 we get $$a^ka^{2p-2k}=a^{2p-k},k and because $$a^{2p-k},k it follows that the pumped $$w$$ is not in $$L$$. Which is a contradiction. Therefore $$L$$ is not regular.

$$\tag*{\blacksquare}$$

• We typically don't check proofs for correctness. – Yuval Filmus Jul 23 at 15:35
• Oh okay, I am sorry. Should I delete this question ? – Frank Jul 23 at 15:38
• No reason. It should get closed, or somebody might answer in the comments. – Yuval Filmus Jul 23 at 15:55
• It is quite simple: Choose a large enough $n$ such that the pumping string lies in the part which contains only $a$s. Pump down (or up) to get a string which isnâ€™t of the form $a^ncb^n$. – prime_hit Jul 23 at 19:48
• Illegal proof check here. Seems ok to me. It was only a surprise to read $y=a^{p-k}$. I would expected $y=a^k$ (with $k\le p$), but that is a matter of taste. – Hendrik Jan Jul 23 at 22:04

Let $$w=a^pcb^p$$. $$w$$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $$|y|>0,|xy|\leq p,xy^iz$$ is in L $$\forall i \in N$$. Because $$|xy|\leq p$$ $$y$$ can only contain the symbol $$a$$(If $$y$$ would contain a symbol different from a it would imply that $$|xy|>p$$, which is not possible). Therefore $$y$$ must be in the form $$y=a^{p-k},0\leq k. So the word w equals $$w=a^ka^{p-k}cb^p$$, if we set i=2 we get $$a^ka^{2p-2k}=a^{2p-k},0<=k and because $$a^{2p-k}\neq b^p$$ it follows that the pumped $$w$$ is not in $$L$$. Which is a contradiction. Therefore $$L$$ is not regular.
$$\tag*{\blacksquare}$$
Assume the language is regular, therefore has a finite state machine. Since the state machine is finite, there are n â‰  m such that $$a^nc$$ and $$a^mc$$ arrive in the same state. Therefore $$a^nca^n$$ and $$a^mca^n$$ arrive in the same state. But one is in the language, so that state must be accepting, and one is not in the language, so that same state must be non-accepting.