{"id":204,"date":"2024-08-02T15:49:34","date_gmt":"2024-08-02T15:49:34","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=204"},"modified":"2024-08-02T17:19:36","modified_gmt":"2024-08-02T17:19:36","slug":"sipser-1-2","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-1-2\/","title":{"rendered":"Sipser 1.2"},"content":{"rendered":"<p>Read Sipser &sect; 1.2. (You can just skim the section on Equivalence of NFAs and DFAs.)<\/p>\n<ol>\n<li> Explain in your own words why every deterministic finite automaton is also a nondeterministic finite automaton.\n <\/li>\n<li> Explain, in your own words, in what ways the epsilon (empty string) comes into play in Figure 1.29. <\/li>\n<li> Suppose we added epsilon to the labels on the arrows going from q2 to q3 and from q3 to q4 in machine N2 in Figure 1.31. So both arrows would then have the label 0,1,epsilon, instead of just 0,1. What language would N2 recognize with this modification? <\/li>\n<li> What is P(Q), if Q = {0,1}? <\/li>\n<li> Describe how the proofs of Theorem 1.45 and Theorem 1.25 are similar and dissimilar.<\/li>\n<li>After reading through the proofs of Theorem 1.45, 1.47, and 1.49 (closure proofs), how would you summarize the technique? <\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect; 1.2. (You can just skim the section on Equivalence of NFAs and DFAs.) Explain in your own words why every deterministic finite automaton is also a nondeterministic finite automaton. Explain, in your own words, in what ways the epsilon (empty string) comes into play in Figure 1.29. Suppose we added epsilon to &#8230; <a title=\"Sipser 1.2\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-1-2\/\" aria-label=\"Read more about Sipser 1.2\">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-204","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/204","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=204"}],"version-history":[{"count":2,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/204\/revisions"}],"predecessor-version":[{"id":230,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/204\/revisions\/230"}],"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=204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}