  The nondeterministic quantum finite automaton (NQFA) is the only known case
where a one-way quantum finite automaton (QFA) model has been shown to be
strictly superior in terms of language recognition power to its probabilistic
counterpart. We give a characterization of the class of languages recognized by
NQFA's, demonstrating that it is equal to the class of exclusive stochastic
languages. We also characterize the class of languages that are recognized
necessarily by two-sided error by QFA's. It is shown that these classes remain
the same when the QFA's used in their definitions are replaced by several
different model variants that have appeared in the literature. We prove several
closure properties of the related classes. The ramifications of these results
about classical and quantum sublogarithmic space complexity classes are
examined.
