[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Back to From Specification to Optimal DFA (1). On to Cancelled.
Held: Wednesday, 11 February 2004
Summary: Today we continue our consideration of how to move from the readable but declarative regular expression notation to the executable but sometimes obtuse finite automaton notation.
Related Pages:
Notes:
Overview:
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
Assume all non-final states can be treated as the same state Assume all final states can be treated as the same state For each group of states treated as equivalent as the same state For each symbol, s If there are two "equivalent" states q1,q2 such that edge(q1,s) and edge(q2,s) lead to non-equivalent states, split q1 and q2 into different equivalencies figure out where the other states in the original equivalency go End For // each symbol End for // each pair of states
/** * Find the first token in the candidate string, starting * at a particular position. */ public token findToken(String candidate, starting_pos) begin State current_state = q0; for i = starting_pos to the length of candidate current_state = edge(current_state,candidate.symbolAt(i)) if current_state is a final state final_found = current_state final_pos = i end if if current_state is undefined then exit the for loop end if end for if (final_found is defined) then return the token given by final_found at position final_pos else no token can be found end if end
strings of a's and b's with equal numbers of a's and b's
Back to From Specification to Optimal DFA (1). On to Cancelled.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
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 Wed May 5 11:47:00 2004.
The source to the document was last modified on Tue Jan 20 23:06:45 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.10.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby