0
$\begingroup$

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<p$. 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<p$ and because $ a^{2p-k},k<p\neq b^p$ it follows that the pumped $w$ is not in $L$. Which is a contradiction. Therefore $L$ is not regular.

$\tag*{$\blacksquare$}$

$\endgroup$
  • 1
    $\begingroup$ We typically don't check proofs for correctness. $\endgroup$ – Yuval Filmus Jul 23 at 15:35
  • $\begingroup$ Oh okay, I am sorry. Should I delete this question ? $\endgroup$ – Frank Jul 23 at 15:38
  • $\begingroup$ No reason. It should get closed, or somebody might answer in the comments. $\endgroup$ – Yuval Filmus Jul 23 at 15:55
  • $\begingroup$ 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$. $\endgroup$ – prime_hit Jul 23 at 19:48
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jul 23 at 22:04
2
$\begingroup$

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<p$. 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<p$ 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$}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm puzzled by your posting a duplicate of your original proof as an answer. What purpose did it serve? $\endgroup$ – Rick Decker Jul 24 at 0:40
  • $\begingroup$ Because a comment is not a answer. And only after the comments I was sure that my proof is correct. So I think is helpful for others to see the solution as a real solution marked and not as a commen.t $\endgroup$ – Frank Jul 24 at 8:32
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.