Sipser 1.4

Read Sipser § 1.4

  1. After reading the proof of the pumping lemma, explain in your own words why the pigeonhole principle is needed.
  2. After reading examples 1.73 – 1.76, describe how to use the pumping lemma to show that a language is not regular.
  3. Describe the technique of “pumping down”.
css.php
The views and opinions expressed on individual web pages are strictly those of their authors and are not official statements of Grinnell College. Copyright Statement.