To study quantum computation, it might be helpful to generalize structures
from language and automata theory to the quantum case. To that end, we prop
ose quantum versions of finite-state and push-down automata, and regular an
d contest-free grammars. We find analogs of several classical theorems, inc
luding pumping lemmas, closure properties, rational and algebraic generatin
g functions, and Greibach normal form. We also show that there are quantum
context-free languages that are not context-free, so QCFL not equal CFL. (C
) 2000 Elsevier Science B.V. All rights reserved.