{"id":209,"date":"2024-08-02T16:10:01","date_gmt":"2024-08-02T16:10:01","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=209"},"modified":"2024-09-16T18:22:20","modified_gmt":"2024-09-16T18:22:20","slug":"decision-procedures","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/decision-procedures\/","title":{"rendered":"Decision Procedures"},"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>Review the closure proofs for DFAs, NFAs, and regular expressions found between in Sipser \u00a7 1.1 to 1.3. Then read about <a href=\"http:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-content\/uploads\/2022\/02\/dfa-decision-procedures.pdf\">Decision Procedures<\/a>. (NOTE: there is a typo on page 1. In the first paragraph in the section titled\u00a0<strong>Emptiness and Acceptance<\/strong>, the word\u00a0<em>rejected<\/em> should be replaced by\u00a0<em>accepted.<\/em>)<\/p>\n<ol>\n<li>Refer back to Sipser to the definition of acceptance. Does it match the one presented in this reading?<\/li>\n<li>Where in previous reading(s) have you seen ideas about reducing finite automata? How is it different than the description of minimizing a DFA in the reading?<\/li>\n<li>Describe, in your own words, how the table-filling algorithm works, and what it does.<\/li>\n<li>The *complement* of a language is defined to be the set of strings *not* in the language:<\/li>\n<\/ol>\n<p><img decoding=\"async\" id=\"output\" src=\"https:\/\/latex.codecogs.com\/svg.image?\\overline{L}=\\{w\\mid%20w\\not\\in%20L\\}\" alt=\"equation\" \/><\/p>\n<p>Which language model (DFA, NFA, or regular expression) would you use to prove closure in this case?<br \/>\nHow do you transform an instance of this model into one that recognizes its complement?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Review the closure proofs for DFAs, NFAs, and regular expressions found between in Sipser \u00a7 1.1 to 1.3. Then read about Decision Procedures. (NOTE: there is a typo on page 1. In the first paragraph in the section titled\u00a0Emptiness and Acceptance, the word\u00a0rejected should be replaced by\u00a0accepted.) Refer back to Sipser to the definition of &#8230; <a title=\"Decision Procedures\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/decision-procedures\/\" aria-label=\"Read more about Decision Procedures\">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-209","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/209","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=209"}],"version-history":[{"count":8,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/209\/revisions"}],"predecessor-version":[{"id":358,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/209\/revisions\/358"}],"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=209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}