ГРАММАТИКА ФОРМАЛЬНАЯ

ГРАММАТИКА ФОРМАЛЬНАЯ — собирательный термин нескольких типов математико-логических исчислений. Основным объектом приложений Г. ф. и одновременно источником идей теории Г. ф. является математическая лингвистика (см. Математическая лингвистика).

Одним из основных типов Г. ф. является порождающая грамматика, которой называется четверка , где  и  — конечные непересекающиеся множества, называемые соответственно основным и вспомогательным словарями (алфавитами) грамматики  — начальный символ грамматики  и  — конечное множество правил грамматики . Правила грамматики  имеют вид , где  и  — слова в алфавите  и символ  и по определению слово  считается непосредственно выводимым из слова  в грамматике . Далее определяются вообще выводимые слова в , а множество всех выводимых слов называется языком, порождаемым Г. ф. .

Систематическое изучение Г. ф. было начато в 50-х годах XX в. Н. Хомским. Дальнейшие сведения по Г. ф. читатель найдет в соответствующей литературе.