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

Algebraic characterizations of context-free languages based on Lukasiewicz logic

作　　者：韩召伟[1,2] 韩召莹[3] 

机构地区：[1]陕西师范大学数学与信息科学学院,西安710062 [2]陕西师范大学计算机科学学院,西安710062 [3]西安石油大学理学院,西安710065

出　　处：《计算机工程与应用》2011年第3期47-50,119,共5页Computer Engineering and Applications

基　　金：陕西师范大学青年科技项目(No.200701008)

摘　　要：提出了基于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.

关 键 词：Lukasiewicz逻辑 l值下推自动机 l值模糊上下文无关语言 代数刻画 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O153.1[自动化与计算机技术—计算机科学与技术]