Review the closure proofs for DFAs, NFAs, and regular expressions found between in Sipser § 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 Emptiness and Acceptance, the word rejected should be replaced by accepted.)
- 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 it different than the description of minimizing a DFA in the reading?
- Describe, in your own words, how the table-filling algorithm works, and what it does.
- The *complement* of a language is defined to be the set of strings *not* in the language:
Which language model (DFA, NFA, or regular expression) would you use to prove closure in this case?
How do you transform an instance of this model into one that recognizes its complement?
