Determinization

Next: Minimization Up: Operations on Finite Automata Previous: Regular expressions

Determinization

The -d option is used to determinize a finite state automaton. Standard input consists of the finite-state automaton to be determinized. The determinized finite-state automaton is written to standard output. The determinization algorithm uses a version of the subset construction (Hopcroft and Ullman [6]) in which only those subsets are considered that can be reached from an initial state. Example:

% fsa -d aabbaabb.nd | fsa -tex -q 0 > aabbaabb.pic

(23)

This results in the following L^ATEX picture of the determinized automaton:
$\begin{picture} (750,100)(-30,-225) \par % state q0 \put(20,-200){\circle*{8}} \... ...){0}} \thinlines\put(670.0,-225.0){\makebox(0,0){\footnotesize b}} \end{picture}$

Noord G.J.M. van
1998-09-28