Хомски и его иерархия грамматик⁠⁠

Предыдущая статья: Грамматика языка и порождающие грамматики. Сказ о «правильных» скобочках.

Напомню как выглядит формула порождающей грамматики: G = { T, N, P, S }

И чтобы проще было запомнить Grammar = { Terminal, Nonteminal, Production rule, Starting nonterminal} или как это выглядело бы на русском по определениям из прошлой статьи Грамматика = { Основные, Вспомогательные, Правила вывода, Начальный вспомогательный } или Г = { О, В, П, Н } или буквальный перевод Грамматика = { Конечные, Неконечные, Правила производства, Стартовый неконечный}, тогда Г = {К, Н, П, С}. Какой бы вариант вы выбрали? Можете оставить в комментариях.

Центральная идея об иерархиях заключается в том, какими правилами вывода мы пользуемся для описания языка, и вот на какие типы разделил Хомски :

Произвольные грамматики вида a → b , где a и b цепочки из основных и и/или вспомогательных (терминалов и/или нетерминалов) символов, причем цепочка а не должна быть пустой, более никаких ограничений не накладывается.

Контекстно-зависимые грамматики (КЗ-грамматика) вида aAb → ayb , где a, b, y — цепочки основных и/или вспомогательных символов. A — вспомогательный символ. Это правило гласит, что вспомогательный символ A, может быть заменен на цепочку y, только в контексте образуемом цепочками a и b.

Контекстно-свободные грамматики (КС-грамматика) вида A → y , где A вспомогательный символ, а y цепочка вспомогательный и/или основных символов. Основная особенно, то что в левой части правила, всегда только один вспомогательный символ.

Автоматные грамматики. Все правила такой грамматики имеют одну из трех форм: A → aB, A → a, A → ε , напомню что ε - это пустая цепочка.

Если вы достаточно внимательны, то можете заметить, что автоматные грамматики частный случай КС-грамматик, КС-грамматики частный случай КЗ-грамматик, КЗ-грамматики частный случай произвольных и когда говорят к примеру о КС-грамматике, говорят о грамматике не являющиеся автоматной. Фух…

Сейчас вам могут показаться эти определения абсолютно бесполезными, но они нам помогут понять конечный автомат, и в основном я буду писать о КС-грамматиках и автоматных, так как в основном они имеют практический интерес. Но перед обсуждением КА нам понадобится разобрать 2 темы, дерево вывода и задачи разбора (да, да парсинг), для чего они нужны что они такое.

З. Ы. Какому типу грамматик относится G = ( {(, )}, {S}, {S → (S), S →SS, S → ε}, S)?
Всем здоровья и улыбайтесь по чаще.