Контекстно-зависимая грамматика

Контекстно-зависимая грамматика (КЗ-грамматика, грамматика типа 1 по иерархии Хомского) — это формальная грамматика, в которой правила вывода имеют вид αAβ → αγβ, где A — нетерминальный символ, α, β, γ — цепочки терминальных и нетерминальных символов, причём γ не пуста. Основное свойство КЗ-грамматик состоит в том, что замена нетерминала A на цепочку γ разрешена только при наличии определённого левого (α) и правого (β) контекста.

Определение и формальная модель

Формальная грамматика G = (V, T, P, S) является контекстно-зависимой, если каждое правило из множества P имеет вид:

αAβ → αγβ,

где A ∈ V (нетерминал), α, β ∈ (V ∪ T)* (возможно пустые цепочки), γ ∈ (V ∪ T)+ (непустая цепочка). Исключение составляет правило S → ε (пустая цепочка), которое допускается только в том случае, если S не встречается в правых частях других правил.

В отличие от контекстно-свободных грамматик (КС-грамматик), где замена нетерминала не зависит от окружения, в КЗ-грамматиках применение правила возможно только при совпадении контекста α и β. Это ограничение существенно сужает множество допустимых выводов, но одновременно увеличивает выразительную мощность грамматики.

Место в иерархии Хомского

Контекстно-зависимые грамматики занимают промежуточное положение между контекстно-свободными и неограниченными (грамматиками типа 0). В иерархии Ноама Хомского, предложенной в 1956 году, выделяются четыре типа грамматик:

• Тип 0 (неограниченные грамматики) — наиболее мощные, распознаются машинами Тьюринга.
• Тип 1 (контекстно-зависимые грамматики) — распознаются линейно ограниченными автоматами.
• Тип 2 (контекстно-свободные грамматики) — распознаются автоматами с магазинной памятью.
• Тип 3 (регулярные грамматики) — распознаются конечными автоматами.

Каждый последующий тип является подмножеством предыдущего: все регулярные грамматики являются контекстно-свободными, все контекстно-свободные — контекстно-зависимыми, и так далее. Однако обратное неверно: существуют языки, которые могут быть порождены КЗ-грамматикой, но не могут быть порождены КС-грамматикой.

Примеры контекстно-зависимых языков

Язык aⁿbⁿcⁿ

Классический пример языка, не являющегося контекстно-свободным, но порождаемого КЗ-грамматикой — язык L = { aⁿbⁿcⁿ | n ≥ 1 }. Этот язык состоит из цепочек, содержащих равное количество букв a, b и c, расположенных в строгом порядке. КС-грамматика не может породить этот язык, так как требует одновременного подсчёта трёх групп символов, что невозможно с помощью одного магазинного автомата.

Пример КЗ-грамматики для L = { aⁿbⁿcⁿ }:

1. S → aSBC | aBC
2. CB → CZ
3. CZ → BZ
4. BZ → BC
5. aB → ab
6. bB → bb
7. bC → bc
8. cC → cc

Вывод цепочки a²b²c² (aabbcc) выглядит следующим образом:

S → aSBC → aaBCBC → aaB CZ C → aaB BZ C → aaB B C C → aab B C C → aabb C C → aabbc C → aabbcc

Язык WW

Другой пример — язык { ww | w ∈ {a, b}* }, состоящий из удвоенных цепочек. Этот язык также не является контекстно-свободным, но может быть порождён КЗ-грамматикой.

Свойства и ограничения

Разрешимость

Для контекстно-зависимых грамматик разрешима проблема принадлежности слова языку: существует алгоритм, который для произвольной КЗ-грамматики G и произвольной цепочки w определяет, выводима ли w в G. Однако этот алгоритм имеет экспоненциальную сложность в худшем случае.

Неразрешимые проблемы

Ряд важных задач для КЗ-грамматик являются алгоритмически неразрешимыми:

• Проблема пустоты (порождает ли грамматика хотя бы одну цепочку) — разрешима.
• Проблема эквивалентности (порождают ли две грамматики один и тот же язык) — неразрешима.
• Проблема однозначности (существует ли для грамматики альтернативный вывод той же цепочки) — неразрешима.
• Проблема включения (является ли язык одной грамматики подмножеством языка другой) — неразрешима.

Замкнутость

Класс контекстно-зависимых языков замкнут относительно следующих операций:

• объединение
• пересечение
• конкатенация
• итерация (звезда Клини)
• гомоморфизм (при определённых условиях)

Однако он не замкнут относительно дополнения (хотя долгое время этот вопрос оставался открытым, пока в 1987 году не было доказано, что дополнение КЗ-языка также является КЗ-языком).

Связь с линейно ограниченными автоматами

Контекстно-зависимые грамматики эквивалентны по выразительной мощности недетерминированным линейно ограниченным автоматам (ЛОА). ЛОА — это машина Тьюринга, лента которой ограничена длиной входной цепочки (с точностью до линейного множителя). Детерминированные ЛОА порождают более узкий класс языков, который, как предполагается, строго меньше класса КЗ-языков, хотя это не доказано.

Применение в компьютерных науках

Обработка естественных языков

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

Теория формальных языков

КЗ-грамматики применяются при изучении границ выразительности формальных языков. Они служат промежуточным звеном между практичными КС-грамматиками (используемыми в компиляторах) и неограниченными грамматиками (слишком сложными для практического применения).

Синтаксический анализ

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

История и развитие

Понятие контекстно-зависимых грамматик было введено Ноамом Хомским в 1956 году в рамках его работы по формальным грамматикам. В 1960-х годах Джон Майхилл и Шейла Грейбах исследовали свойства этих грамматик. В 1964 году Питер Ландин показал связь между КЗ-грамматиками и линейно ограниченными автоматами.

В 1970-х годах были разработаны алгоритмы синтаксического анализа для подклассов КЗ-грамматик (например, грамматики с контекстно-зависимыми правилами, но ограниченной сложностью). В 1980-х годах было доказано, что класс КЗ-языков замкнут относительно дополнения (результат, полученный независимо несколькими исследователями).

Критика и ограничения

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

Кроме того, для многих задач, решаемых с помощью КЗ-грамматик, существуют более эффективные альтернативы, такие как атрибутные грамматики или грамматики с зависимостями.

Источники

• Хомский Н. Три модели описания языка // Кибернетический сборник. — 1962. — № 2. — С. 237–266.
• Гинзбург С. Математическая теория контекстно-свободных языков. — М.: Мир, 1970. — 326 с.
• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1. — 612 с.
• Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973. — 368 с.
• Hopcroft J. E., Ullman J. D. Introduction to Automata Theory, Languages, and Computation. — Addison-Wesley, 1979. — 418 p.