Конечная и Бесконечная языковая путаница

Question

Недавно я начал изучать теорию формального языка и столкнулся с некоторыми проблемами с конечными и бесконечными языками.

Мне сказали, что все конечные языки являются регулярными.

Однако, читая записки, данные мне, грамматика с постановками:

S --> ab

S --> aabb

S --> aaabbb

Не является обычным языком, хотя произведения генерируют конечное число строк.

Однако грамматика с постановками:

S --> Sb

S --> Tb

T --> Ta

T --> a

Какие генерируют строки вида a^m b^n, который представляет собой бесконечный список строк, но этот язык определен как обычный?

Может ли кто-нибудь помочь мне понять простыми словами? Был бы очень признателен, как я борюсь.

Answer 1

Вопросы по теории могут получить более быстрые ответы на https://cs.stackexchange.com/, однако есть еще люди, которые могут ответить здесь.

Вы забываете, что отношения не симметричны. Все конечные языки регулярны, но не все регулярные языки конечны. Точно так же все обычные языки являются контекстно-свободными, но не все контекстно-свободные языки являются регулярными. Отношения хорошо проиллюстрированы в Cleaveland, JC & Uzgalis, RC (1977) Grammars For Programming Languages, Elsevier North Holland, pp.20: