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

Порождающая грамматика состоит из четырех компонент: Г = (V, W, J, R), где V и W - непересекающиеся конечные множества, называющиеся основным и вспомогательнымалфавитами (или словарями); элементы этих множеств называются соответственно основными (или терминальными) и вспомогательными (или нетерминальными) символами; J - выделенный вспомогательный символ, называемый начальным символом; R - конечный набор правил вывода, имеющих вид j (r) y, где j и y - цепочки, состоящие из основных и вспомогательных символов.

Основные символы интерпретируются как слова языка, вспомогательные - как имена классов слов и словосочетаний, начальный символ - как символ предложения (т.е. имя класса словосочетаний, являющихся предложениями). Правила вывода описывают связи между частями предложения. Применение правила j (r) y к цепочке, имеющей вид a j b, означает преобразование ее в цепочку ay b (здесь a и b - цепочки, одна из которых или обе могут быть пустыми). Вывод в порождающей грамматике есть конечная последовательность цепочек, в которой каждая следующая цепочка получается из предыдущей использованием каких-либо правил вывода. Последняя цепочка вывода называется выводимой из первой. Цепочка основных символов, выводимая из начального символа, называется предложением, а множество всех предложений - языком, порожденным данной грамматикой.