Pumping Lemma Proof for non-regular languages

Question

Okay, so this is a confusing and abstract topic. I'm having some trouble proving a language is not regular using the Pumping Lemma.

Suppose I have: $L = \{ a^ncb^n | n >0\}$

I know for a fact that this is not a regular language since there needs to be a memory somewhere to keep track of how many a's and b's there are. However, if I choose to do this formally, I fall short on my proof.

Considering $p$ being the pumping constant for: $L = \{ a^pcb^p | n >0\}$, I need to find a string $w$ whose length is less than or equal to $p$ while breaking it down into three parts: $w=xyz$ for $|xy|\le p$ and $|y| \gt 0$.

The only way I can do this proof is by actually choose a value for $p$, say $p=3$.

Which would yield: $w=aaacbbb$ where $x=aa$ , $y=a$ and $z=cbbb$. (from left to right of the string). If I pump $y^i$ where $i=2$, This would yield a string $aaaacbbb$ where the number of $a's$ exceed the number of $b's$. This itself is a contradiction.

Although finding a single counter-example like the one above, it is enough to prove that a language is not regular. But, according to the definition, how do I prove this for all values of $i \geq 0$. Is there a more general way of doing these proofs without using hard-coded numbers like the one I gave?

I found the above example with the following explanation:

"The only way to partition w into three parts, $w = xyz$, is such that $x$ contains 0 or more a's, $y$ contains 1 or more a's, and $z$ contains 0 or more a's concatenated with $cb^p$ . This is because of the restrictions $|xy| \leq p $ and $|y| > 0$"

I'm not sure how they came up with all of these cases and is where I get stuck.

Answer 1

The Pumping Lemma says that if $L$ is a regular (and infinite) then $\exists p \in \mathbb N$ such that $\forall w \in L$ such that $|w| \geq p$ there $\exists x,y,z$ such that $w = xyz$, $|xy|<p$, $|y|>0$ and $\forall k \in \mathbb N$ one always have $xy^kz \in L$. So we have $\exists-\forall-\exists-\forall$ scheme.

So, if you'd like to show that $L$ is not regular you need to implement $\forall-\exists-\forall-\exists$. In other words: $\forall p \in \mathbb N$ there $\exists w \in L$ such that $|w| \geq p$ and $\forall x,y,z$ such that $w = xyz$, $|xy|<p$, $|y|>0$ there $\exists k \in \mathbb N$ such that $xy^kz \not\in L$.

In your example, let fix some $p \in \mathbb N$. Then we need some word: let's take $w=a^pcb^p$ (obviously, $|w|>p$). Then $\forall$ subwords $x,y,z$ such that $w=xyz$, $|xy|<p$ and $|y|>0$ we obtain that $x$ and $y$ contain only $a$'s (since $|xy|<p$ and in $w$ we have $p$ $a$'s). So, now, let's consider, for instance, $k=2$. Then, since $|y|>0$, $xy^2z$ have more $a$'s than $b$'s (precisely, $+|y|$ more $a$'s). Hence, $xy^2z \not\in L$. $\square$