Language Recognition by Generalized Quantum Finite Automata with Unbounded Error
Abuzer Yakaryılmaz, A. C. Cem Say · 2009
Abstract. We prove that the class of languages recognized by generalized quantum finite automata (GQFA’s) with unbounded error equals the class of stochastic languages. The capability of performing additional intermediate projective measurements does not increase the recognition power of GQFA’s over Kondacs-Watrous quantum finite automata in this setting. Unlike their probabilistic counterparts, allowing the tape head to stay put for some steps during its traversal of the input enlarges the class of languages recognized by GQFA’s with unbounded error. 1