聖塔非研究所 量子自動機與量子語法 2026-03-18 · 工作論文 · 更新 2026/03/18 下午11:16 摘要 為了研究量子計算，將語言和自動機理論的結構推廣到量子情況可能會有所幫助。為此，我們提出了有限狀態和下推自動機的量子版本，以及常規和上下文無關語法。我們發現了幾個經典定理的類似物，包括泵引理、閉包性質、有理和代數生成函數以及格雷巴赫範式。我們也表明，存在一些並非上下文無關的量子上下文無關語言。 原文連結PDF 來源 本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。 原文連結 原文連結 PDF 來源 論文資訊 類型：工作論文 編號：工作論文 #1134 日期：2026-03-18 摘要 為了研究量子計算，將語言和自動機理論的結構推廣到量子情況可能會有所幫助。為此，我們提出了有限狀態和下推自動機的量子版本，以及常規和上下文無關語法。我們發現了幾個經典定理的類似物，包括泵引理、閉包性質、有理和代數生成函數以及格雷巴赫範式。我們也表明，存在一些並非上下文無關的量子上下文無關語言。