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

doi:10.3778/j.issn.1002-8331.2011.03.014

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (3): 47-50.DOI: 10.3778/j.issn.1002-8331.2011.03.014

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

韩召伟^1，2，韩召莹³

1.陕西师范大学数学与信息科学学院，西安 710062
2.陕西师范大学计算机科学学院，西安 710062
3.西安石油大学理学院，西安 710065

收稿日期:2009-05-13 修回日期:2009-07-22 出版日期:2011-01-21 发布日期:2011-01-21
通讯作者: 韩召伟

Algebraic characterizations of context-free languages based on Lukasiewicz logic

HAN Zhaowei^1，2，HAN Zhaoying³

1.College of Mathematics and Information Science，Shaanxi Normal University，Xi’an 710062，China
2.College of Computer Science，Shaanxi Normal University，Xi’an 710062，China
3.School of Science，Xi’an Shiyou University，Xi’an 710065，China

Received:2009-05-13 Revised:2009-07-22 Online:2011-01-21 Published:2011-01-21
Contact: HAN Zhaowei

摘要/Abstract

摘要：

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

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

Abstract: 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.

Key words: Lukasiewicz logic, Lukasiewicz lattice-Valued Pushdown Automata (l-VPDA), Lukasiewicz lattice-valued context-free language, algebraic characterization

中图分类号:

韩召伟^1，2，韩召莹³. Lukasiewicz逻辑值上下文无关语言的代数刻画[J]. 计算机工程与应用, 2011, 47(3): 47-50.

HAN Zhaowei^1，2，HAN Zhaoying³. Algebraic characterizations of context-free languages based on Lukasiewicz logic[J]. Computer Engineering and Applications, 2011, 47(3): 47-50.

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

Algebraic characterizations of context-free languages based on Lukasiewicz logic

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics