摘要
在正规文法的基础上,通过增加一个约束变量集合,给出了二元文法的定义,证明了二元文法与袋自动机的等价性,定义了平衡推导、递增推导、递减推导和传递推导,证明了它们与不变重复序列、增重复序列、减重复序列和传递重复序列之间的关系,并且给出判定一个二元文法所产生语言(袋语言)分别是正规语言、上下文无关语言或上下文有关语言的充分条件。
The concept of binary grammar is presented, and it is shown that the languages accepted by bag automata are exactly the languages generated by binary grammar. The concepts of balanced derivations, increasing derivations, decreasing derivations and transitive derivations are defined. A set of necessary and sufficient conditions for determining a bag language to be a regular language, a context-free language or a context-sensitive language are given.
出处
《计算机工程与科学》
CSCD
2008年第11期95-97,117,共4页
Computer Engineering & Science
基金
国家自然科学基金资助项目(60673053)
关键词
二元文法
袋自动机
袋语言
推导
binary grammar
bag automata
bag language
derivation
