Report

Pumping Lemma • The pumping lemma describes something that the regular languages satisfy If regular then the properties of pumping lemma satisfied So If pumping lemma not satisfied then ….. NOT REGULAR 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