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