Pumping Lemma

Pumping Lemma
• The pumping lemma describes something that the
regular languages satisfy
If regular then the properties of pumping lemma satisfied
If pumping lemma not satisfied then …..
Remember contrapositive?
Regular languages
• Not all languages are regular!
• How to show a language is regular?
– Write a regular expression for it
– Break it down via unions, intersections,
concatenations, stars, complements, reversals
• {a^k | k is a multiple of 6} is regular because {a^k | k is
a multiple of 2} is regular and {a^k | k is a multiple of 3}
is regular
– Make a DFA/NFA
Central idea of the pumping lemma
• If the language contains only a finite number
of strings, we have a regular language. Why?
– Make an NFA for each string
– Union them all
• The finiteness of states is v important and is
the main concept the pumping lemma uses
Central idea of the pumping lemma
• Assume the language is accepted by a DFA
that has p states. Now consider what happens
when you have a string that is p in length.
What states are you going to hit?
• As you go from state to state while traversing
the string ….
You will repeat a state!
Central idea of pumping lemma
• How do states repeat themselves? That means
the NFA/DFA/graph contains ….
A loop!
• Using a loop we can pump!
Pumping just means using the loop over and
over again
Statement of pumping lemma
If A is a regular language then A has a ‘pumping
length’ p such that any string s that is longer
than p can be broken into 3 pieces s = xyz
so that
• xyiz is in A. Basically saying the string y is the
string you can read on the loop
• Length of y is non-zero
• Length of xy portion <= p

similar documents