- Use the PL to prove that language is
**NOT**regular - "Lemma": Fact to use to prove something else
- Use proof by contradiction:
- Assume language A is Regular.
- Show that A violates the PL
- Thus, A is NOT regular

- DFA $M$ has $p$ states
- That is, $|Q_M|=p$
- Let $L(M)=A$

- $s \in A$
- Assume $|s| = p$
- Question 1: What is the length of $M$'s computation accepting $s$?
- Hint: What if $M$'s computation has 2 states?
- Question 2: What must be true of those states?
- Are they all ...

- Computation has $p + 1$ states
- Must be a repeated state
- Pigeonhole principle

- Let $q_r$ be the first repeated state in the computation
- That is, the first state that appears a second time in the computation
- All states prior to $q_r$ in the computation are unique,
- but $q_r$ repeats an earlier state in the computation

- Let's divide the computation into 3 segments
- States before $q_r$
- States between first 2 occurrences of $q_r$
- States after second occurrence of $q_r$
- Let's label the substrings of $s$ that take the machine
- $x$: From $q_i$ to $q_r$
- $y$: From first $q_r$ to second $q_r$
- $z$: From second $q_r$ to $q_f$ (ie the last state)
- $s=xyz$

- If $xyz$ is in A, what other string is in A?
- And another ...
- And another ...
- Longer and shorter ...
- This is called
**pumping**the string

- A string in a language $A$ is
**pumped**if - it's divided $s=xyz$ and
- the strings $xy^iz, i\ge0$ are in $A$
- We say that the string is
**pumpable** - Informally we talk about
- pumpable machine: it accepts pumpable strings
- pumpable language: it contains pumpable strings

- In a Regular Language,
**all string**that are long enough strings are pumpbable - Long enough means longer than the
**pumping length** - We use $p$ to represent the
**pumping length**of a language - We don't know the value of $p$
- but that's okay, the value is NOT needed
- All we need to know is that it exists
- Effectively, $p$ can be any value that is larger than the number of states in some machine that accepts the language
- We don't need to actually create this machine
- We just assume that it exists, and let $p$ be its number of states

- What is $|y|$
- Two occurrences of $q_r$ must have a non-empty path between them
- Where must the second occurrence of $q_r$ be?
- That is, $|xy|$ ...

- If $A$ is regular, then it has a pumping length $p$
- If $s\in A$, and $|s| \ge p$ then
- $s$ can be divided into $xyz$ such that
- $xy^iz \in A$, for $i\ge0$
- $|y| \gt 0$
- $|xy| \le p$

- If $A$ is regular, then
- If $s$ is in $A$, and $s$ is long enough,
- $s$ can be divided into substrings $x$, $y$, and $z$ such that
- $s$ can be pumped
- The pumpable substring is not empty
- The pumpable substring is at the beginning of the computation

- Let $A=\{0^n1^n\ |\ n\ge0\}$
- Let $p$ be the pumping length for $A$
- Consider $s=0^p1^p$
- Clearly $|s|\ge p$
- Thus $s$ can be divided into $s=xyz$ such that conditions 1-3 hold
- But there are only 3 possibilities for $y$, and each leads to a contradiction:
- If $y=0^k,k\gt0$, then $xy^2z$ has $p+k$ 0's and $p$ 1's, and so $xy^2z\not\in A$, a contradiction
- Similarly, if $y=1^k,k\gt0$, then $xy^2z$ has more 1's than 0's and is not in $A$, a contradiction
- If $y=0^j1^k,j,k\gt0$, then in $xy^2z$ has a string of 0's followed by a string of 1's then more 0's, and so it is not in $A$, a contradiction
- Thus, $A$ is not regular.

- Choosing the right $s$ is critical:
- Choose one that is
**impossible**to divide for pumping - Lots of strings are pumpable (eg 01)
- You only need to find ONE non-pumpable string
- Possibilities 1 and 2 select $y$ from the left and right halves of $s$, respectively
- Possibility 3 selects $y$ from the middle of the string
- Actually, possibilities 2 and 3 are impossible by condition 3!
- By condition 3, where must $y$ be?
- Exercise: in the third possibility, what string, exactly, is $xy^2z$

- Imagine the set of all languages and the set of regular languages
- How do you prove that language $A$ is regular?
- How do you prove that language is
**NOT**regular - What is true of all regular languages
- Can you use the Pumping Lemma to prove that a language
**IS**regular? - No. There are pumpable languages that are not regular.

ITEC 420 Course Page