量子无穷正则语言的代数性质

Algebraic properties of quantum infinite regular languages

引入了量子Müller自动机和量子无穷正则语言的概念.注意到量子Müller自动机识别的量子无穷正则语言的像集总是有限的,借助语义分析方法和量子状态构造技术,研究了量子Müller自动机的代数刻画,即证明了任一量子Müller自动机与具有分明初状态和状态转移函数且具有量子终状态的量子Müller自动机是相互等价的;借此给出了量子无穷正则语言的代数描述和层次刻画,即任一量子无穷语言A是可识别的当且仅当A的像集有限且A可表示为有限个特殊量子无穷正则语言的并;作为应用,证明了即使量子逻辑本身缺少分配律,量子无穷正则语言关于正则运算仍然封闭.

The concepts of quantum Müller automaton and quantum infinite regular language are introduced.In virtue of the fact that the image set of a quantum infinite regular language recognized by an arbitrary quantum Müller automaton is always finite and by means of semantic analysis and quantum state construction, the algebraic characterization of quantum Müller automaton is studied.It is shown that an arbitrary quantum Müller automaton is equivalent to the one which has crisp initial states and transition relation but with quantum final states. Based on this,the algebraic description and the level characterization of quantum infinite regular languages are obtained, and it is proved that an arbitrary quantum infinite language A is recognizable if and only if the image set of A is finite and A can be represented as a finite union of special quantum infinite languages.As applications,it is proved that even if the distributivity law does not hold in quantum logic itself, quantum infinite regular languages are still closed under regular operations.