{"id":264,"date":"2024-08-02T18:30:59","date_gmt":"2024-08-02T18:30:59","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=264"},"modified":"2024-08-02T18:37:13","modified_gmt":"2024-08-02T18:37:13","slug":"sipser-5-1-5-3","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-5-1-5-3\/","title":{"rendered":"Sipser 5.1, 5.3"},"content":{"rendered":"<p><script id=\"MathJax-script\" async src=\"https:\/\/cdn.jsdelivr.net\/npm\/mathjax@3\/es5\/tex-mml-chtml.js\"><\/script><\/p>\n<p>Read Sipser &sect;5.1 and &sect;5.3. Then review this overview of <a href=\"http:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-content\/uploads\/2022\/03\/undecidable-proof-strategies.pdf\">undecidable proof strategies<\/a>.<\/p>\n<ol>\n<li> Outline the common strategy for proving that a language is undecidable.\n<li> How are computation histories used in the proofs of Theorems 5.10 and 5.13?\n<li> If $$A \u2264_m B,$$ and B is a regular language, does that imply that A is a regular language? Why or why not?\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect;5.1 and &sect;5.3. Then review this overview of undecidable proof strategies. Outline the common strategy for proving that a language is undecidable. How are computation histories used in the proofs of Theorems 5.10 and 5.13? If $$A \u2264_m B,$$ and B is a regular language, does that imply that A is a regular &#8230; <a title=\"Sipser 5.1, 5.3\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-5-1-5-3\/\" aria-label=\"Read more about Sipser 5.1, 5.3\">Read more<\/a><\/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-264","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/264","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=264"}],"version-history":[{"count":4,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/264\/revisions"}],"predecessor-version":[{"id":273,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/264\/revisions\/273"}],"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=264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}