摘要
提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.
The concepts of commutative derivation context-free grammar and of commutative derivation context-free language are presented. It is proofed that regular language and bound context-free language is a subset of the commutative derivation context-free language, while the commutative derivation context-free language is the subset of context-free language. The expression of commutative derivation context-free language is defined, and it is proofed that commutative derivation context-free grammar is equipollence with the expression of commutative derivation context-free language.
出处
《小型微型计算机系统》
CSCD
北大核心
2008年第2期368-372,共5页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(60673053)资助.
关键词
推导可交换上下文无关语言
文法
语言表达式
commutative derivation context-free language
grammar
language expression
