CSC362 2004S, Class 10: Regular Expressions to DFAs (2)
Admin:
* No class Friday.
* Questions on the homework?
Overview:
* NFA to DFA
* DFA to Optimal DFA
* Tokenizing with FA
* Limitations of REs and FA
Translating NFA to DFA
* The states in the DFA sets of states from the NFA
* How do we build the states of the DFA?
* Create the start state (Q0)
Q0 = { q0 }
Q0 = epsilon-closure(Q0);
* For each symbol, t, in the alphabet
Compute a new state from Q by
* Building a set of delta(qi in Q)
* Computing the epsilon closure of that state
* Add a transition from Q to that new state
* Repeat th is process for each new state
* How do we treat the new thing as a DFA?
/How good is our DFA? Can we make it smaller?/
* Enumerate all possible DFAs that are smaller and see if any represent the same language
* There can be a significant number of DFAs that are smaller.
* Given N states and M symbols in the alphabet, how many possible DFAs do you have?
* Each state can have M symbols coming out of it ...
* How do we determine whether two DFAs represent the same language?
* Theorem: If you apply the same algorithm to a non-minimal DFA, you'll get a smaller DFA back.
* Is this theorem correct? No: If you apply the algorithm to any DFA, you get the same DFA back.
* Theorem: If two states follow the same symbol to the same state, merge 'em
* Failure by counter-example
* Theorem: If two states have identical transitions (and the same finality), you can merge them
* True, but doesn't necessarily get you to a minimal DFA.
* The standard solution is a strange one
* Start with an overly-optimisic assumption: All nonfinal states can be merged; all final states can be merged
* Whenever you find that you're wrong, unmerge as appropriate