Порождающие грамматики Хомского

Чтобы применить математический подход к проблемам, связанным с языками и их обработкой, мы должны ограничиться множеством цепочек, которые можно определить некоторым точным образом.

Есть много способов точного задания таких множеств. Один способ, например, заключается в задании языка как множества, допускаемого каким-нибудь распознавателем цепочек вроде конечного автомата или автомата с магазинной памятью. Другой подход заключается в использовании методов, которые можно считать грамматическими.

Термин «формальная грамматика» применим к любому определению формального языка, основанному на грамматических правилах, с помощью которых можно порождать и анализировать цепочки аналогично тому, как грамматики используются при изучении естественных языков.