1997/07/16 by Cristopher Moore, James P. Crutchfield, Moore, Cristopher +1 · 6 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.quant-ph/9707031
21 pages
arxiv created 1997/07/16 · openalex publication_date 1997/07/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.