Next: DFA Construction Up: No Title Previous: Algorithm (2)

Simulating a DFA

Using the machinery developed so far, we can already simulate a DFA, given an NFA.
Let s be the start state. Then the simulation works as follows
$\begin{program} d~=~closure(\{s\}); \\ {\vem while}~(ch~!=~EOF)~\{ \\ ~~~~~~~~d~=~DFAedge(d,~ch); \\ ~~~~~~~~nextCh(); \\ \}\end{program}$
Manipulating these sets at runtime is still very inefficient.

Christoph Zenger
3/23/2000