Basic Properties of Quantum Automata

This paper develops a theory of quantum automata and their slightly more general versions, q-automata. Quantum languages and -quantum languages, 0<1, are studied. Functions that can be realized as probability maps for q-automata are characterized. Quantum grammars are discussed and it is shown that quantum languages are precisely those languages that are induced by a quantum grammar. A quantum pumping lemma is employed to show that there are regular languages that are not -quantum, 0<1.