On the degree of ambiguity of finite automata (Q1177168)

Nondeterministic finite automata are subject of the paper. The degree of ambiguity for a nondeterministic automaton is defined as the supremum of the number of paths for the accepting input words. The main established results are: the degree of ambiguity of a finite nondeterministic automaton with \(n\) states is \(5^{n/2}\cdot n^ n\); there exists a polynomial time criterion, characterizing automata. Polynomial time algorithms are proposed for computing the degree of growth (polynomial or exponential) of the ambiguity.