有限语言与无限语言混淆

Question

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

有人告诉我，所有有限的语言都是固定的。

然而，阅读给我的笔记，一种有成果的语法：

S --> ab

S --> aabb

S --> aaabbb

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

然而，一个语法与产品：

S --> Sb

S --> Tb

T --> Ta

T --> a

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

有人能帮我简单地理解吗？当我挣扎的时候我会很感激的。

Answer 1

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

你忘了这种关系是不对称的。所有有限的语言都是正则的，但并不是所有的正则语言都是有限的。同样，所有普通语言都是上下文自由的，但并不是所有上下文无关的语言都是规则的。这种关系在Cleaveland，J.C. & Uzgalis，R.C. (1977)编程语言的语法中得到了很好的说明，Elsevier North Holland，第20页：

​

​