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