Beta 1


Title Implementation and analysis of NFAs with adjustable deterministic blow-up
Author Lissovoi, Andrei
Supervisor Witt, Carsten (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Bachelor thesis
Year 2010
Abstract 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.
Imprint Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Series IMM-B.Sc.-2010-15
Fulltext
Original PDF bac10_15.pdf (0.36 MB)
Admin Creation date: 2010-06-28    Update date: 2010-06-28    Source: dtu    ID: 264200    Original MXD