Pumping Lemma for RL: A New Introduction

Ultimate Goal of the Pumping Lemma for Regular Languages

• 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

$L(M) = A$

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

Consider String $s$ and its Computation

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

Answers

• Computation has $p + 1$ states


• Must be a repeated state
• Pigeonhole principle

$q_r$ - The First Repeated State

• 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

Divide the computation

• Let's divide the computation into 3 segments
1. States before $q_r$
2. States between first 2 occurrences of $q_r$
3. States after second occurrence of $q_r$


• Let's label the substrings of $s$ that take the machine
1. $x$: From $q_i$ to $q_r$
2. $y$: From first $q_r$ to second $q_r$
3. $z$: From second $q_r$ to $q_f$ (ie the last state)


• $s=xyz$

Other strings in A?

• If $xyz$ is in A, what other string is in A?
• And another ...
• And another ...
• Longer and shorter ...


• This is called pumping the string

Pump a String - Defined

• 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

Pumping Length

• 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

Other Conditions on the Computation

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

What is True for All Regular Languges

• 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
1. $xy^iz \in A$, for $i\ge0$
2. $|y| \gt 0$
3. $|xy| \le p$

What is True, Using Words

• 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
1. $s$ can be pumped
2. The pumpable substring is not empty
3. The pumpable substring is at the beginning of the computation

Use PL to Prove $0^n1^n$ is NOT Regular

• 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:
1. 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
2. Similarly, if $y=1^k,k\gt0$, then $xy^2z$ has more 1's than 0's and is not in $A$, a contradiction
3. 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.

Thinking About the Above Proof

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

Thinking About Proving that a Language is Regular

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