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
- 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?
Answers
- Computation has $p + 1$ states
- Must be a repeated state
$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
- 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$
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?
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
- $xy^iz \in A$, for $i\ge0$
- $|y| \gt 0$
- $|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
- $s$ can be pumped
- The pumpable substring is not empty
- 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:
- 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.
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.
ITEC 420 Course Page