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