  To study quantum computation, it might be helpful to generalize structures
from language and automata theory to the quantum case. To that end, we propose
quantum versions of finite-state and push-down automata, and regular and
context-free grammars. We find analogs of several classical theorems, including
pumping lemmas, closure properties, rational and algebraic generating
functions, and Greibach normal form. We also show that there are quantum
context-free languages that are not context-free.
