{"id":217,"date":"2024-08-02T16:31:41","date_gmt":"2024-08-02T16:31:41","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=217"},"modified":"2024-08-02T16:36:42","modified_gmt":"2024-08-02T16:36:42","slug":"sipser-1-4","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-1-4\/","title":{"rendered":"Sipser 1.4"},"content":{"rendered":"

Read Sipser § 1.4<\/p>\n

    \n
  1. After reading the proof of the pumping lemma, explain in your own words why the pigeonhole principle is needed.\n
  2. After reading examples 1.73 \u2013 1.76, describe how to use the pumping lemma to show that a language is not regular.\n
  3. Describe the technique of \u201cpumping down\u201d.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    Read Sipser § 1.4 After reading the proof of the pumping lemma, explain in your own words why the pigeonhole principle is needed. After reading examples 1.73 \u2013 1.76, describe how to use the pumping lemma to show that a language is not regular. Describe the technique of \u201cpumping down\u201d.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":29,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-217","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/217","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/comments?post=217"}],"version-history":[{"count":1,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/217\/revisions"}],"predecessor-version":[{"id":218,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/217\/revisions\/218"}],"up":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/media?parent=217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}