Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (3): 47-50.DOI: 10.3778/j.issn.1002-8331.2011.03.014

• 研究、探讨 • Previous Articles     Next Articles

Algebraic characterizations of context-free languages based on Lukasiewicz logic

HAN Zhaowei1,2,HAN Zhaoying3   

  1. 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



  1. 1.陕西师范大学 数学与信息科学学院,西安 710062
    2.陕西师范大学 计算机科学学院,西安 710062
    3.西安石油大学 理学院,西安 710065
  • 通讯作者: 韩召伟

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



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

CLC Number: