Введение

Формальный язык, порожденный контекстно-свободной грамматикой.
В теории формальных языков контекстно-свободный язык (CFL), также называемый языком типа 2 по Чомски, — это язык, порождаемый контекстно-свободной грамматикой (CFG). Контекстно-свободные языки имеют широкое применение в языках программирования, в частности, большинство арифметических выражений порождаются контекстно-свободными грамматиками.

Грамматика без контекста

Различные контекстно-свободные грамматики могут порождать один и тот же контекстно-свободный язык. Свойства, присущие самому языку, можно отделить от свойств конкретной грамматики, сравнивая несколько грамматик, описывающих этот язык.

Автоматы

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

Язык Дика

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

Контекстный анализ

Контекстно-свободная природа языка делает его простым для разбора с помощью автомата с магазинной памятью. Определение экземпляра задачи о принадлежности, то есть, для заданной строки, определение, принадлежит ли она языку, порожденному данной грамматикой, также известно как распознавание. Контекстно-свободное распознавание для грамматик в нормальной форме Чомского было показано Лесли Г. Валиантом как сводимое к умножению булевых матриц, таким образом, наследуя его верхнюю границу сложности O(n^2.3728596). В свою очередь, Лилиан Ли показала, что умножение булевых матриц со сложностью O(n^(3-ε)) может быть сведено к CFG-разбору со сложностью O(n^(3-3ε)), тем самым устанавливая некоторую нижнюю границу для последнего. Практическое применение контекстно-свободных языков также требует построения дерева разбора, которое отражает структуру, ассоциированную грамматикой с заданной строкой. Процесс построения этого дерева называется разбором (парсингом). Известные алгоритмы разбора имеют временную сложность, кубическую относительно размера разбираемой строки. Формально, множество всех контекстно-свободных языков идентично множеству языков, принимаемых автоматами с магазинной памятью (PDA). Алгоритмы разбора для контекстно-свободных языков включают алгоритм CYK и алгоритм Эрли. Особым подклассом контекстно-свободных языков являются детерминированные контекстно-свободные языки, которые определяются как множество языков, принимаемых детерминированным автоматом с магазинной памятью, и могут быть разобраны LR(k)-парсерoм. См. также грамматики выражений как альтернативный подход к грамматикам и парсерам.

Неограниченность по пересечению, дополнению и различию

Контекстно-свободные языки не образуют замкнутое множество относительно операции пересечения. Это можно увидеть, рассмотрев языки и , которые оба являются контекстно-свободными. Их пересечение равно , и можно доказать, что оно не является контекстно-свободным, используя лемму о выкачивании для контекстно-свободных языков. Как следствие, контекстно-свободные языки не образуют замкнутое множество относительно операции взятия дополнения, поскольку для любых языков A и B их пересечение можно выразить через объединение и дополнение: . В частности, контекстно-свободные языки не образуют замкнутое множество относительно операции разности, так как дополнение можно выразить через разность: . Однако, если L – контекстно-свободный язык, а D – регулярный язык, то как их пересечение , так и их разность являются контекстно-свободными языками.

Языки, не свободные от контекста

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