recall that a regular language is one that can be expressed using finite automata or regular expressions a non-regular language on the other hand cannot here is an example of a non-regular language if you try to construct a finite automaton for this language 0 to the n1 to the n you will find that it is impossible and that is because nfas and dfas have a finite amount of memory so other than failing again and again to construct a machine that recognizes the language how else can we show that a language is not regular this is where
the pumping lemma comes in recall that a pumping lemma states that if a language is regular then every string in the language of a certain length can be pumped any number of times and still be in the language if you aren't familiar with the pumping lemma we have a video on it that you should definitely watch link is in the description below so how can we use the pumping lemma to prove that a language is not regular well we know that every regular language must satisfy the pumping lemma which means that if a language does
not satisfy the pumping lemma then it cannot be regular and that language is instead a non-regular language so to use the pumping lemma to formally prove that a language is not regular we show that it does not satisfy the pumping lemma this is done through a proof by contradiction here is the intuition for how the proof works let's say we want to prove that the language 0 to the n 1 to the n is not regular because this is a proof by contradiction we first claim that it is regular we then take it to the
all-knowing pumping lemma that gives us back the pumping length p which if you recall if a language is regular then for all strings in the language that has a length of at least p there will be a section of the string that can be pumped and still be in the language now given p this next step is where we show that the language is actually not regular we have to find a string that is at least length p that breaks the pumping lemma so for our example 0 to the n1 to the n this string
0 to the p1 to the p is indeed at least as long as p but cannot in fact be pumped we will use this string to contradict our initial assumption that the language satisfies the pumping lemma and since we had claimed that the language is regular according to the pumping lemma the string can be split into three different components the part before pumping the part being pumped and the part after pumping and this is where we see things go wrong and the contradiction kicks in we can argue that there are three cases for how the
pumping lemma could have chosen y it could have chosen all zeros all ones or a combination of zeros and ones as the pumping string if the pumping string consisted of all zeros then we will end up with a string that has more zeros than ones which doesn't belong in the language similarly if the pumping string consisted of all ones then we will end up with a string that has more ones than zeros which also does not belong in the language and if the pumping string y was somewhere in the middle where it consisted of both
zeros and ones then we may end up with a string with a different sequence which also does not belong in the language therefore this string that belongs in the language cannot actually be pumped and as long as there is one string that is at least length p that cannot be pumped such as this one then the language does not in fact satisfy the pumping lemma and therefore is not regular and one final note if we had noticed that the third condition of the pumping lemma requires y to be within the first p symbols we could
have actually eliminated the second and third cases in summary we first assume that the language is regular then given p we find a string that can't in fact be pumped and then we show how splitting and pumping the string will result in a string that is not in the language and therefore we contradict our initial assumption that the language is regular
