为何给定产生式对应的最受限语言非正则而是上下文无关？

1. 产生式对应的语言类型判断 #

你给出的产生式规则是：

S → aSb | ab

它生成的语言是 {aⁿbⁿ | n≥1}，在乔姆斯基层级里，这属于上下文无关语言（2型语言），也是它能归属的最受限类型——正则语言（3型）搞不定它，但它又符合上下文无关文法的要求（产生式左部只有单个非终结符）。

2. 聊聊“计数部分字符串以生成剩余部分” #

就拿这个例子说事儿：

• 正则语言靠有限自动机运行，这玩意儿只有有限个状态，最多能记录固定数量的信息，根本扛不住无限增长的计数需求。比如要生成aⁿbⁿ，n可以是任意正整数，有限状态没法记住已经生成了多少个a，自然没法保证后面的b数量和a完全匹配。
• 而这个文法里的递归规则S→aSb，每执行一次递归，就给当前字符串左边加个a、右边加个b。这个递归过程其实就是偷偷“数着”a的数量：每加一个a，就给后面预留了一个必须对应的b的位置，直到触发终止规则S→ab，最终生成的字符串里a和b的数量肯定完全一致。这就是“计数部分字符串以生成剩余部分”的核心——生成前半段（a序列）时，得记录它的数量，用来约束后半段（b序列）的生成，确保两者数量对等。

内容的提问来源于stack exchange，提问作者Lorenzo