Programming Languages: Pumping theorem(regular lang) walk through

Question

so I'm trying to figure out pumping theorem for regular languages. Here is an example from class. I'm going to label each line and ask questions about the proof.

Problem:

Let language $L = \{a^m b^n c^q \mid m>n\text{ or }m>q\text{ or }n>q\}$. Apply the pumping theorem for regular languages to prove that language $L$ is not regular.

Solution:

1) Suppose $L$ is regular, and let $p$ be the constant in the pumping theorem.

2) Choose $z = b^{p+1} c^p$, and let $z = uvw$.

3) No matter how we pump the string, it has $m=0$, so conditions $m>n$ and $m>q$ are both false.

4) Because $|uv| \le p$, substring $v$ must be within the first $b^p$.

5) Let $u = b^i$, $v = b^j$, and $w = b^{p+1–i–j} c^p$.

6) Therefore $u v^0 w = b^{p+1–j} c^p \notin L$, because $|v| \ge 1\to j \ge 1 \to p+1–j \le p$.

7) Contradiction, so $L$ is not regular.

Stuff I'm not understanding:

A) What is the importance of line 3? It seems like a follow through from how we chose our $z$.

B) On line 5 we have $b^{p+1-i-j}$, yet on line 6 this changes to $b^{p+1-j}$; where did the $i$ go?

C) On line 6, why is $p+1-j \le p$ a contradiction? As in wouldn't $j$ make $p+1$ go smaller than $p$? And therefore be within the constraints? The only case that this wouldn't apply is when $j$ is equal to $0$.

Thank you guys for any and all help.

Answer 1

You’re quite right: line 3 does follow immediately from the choice of $z$. It’s important because it shows that in order for a pumped string $uv^kw$ to be in $L$, it must have more $b$s than $c$s, since it will never have any $a$s. Remember, we want to get a contradiction by showing that there is at least one $k$ such that $uv^kw\notin L$. The definition of $L$ gives three different ways for a string to get into $L$; by ruling out two of them, we’ve made our lives much simpler.

From line 4 we know that the entire substring $uv$ of $z$ must lie within the first $p$ characters, so it consists entirely of $a$s; if $i$ is the length of $u$, and $j$ is the length of $v$, then it must be the case that $u=a^i$ and $v=a^j$. The rest of the $p+1$ $a$s must be part of $w$, as must all $p$ of the $b$s, so $w=a^{(p+1)-(i+j)}b^p=a^{p+1-i-j}b^p$, and we’ve decomposed $z$ as

$$z=\color{crimson}u\color{blue}vw=\color{crimson}{a^i}\color{blue}{a^j}a^{p+1-i-j}b^p\;.$$

That’s what you’re getting in line 5. In line 6, however, we’re looking not at $z=uvw$, but at $uv^0w$, the string that we get when we pump $z$ down by setting $k=0$ in $uv^kw$. That means that $v$ disappears altogether:

$$uv^0w=\color{crimson}uw=\color{crimson}{a^i}a^{p+1-i-j}b^p=a^{i+(p+1-i-j}b^p=a^{p+1-j}b^p\;.$$

The whole point is that because $j\ge 1$, $p+1-j\le p+1-1=p$. Back in line 3 we noted that no matter what $k$ is, $uv^kw$ does not have more $a$s than $b$s or more $a$s than $c$s, so that the only way for it to be in $L$ is to have more $b$s than $c$s. But we’ve just seen that when $k=0$, $uv^kw$ has at most $p$ $b$s; since it has exactly $p$ $c$s, it does not have more $b$s than $c$s and therefore cannot be in $L$. This contradicts the assumption in line 1: if $L$ really were regular, $uv^0w$ would be in $L$.