Классы граммитик. 
Языковые способности человека по Хомскому

Грамматика представляет собой конечное описание формального языка. Формальный язык, в свою очередь, является произвольным множеством цепочек, составленных из символов некоторого конечного алфавита. Произвольность множества здесь понимается в том смысле, что оно может быть бесконечным, конечным или пустым.

Формализм порождающих грамматик Хомского был введен Ноамом Хомским в конце 50-х годов прошлого века. За короткое время этот формализм обрел необычайную популярность. Некоторое время порождающие грамматики рассматривались как панацея — универсальный подход для задания всевозможных языков, в том числе и естественных (т.е. языков, которые люди используют для повседневного общения между собой). Но время показало, что порождающие грамматики для описания естественных языков не очень удобны. Сейчас порождающие грамматики применяются, в основном, для описания синтаксиса формальных языков, подобных языкам программирования и другим компьютерным языкам.

Порождающая грамматика Хомского задается как множество «правил порождения» (продукций). Каждое правило является просто парой цепочек (w', w'') и задает возможность замены левой цепочки на правую при генерации цепочек языка, задаваемого грамматикой. По этой причине, правила обычно записывают в виде w' —> w'', указывая конкретно, что на что можно заменять. Множество правил в грамматике должно быть непустым и конечным, и обычно обозначается латинской P.

Цепочки в правилах грамматики могут быть составлены из символов двух алфавитов: алфавита терминальных символов (терминалов) и алфавита нетерминальных символов (нетерминалов). Алфавит терминалов обозначают через T. Этот алфавит на самом деле совпадает с алфавитом того формального языка, который задает данная грамматика. Смысл термина «терминальный» состоит в том, что в правилах грамматики в левой части не может быть цепочек, которые составлены только из терминальных символов. Поэтому, если такая цепочка получилась в результате подстановки, то следующая процесс порождения цепочки остановится (terminate). Нетерминальные символы используются в промежуточных порождениях цепочек. Смысл нетерминала в задании алгоритма порождения цепочки может быть самый разный и обычно зависит от типа грамматики, в которой этот символ используется. Различные примеры использования нетерминальных символов будут рассмотрены ниже.

Но один нетерминальный символ всегда имеет один и тот же смысл — он обозначает все цепочки языка. Называется этот нетерминал «начальным нетерминальным символов порождающей грамматики» и обычно обозначается посредством латинского S (start или sentence). В каждой порождающей грамматике обязательно должно быть правило, к которого левая часть состоит из единственного начального нетерминала, иначе в данной грамматике нельзя будет породить даже одной цепочки.

Итак, порождающая грамматика Хомского — это четверка.

G = {N, T, P, S},.

N — конечный алфавит нетерминальных символов.

T — конечный алфавит терминальных символов (совпадает с алфавитом языка, задаваемого грамматикой).

P — конечное множество правил порождения.

S — начальный нетерминал грамматики G.

Ноам Хомский ввел классы грамматик (и соответствующие классы языков) задавая ограничения на вид правил порождающей грамматики. Каждый класс грамматик имеет свою описательную мощность. Описательную мощность класса грамматик можно охарактеризовать, как возможность выражений в правилах грамматики определенных синтаксических отношений. Рассмотрим, как классы грамматик задают синтаксические отношения.