DFAs, NFAs, and regular expressions are all restricted models of computation in that we trade-off computational expressiveness for tractability in terms of analysis. We crystallize the limitations of these models by showing that some languages are provably not regular. We can do this via two methods:
- The pumping lemma which describes a necessary characteristic of the repetitive nature of infinite regular languages.
- The Myhill-Nerode theorem which relates the finite invariants captured the states of a finite automata to regularity directly.
First, we will learn about the pumping lemma, and in next class, we’ll learn about the Myhill-Nerode Theorem.
- Learn about the pumping lemma from Sipser, chapter 1.4, “Nonregular Languages”.
Reading Problem (Skeletons)
The pumping lemma and Myhill-Nerode theorem each give a unique technique for proving that a language is irregular. Give a proof skeleton for each technique. A proof skeleton for a particular proof technique is an outline of a proof using that technique, clearly indicating:
- What is generic in the proof, i.e., what parts of the skeleton hold for all claims when using this technique.
- What we must ultimately show when proving a particular claim. This part should be unique to each claim.