Lukasiewicz逻辑值上下文无关语言的代数刻画

Algebraic characterizations of context-free languages based on Lukasiewicz logic

提出了基于Lukasiewicz逻辑的下推自动机(l-VPDA)的概念,从代数角度研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用模糊状态构造,证明了任意以终状态方式接受模糊语言的l-VPDA与状态转移为经典函数且具有l值模糊终状态的l-VPDA间的相互等价性;并证明任意以空栈方式接受模糊语言的l-VPDA与状态转移除一步转移为模糊的以外,其余都是经典函数的l-VPDA是相互等价的;详细研究了l-值模糊上下文无关语言的代数和层次刻画,以及对于正则运算的封闭性。

This paper introduces,the notion Lukasiewicz lattice-valued pushdown automaton（l-VPDA）,traverses some algebraic properties of these automata in details and also establishes the algebraic features of these automata,i.e,by using the means of fuzzy state construction,and proves the fact that an arbitrary l-VPDA which accepts the l-valued language by final states and the other l-VPDA with the crisp transition relation and fuzzy final states are equivalently constructed,and also shows that an arbitrary l-VPDA can accept the same l-valued language by empty stack and by one l-VPDA with the crisp transition relation except one step with fuzzy transition relation in the mean time.It also discusses some algebraic and level characterizations of l-valued context-free languages,and deals with the closed properties of these l-valued languages under some regular operations in particular at the same time.