Key Terms
Deterministic Finite State Automata (DFA), Subset construction, closure properties: union, intersection, complement
Skills to be developed
Learn to convert a given NFA into an equivalent DFA using subset construction and prove that the two indeed recognize the same language. Learn to build an NFA whose language is the union of two (or more) NFAs. Learn to construct an NFA accepting a language that is the complement of a given NFA.
References
Kozen: Lecture 2, Operation on Sets section on page 10 (to brush up set operations and De Morgan Laws) and Lecture 6(stop before -transitions on page 32
Sipser: in Section 1.2 the equivalence of NFAs and DFAs subsection on page 54
Hopcroft: Section 2.3.5 on page 60
Practice Problems
Kozen: Homework 2, question 1(pg 302)
Sipser: Exercise 1.5,1.6 (pg 84)