Next: Algorithm (2) Up: No Title Previous: From an NFA to

Algorithm

First step: For a set of states S, let closure(S) be the largest set of states, that is reachable from S using only $\epsilon$ -transitions.
Algorithm to compute T = closure(S):
$\begin{program} ~~~~~~~~T~=~S; \\ ~~~~~~~~{\vem do}~\{ \\ ~~~~~~~~~~~~~~~~T'~=~T... ...~~~~~~\} \\ ~~~~~~~~~~~~~~~~\} \\ ~~~~~~~~\}~{\vem while}~(T~!=~T')\end{program}$
This is an example of a fixpoint algorithm.

Christoph Zenger
3/23/2000