论文部分内容阅读
本文讨论了正则语言的特征标c以及它的生成正则文法的变量个数n和其接受有限自动机的状态个数S（NM）之间的关系。得到了不等式n≥[log2c-1],S（NM）≥[log2c-1]。并且证明了,对任意整数 c>2,常存在这样的正则语言,此语言具特征标c,并恰能被一个含变量个数为[（log2c）-1]的正则文法生成。