Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Sets:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaneous:
[2001S]
[98F]
[SamR]
[Glimmer Labs]
Back to Finite Automata. On to From Specification to Optimal DFA, Continued.
Held Wednesday, September 11, 2002
Summary
Today we start to consider how to move from the readable but declarative regular expression notation to the executable but obtuse finite automaton notation.
Notes
Assignments
Overview
optimizethe DFAs.
on the fly.
integers in C
Q0 = { q0 } // but there are some states we can reach from q0 at no cost Q0 = epsilon-closure(Q0) while there are states we haven't processed pick one such state, Qn for each symbol s let tmp be a new, empty, set for each q in Qn add delta(q,s) to tmp end for tmp = epsilon-closure(tmp) if tmp is not in the DFA then let Qi be a new state Qi = tmp add Qi to the DFA else let Qi be the state equivalent to tmp end if add an edge from Qn to Qi in the automaton end for end while for each Qi if there is a q in Qi that is a final state then Qi is a final state end if end for
Back to Finite Automata. On to From Specification to Optimal DFA, Continued.
Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Sets:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaneous:
[2001S]
[98F]
[SamR]
[Glimmer Labs]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Fri Dec 6 10:37:57 2002.
The source to the document was last modified on Wed Sep 4 10:08:33 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.06.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby