Зафиксируем некоторый алфавит (конечное множество) X. Элементы алфавита X будем называть обычными символами или терминалами и обозначать маленькими начальными буквами латинского алфавита: a, b, c, d,... Мы будем также рассматривать алфавит метасимволов M, множество M не пересекается с X. Элементы алфавита M будем называть метасимволами или нетерминалами; для обозначений нетерминалов мы будем использовать большие буквы латинского алфавита: A, B, C,...
Пусть Y — некоторое множество. Через Y* мы будем обозначать множество всех конечных цепочек из элементов множества Y, включая конечную цепочку.
Язык L — это некоторое подмножество множества X* всевозможных терминальных цепочек. Мы будем рассматривать только контекстно свободные языки, т.е. языки, задаваемые с помощью контекстно свободных грамматик.
Определим понятие контекстно свободной (КС) грамматики.
Определим теперь понятия вывода и языка, задаваемого КС грамматикой. Рассмотрим цепочку вида xAy. Применение правила "A->u" к этой цепочке состоит в замене метасимвола A на цепочку u, при этом получается цепочка xuy. Выводом называется последовательность применений правил к некоторой цепочке. Мы будем говорить, что получаемые в процессе вывода цепочки выводимы из начальной (эти цепочки, естественно, могут содержать терминалы и нетерминалы).
Языком, задаваемым КС грамматикой, называется множество терминальных цепочек, выводимых из начального символа грамматики.
Рассмотрим примеры.
Пример 1. Первая (плохая) грамматика языка арифметических формул.
Язык, задаваемый этой грамматикой, состоит из арифметических формул, где в качестве переменной используется единственная буква a. Примеры цепочек языка: a, a+a, a+(a*a). Приведем вывод последней цепочки:
В процессе вывода мы все время применяли замены к самому левому нетерминалу, входящему в выводимую цепочку. Такой вывод называется левым выводом. Соответственно, если заменять всегда самый правый нетерминал, то мы получим правый вывод:
Поскольку преобразования, состоящие в замене разных метасимволов, коммутируют между собой, то всякая выводимая цепочка имеет и левый, и правый выводы.
В теории формальных языков рассматривают также дерево вывода. Вот дерево вывода цепочки a+(a*a):
Корнем дерева является начальный нетерминал грамматики. Каждая нетерминальная вершина дерева отмечена некоторым метасимволом. При применении правила к метасимволу в вершине мы получаем столько веток, выходящих из этой вершины, сколько символов в правой части правила. Вершины, в которые идут эти ветки, отмечаются символами правой части правила. Обычные символы потому и называются терминалами, что им соответствуют терминальные (т.е. конечные) вершины дерева вывода. Выведенная цепочка получается прочтением терминальных вершин дерева выводе слева направо.
Для сокращения записи несколько правил с одной и той же левой частью иногда объединяют в одну запись, разделяя правые части правил вертикальной чертой "|". Например, грамматику арифметических формул можно было бы записать следующим образом.
ПРЕДЛОЖЕНИЕ. Имеется взаимно однозначное соответствие между множествам всех левых выводов цепочек языка, множеством всех правых выводов и множеством всех деревьев выводов.
ОПРЕДЕЛЕНИЕ. КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод). Язык, заданный детерминированной грамматикой, называется детерминированным.
Приведенная выше грамматика языка арифметических формул не является детерминированной. Действительно, цепочка a+a+a имеет два разных дерева вывода.
Недетерминированность грамматики — неприятное свойство, поэтому всегда стремятся найти детерминированную грамматику. Построим детерминированную грамматику языка арифметических формул.
Пример 2. Вторая (хорошая) грамматика языка арифметических формул.
Данная грамматика, кроме того, что она детерминированная, еще к тому же правильно отражает приоритет арифметических операций и общепринятый порядок выполнения равноприоритетных операций слева направо.
Метасимволы грамматики по своему смыслу связаны с существенными понятиями языка. Поэтому вместо букв в качестве метасимволов иногда используют слова, заключенные в угловые скобки или записанные курсивом. Такую форму записи грамматики иногда называют нормальной формой Бэкуса-Наура в честь филологов, придумавших ее. Пример записи второй (хорошей) грамматики арифметических формул:
Следующая лемма используется для доказательства того, что конкретный язык не является контекстно свободным.
ЛЕММА О РАЗРАСТАНИИ (в оригинале "pumping lemma", лемма о накачке). Пусть L — контекстно свободный язык. Тогда существуют такие натуральные числа K и N, что если цепочка u принадлежит языку L и имеет длину не меньше N, то
ИДЕЯ ДОКАЗАТЕЛЬСТВА (попробуйте восстановить строгое доказательство). Возьмем минимальное дерево вывода достаточно длинной цепочки. Оно должно иметь достаточно большую высоту — больше, чем число нетерминалов грамматики. Следовательно, на пути к терминальной вершине какой-то нетерминал, скажем, "A", встретится дважды.
Поддерево, корнем которого явлеется второе (нижнее) "A", можно заменить на поддерево с корнем в верхнем "A". Мы получим дерево вывода цепочки
Пример применения леммы о накачке. Покажем, что язык, состоящий из всевозможных цепочек из единиц, длины которых являются простыми числами, не является контестно свободным. Действительно, по лемме любой бесконечный КС язык содержит бесконечную последовательность цепочек, длины которых составляют арифметическую прогрессию. Но последовательность простых чисел не содержит никакой бесконечной арифметической прогрессии.