有限和無限語言混淆

Question

我最近開始學習形式語言理論，並遇到了有限和無限語言的一些問題。

我被告知所有有限的語言都是常規的。

然而，通讀給我的，語法與製作筆記：

S --> ab 

S --> aabb 

S --> aaabbb 

不是正規的語言雖然製作生成的字符串的數量有限。

然而，隨着製作一個語法：

S --> Sb 

S --> Tb 

T --> Ta 

T --> a 

哪個生成形式的^ M B^N，這是還沒有這種語言被定義爲正則字符串無窮列表的字符串？

誰能幫我理解一下嗎？當我掙扎時會非常感激。

Answer 1

關於理論的問題可能會在https://cs.stackexchange.com/中得到更快的答案，但仍有人可以在這裏回答。

你忘記了這種關係是不對稱的。所有有限的語言都是規則的，但並非所有的正規語言都是有限的同樣，所有常規語言都是上下文無關的，但並非所有上下文無關語言都是常規語言。這種關係在Cleaveland很好地說明，J.C. & Uzgalis，R.C. （1977年）文法編程語言，愛思唯爾北荷蘭，pp.20：