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