  This paper presents and analyzes an incremental algorithm for the
construction of Acyclic Non-deterministic Finite-state Automata (NFA). Automata
of this type are quite useful in computational linguistics, especially for
storing lexicons. The proposed algorithm produces compact NFAs, i.e. NFAs that
do not contain equivalent states. Unlike Deterministic Finite-state Automata
(DFA), this property is not sufficient to ensure minimality, but still the
resulting NFAs are considerably smaller than the minimal DFAs for the same
languages.
