Reducing Nondeterministic Finite Automata

📄 Project Abstract

A finite automaton is an abstract computing machine, containing a set of "states", and describing a language. At any time, the automaton is in a fixed state, and an input event corresponding to a symbol makes it switch to another state. Nondeterminism allows these machines to be in several states at once, although this does not make them more powerful: the languages recognized are the regular languages in both deterministic and nondeterministic cases. Still nondeterministic finite automata (NFAs) are interesting, because for a given language they can be smaller than the minimum deterministic finite automaton describing the same language, and this could save some execution time for the applications using them. This project aims to explore ways of reducing the size of NFAs. After research into possible techniques, an implementation work was done to apply these techniques and to help evaluate their actual efficiency.