- Google group (mailing list) for this class
- math304-01-spr16-googlegroup@geneseo.edu
- Also shares this document
- Section 1.2 “Equivalence of NFAs and DFAs”
- Corresponding DFA for every NFA
- Proof is constructive
- Sets of NFA states = DFA states
- k states implies at most 2k DFA states
- epsilon transitions are tricky, modeled by E( q ) = set of states reachable from q via ε transitions (aka epsilon-closure of q)
- Examples
- Hardware example
- Corresponding DFA
- Show that the language over {a,b,c,d} consisting of strings containing no
more than 3 of the alphabet symbols is regular
- e.g., aabac, aa, bdcbdbb, ε
- But not abcd
- Idea: design an NFA to recognize the language, then conclude that there is also a DFA and therefore language is regular
- Idea behind NFA is to nondeterministically guess which symbol isn’t used
- Hardware example
- Some closure properties of set of regular languages
- Read section 1.1 “The Regular Operations” and section 1.2 “Closure Under the Regular Operations”