基于量子逻辑的下推自动机的代数刻画

摘要

首先,本文提出量子下推自动机(简记为L-VPDA)的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA问的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。