{"id":209,"date":"2024-08-02T16:10:01","date_gmt":"2024-08-02T16:10:01","guid":{"rendered":"http:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/?page_id=209"},"modified":"2025-01-03T20:51:53","modified_gmt":"2025-01-03T20:51:53","slug":"decision-procedures","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/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-spring-2025\/wp-content\/uploads\/2025\/01\/dfa-decision-procedures.pdf\">decision procedures<\/a>. <\/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. Refer back to Sipser to the definition of acceptance. Does it match the one presented in this reading? Where in previous reading(s) have you seen ideas about reducing finite automata? How is &#8230; <a title=\"Decision Procedures\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/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-spring-2025\/wp-json\/wp\/v2\/pages\/209","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/comments?post=209"}],"version-history":[{"count":9,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/209\/revisions"}],"predecessor-version":[{"id":393,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/209\/revisions\/393"}],"up":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/media?parent=209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}