regex - 有限和无限语言混淆

Question

我最近开始学习形式语言理论，并在有限和无限语言方面遇到了一些问题。

有人告诉我，所有有限语言都是规则的。

然而，通读给我的笔记，一个带有产生式的语法：

S --> ab

S --> aabb

S --> aaabbb

尽管产生的字符串数量有限，但它不是常规语言。

但是，产生式的语法：

S --> Sb

S --> Tb

T --> Ta

T --> a

它生成 a^mb^n 形式的字符串，这是一个无限的字符串列表，但这种语言被定义为常规语言？

谁能帮我简单理解一下？在我苦苦挣扎时将不胜感激。

Answer 1

理论上的问题可能会在https://cs.stackexchange.com/中得到更快的答案，但是仍然有人可以在这里回答。

您忘记了关系不是对称的。所有有限语言都是正则的，但并非所有正则语言都是有限的。同样，所有常规语言都是上下文无关的，但并非所有上下文无关语言都是常规语言。Cleaveland, JC & Uzgalis, RC (1977) Grammars For Programming Languages , Elsevier North Holland, pp.20 很好地说明了这种关系：