CSC362 2011F, Class 10: From Specification to Optimal DFA (2)
Overview:
* Examples.
* From NFA to DFA.
* From DFA to optimal DFA.
* Lexical analysis using finite automata.
Admin:
* No new assignment right now. Just keep reading in the book.
* EC for town hall meeting next week. (You should go anyway - What Kington has to say about the budget it interesting and important.)
* EC for next week's CS extra on Grad School in CS.
* EC for Bread and Puppets on Monday.
* We hope AH feels better!
* We hope GMJ and the football team do well this weekend!
* We hope the other missing students are okay, too.
An example
* (a(ba)*a)|(b(ab)*b)
From NFA to DFA
* While we can implement the NFA by parallel processing, it's difficult
* Better to translate the NFA into a DFA.
* Strategy: In effect simulate the threads of the parallel processed NFA.
* Simple states in the NFA
* Compound states in the DFA
* A set of states that the different threads *could* be in at this
point of the computation
* Since there are only finitely many states in the NFA, there are only
finitely many states in the DFA.
* DFA has five things
* alphabet - in this case, same as the NFA and regexp
* set of states
* start state
* transition function from state x symbol -> state
* set of final states
Start state:
* Start with the start state of the NFAa
* Add anything reachable with only epsilon transitions
Other states and transition function
* As long as we have an unprocessed state in the DFA
* For each symbol in the alphabet
* Add an edge labeled by that symbol
* Build a new set which is the result of following the edge
labeled by that symbol in the NFA from each NFA state.
* Add all the states reachable by epsilon transitions
Final states
* Any set in the DFA that contains a final state in the NFA is a final
state.
Potentially, the DFA is huge
* n states in the NFA, 2^n states in the DFA.
Can we make it smaller?
* Yes!
* We can even optimize it
* How? We start by over-optimizing and then refine
* Once again, sets of states!
* Sets of states from the original DFA.
* Start with two states: One consisting of nonfinal states, one
consisting of final states.
* How do know if this split is "wrong" (an oversimplification)
* How do we build the transition function?
From DFA to Optimal DFA