Today in 362: From Regular Expressions to DFA

Admin
  HW1 Assigned (problems from The Red Dragon)
               (no, not the Thomas Harris Book)
  Try not to miss lab
  Any observations from yesterday's lab? [Friday]
  Picnic
  Compilers, phase 1, coming soon
  Missing: Erik, Mark, Ananta

Overview
  Review of our plans
  From regexp to NFA
  Example
  From NFA to DFA
  Example, continued

We know how to write regular expressions for the
tokens of a language; we'd like to have programs
that do the tokenizing.  So, we need to go from
regular expression to "program".
* Step 1: Convert regular expression(s) to NFA
* Step 2: Convert NFA to DFA
* Step 3: Optimize the DFA

From RegExp to NFA
* Reminder: Build NFA with 1 start state , 1 final state
* See the "physical whiteboard"

From NFA to DFA
* We can use Daren's idea of "see what states you might be
  in" to turn any NFA into a DFA.
* The states of the DFA are sets of NFA states
* There is a transition in the DFA from Qi to Qj if
  exist qi in Qi and qj in Qj and there's an edge from
  qi to qj in the NFA.
* A state of the DFA is final if it contains a final NFA
  state.
* Construction:
  + Start at the start state: Q0 = { q0 }
  + Add any place you can go for free
    Q0 = epsilon-closure(Q0)
  + While unprocessed states, Qu, remain, compute
    transitions on Qu
* To compute transitions on Qu
    For each symbol, s, in Sigma
      Create a new, temporary, set of states Qt
      For each state qi in Qu,
        If there's a transition from qi to qj on s in
        NFA, add qj to Qt
      Qt = epislon-closure(Qt)
      If Qt = Qx for some already constructed state Qx,
        Add Qu->Qx on input of s to DFA
      Otherwise 
        Add Qu->Qt on input of s to DFA
        Add Qt to the list of unprocessed states