||Implementation and analysis of NFAs with adjustable deterministic blow-up
||Witt, Carsten (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||Non-deterministic and deterministic automata both have the expressive power
to recognize regular languages; thus, for any non-deterministic automaton there
exists an equivalent deterministic automaton that recognizes the same regular
language (and vice versa). Depending on the regular language recognized, however,
the number of states in minimal NFAs and DFAs recognizing the language
may dier signicantly; an n-state NFA can be equivalent to an DFA with as
few as n and as many as 2n states.
This project explores the question of whether there always exists an n-state
minimal NFA such that the equivalent minimal DFA has n d 2n states.
Past research has shown several methods to construct an n-state minimal NFA
for a given (n; d) pair over varying alphabet sizes; this report presents several
of those constructions and proves their correctness.
In addition, some of the constructions are implemented using Java, allowing
the NFAs for a particular (n; d) pair to be quickly constructed, visualized, and
converted to DFA or regular expressions representations.
||Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Creation date: 2010-06-28
Update date: 2010-06-28