Введение

Тип формальной грамматики
Контекстно-зависимая грамматика (CSG) — это формальная грамматика, в которой левые и правые части любых правил вывода могут быть ограничены контекстом терминальных и нетерминальных символов. Контекстно-зависимые грамматики более общие, чем контекстно-свободные грамматики, в том смысле, что существуют языки, которые могут быть описаны с помощью CSG, но не с помощью контекстно-свободной грамматики. Контекстно-зависимые грамматики менее общие (в том же смысле), чем неограниченные грамматики. Таким образом, CSG занимают промежуточное положение между контекстно-свободными и неограниченными грамматиками в иерархии Чомского. Формальный язык, который может быть описан контекстно-зависимой грамматикой или, эквивалентно, нестягивающей грамматикой или линейно ограниченным автоматом, называется контекстно-зависимым языком. Некоторые учебники фактически определяют CSG как нестягивающие, хотя это не то определение, которое дал Ноам Чомски в 1959 году. Этот выбор определения не имеет значения с точки зрения генерируемых языков (то есть два определения слабо эквивалентны), но имеет значение с точки зрения того, какие грамматики структурно считаются контекстно-зависимыми; этот вопрос был проанализирован Чомски в 1963 году. Чомски ввел контекстно-зависимые грамматики как способ описания синтаксиса естественного языка, где часто бывает так, что слово может быть или не быть уместным в определенном месте в зависимости от контекста. Уолтер Савич критиковал терминологию «контекстно-зависимый» как вводящую в заблуждение и предложил термин «невычеркивающий» как лучшее объяснение различия между CSG и неограниченной грамматикой. Хотя хорошо известно, что определенные особенности языков (например, перекрестная последовательная зависимость) не являются контекстно-свободными, остается открытым вопрос о том, насколько велика выразительная сила CSG, необходимая для описания контекстной зависимости, наблюдаемой в естественных языках. Последующие исследования в этой области были сосредоточены на более вычислительно управляемых слабо контекстно-зависимых языках. Синтаксис некоторых языков визуального программирования может быть описан с помощью контекстно-зависимых графов грамматик.

Формальная грамматика

Давайте обозначим формальную грамматику как G, состоящую из множества нетерминальных символов, множества терминальных символов, множества правил вывода и стартового символа. Строка u непосредственно выводит строку v, что обозначается как u ⇒ v, если v может быть получена из u применением некоторого правила вывода p из P, то есть, если p имеет вид α → β и u = xαy, где x и y – нетронутые левая и правая части строки соответственно, а v = xβy. В более общем случае, говорят, что u выводит v, что обозначается как u ⇒* v, если v может быть получена из u последовательным применением правил вывода, то есть, если u ⇒ v₁ ⇒ v₂ ⇒ ... ⇒ vₙ, для некоторого n ≥ 0 и строк v₁, v₂, ..., vₙ. Иными словами, отношение ⇒* является рефлексивно-транзитивным замыканием отношения ⇒. Язык грамматики G – это множество всех строк терминальных символов, выводимых из ее стартового символа, формально: L(G) = {w | S ⇒* w, w ∈ T*}. Выводы, не заканчивающиеся строкой, состоящей только из терминальных символов, возможны, но не влияют на L(G).

a2i

Грамматика, не содержащая контракций, для языка { a²ⁱ | i ≥ 1 } построена в примере 9.5 (с. 224) (Хопкрофт, Уллман, 1979):

Нормальная форма Курода

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

Эквивалентность линейному автомату

Формальный язык может быть описан контекстно-зависимой грамматикой тогда и только тогда, когда он принимается некоторым линейно ограниченным автоматом (LBA). В некоторых учебниках этот результат приписывается исключительно Ландвеберу и Куроде. (Майхилл ввёл понятие детерминированного LBA в 1960 году. Питер С. Ландвебер опубликовал в 1963 году, что язык, принимаемый детерминированным LBA, является контекстно-зависимым. Курода ввёл понятие недетерминированного LBA и эквивалентность между LBA и контекстно-зависимыми грамматиками в 1964 году.) По состоянию на 2010 год остаётся открытым вопрос, может ли каждый контекстно-зависимый язык быть принят детерминированным LBA.

Свойства закрытия

Контекстно-зависимые языки замкнуты относительно дополнения. Этот результат 1988 года известен как теорема Иммермана — Селепчени. Обратный гомоморфизм и операция Клине плюс. Любой рекурсивно перечислимый язык L может быть представлен в виде h(L) для некоторого контекстно-зависимого языка L и некоторого строкового гомоморфизма h.

Вычислительные задачи

Задача определения, принадлежит ли заданная строка s языку заданной контекстно-зависимой грамматики G, является PSPACE-полной. Более того, существуют контекстно-зависимые грамматики, языки которых PSPACE-полны. Иными словами, существует контекстно-зависимая грамматика G, такая что проверка принадлежности заданной строки s языку G является PSPACE-полной (при этом G фиксирована, и только s является частью входных данных задачи). Задача об определении пустоты для контекстно-зависимых грамматик (для заданной контекстно-зависимой грамматики G, является ли L(G) пустым?) является неразрешимой.

В качестве модели естественных языков

Савич доказал следующий теоретический результат, на котором он основывает свою критику грамматик с контекстной чувствительностью (CSG) как основы для естественного языка: для любого рекурсивно перечисляемого множества R существует контекстно-зависимый язык/грамматика G, который можно использовать как своего рода заместитель для проверки принадлежности к R следующим образом: для данной строки s, строка s принадлежит R тогда и только тогда, когда существует положительное целое число n, для которого scn принадлежит G, где c – произвольный символ, не входящий в R.

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