On the Size of Unary Probabilistic and Nondeterministic Automata
We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pia accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower hound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.
nondeterministic automata probabilistic automata descriptional complexity unary languages