乔姆斯基-许岑贝格尔枚举定理
2024-06-30
乔姆斯基-许岑贝格尔枚举定理是诺姆·乔姆斯基和马塞尔-保罗·许岑贝格尔推导出的关于由明确的上下文无关文法生成的给定长度的单词数量的定理。该定理提供了形式语言理论和抽象代数之间的一个意想不到的联系。该定理指出，如果一种语言可由明确的上下文无关文法生成，那么描述该语言中具有给定长度的单词数量的生成函数是满足特定多项式方程的代数函数。
67