Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (4): 42-46.DOI: 10.3778/j.issn.1002-8331.2011.04.012

• 研究、探讨 • Previous Articles     Next Articles

Algebraic properties of context-free grammar based on quantum logic

SONG Xiaozhen1,2,HAN Zhaowei1,LI Yongming3   

  1. 1.College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,China
    2.Department of Mathematics,Yulin University,Yulin,Shaanxi 719000,China
    3.College of Computer Science,Shaanxi Normal University,Xi’an 710062,China
  • Received:2009-09-09 Revised:2009-10-29 Online:2011-02-01 Published:2011-02-01
  • Contact: SONG Xiaozhen

量子上下文无关文法的代数性质

宋小震1,2,韩召伟1,李永明3   

  1. 1.陕西师范大学 数学与信息科学学院,西安 710062
    2.榆林学院 数学系,陕西 榆林 719000
    3.陕西师范大学 计算机科学学院,西安 710062
  • 通讯作者: 宋小震

Abstract: The concept of orthomodular lattice-Valued Context-Free Grammar (l-VCFG) is proposed and its algebraic properties are investigated.It is shown that orthomodular lattice-Valued Chomsky Normal Forms (l-VCNF) and orthomodular lattice-
Valued Greibach Normal Forms (l-VGNF) of l-VCFG are mutually equivalent.The related transformations are constructed in the meantime.Some algebraic and level characterizations of orthomodular lattice-valued context-free languages are presented,and the closed properties of this l-valued languages under some regular operations are studied at the same time.

Key words: quantum logic, orthomodular lattice, orthomodular lattice-valued context-free grammar, orthomodular lattice-valued context-free language

摘要:

提出了量子上下文无关文法(l-VCFG)的概念,并研究了其具有的代数性质;证明了量子上下文无关文法(l-VCFG)和Chomsky范式文法(l-VCNF)以及Greibach范式文法(l-VGNF)的相互等价性;详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。

关键词: 量子逻辑, 正交模格, 量子上下文无关文法, 量子上下文无关语言

CLC Number: