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