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

Контекстно-зависимая грамматика ( CSG ) является формальной грамматикой , в которой левые стороны и правые стороны каких - либо правила производства могут быть окружены контекстом терминальных и нетерминальных символов . Контекстно-зависимые грамматики являются более общими, чем контекстно-свободные , в том смысле, что есть языки, которые могут быть описаны с помощью CSG, но не контекстно-свободных грамматик. Контекстно-зависимые грамматики менее общие (в том же смысле), чем неограниченные грамматики . Таким образом, CSG расположены между контекстно-свободной и неограниченной грамматиками в иерархии Хомского . ^[1]

Формальный язык , который может быть описан с помощью контекстно-зависимой грамматики, или, что эквивалентно, с помощью несжимающих грамматики или линейного ограниченного автомата , называется контекстно-зависимым языком . Некоторые учебники фактически определяют CSG как недоговорные ^{[2] [3] [4] [5],} хотя Ноам Хомский определил их в 1959 году не так. ^{[6] [7]} Этот выбор определения не имеет значения с точки зрения сгенерированные языки (т. е. два определения слабо эквивалентны), но это действительно имеет значение с точки зрения того, какие грамматики структурно считаются контекстно-зависимыми; последний вопрос был проанализирован Хомским в 1963 году. ^{[8] [9]}

Хомский ввел контекстно-зависимые грамматики как способ описания синтаксиса естественного языка, когда часто бывает, что слово может или не может быть подходящим в определенном месте в зависимости от контекста. Уолтер Савич раскритиковал терминологию «контекстно-зависимая» как вводящую в заблуждение и предложил «не стирать» как лучшее объяснение различия между CSG и неограниченной грамматикой . ^[10]

Хотя хорошо известно, что некоторые особенности языков (например, кросс-последовательная зависимость ) не являются контекстно-независимыми, остается открытым вопрос, какая выразительная сила CSG необходима для улавливания контекстной чувствительности, присущей естественным языкам. Последующие исследования в этой области были сосредоточены на более легко поддающихся вычислениям и умеренно контекстно-зависимых языках . ^{[ необходима цитата ]} Синтаксис некоторых языков визуального программирования может быть описан контекстно-зависимыми грамматиками графов . ^[11]

Формальное определение [ править ]

Формальная грамматика G = ( N , Σ, P , S ), с N множество нетерминальных символов, Σ множество терминальных символов, Р набор правил производства, а S начальный символ , является контекстно-зависимой , если все правила в P имеют вид

α A β → αγβ

с A ∈ N , ^{[примечание 1]} α, β ∈ ( N ∪Σ) ^{* [примечание 2]} и γ ∈ ( N ∪Σ) ⁺ . ^{[заметка 3]}

Строка U ∈ ( N ∪Σ) ^* непосредственно дает , или непосредственно вытекает к , струнный V ∈ ( N ∪Σ) ^* , обозначается как ¯u ⇒ V , если у можно записать в виде л α β г , и V может , записывается как l αγβ r для некоторого продукционного правила (α A β → αγβ) ∈ P и некоторых контекстных строк l , r ∈ ( N ∪Σ) ^* . В более общем смысле,U называется выходом , или получить в , V , обозначается как U ⇒ ^* v , если у = у ₁ ⇒ ... ⇒ U _п = v для некоторого п ≥ 0 и некоторых строк ˙U ₂ , ..., у _{п -1} ( N ∪Σ) ^* . То есть отношение (⇒ ^* ) является рефлексивным транзитивным замыканием отношения (⇒).

Язык грамматики G есть множество всех терминальных цепочек символов выводима из ее начального символа, формально: L ( G ) = { ш ∈ Σ ^* : S ⇒ ^* ш }. Возможны производные, которые не заканчиваются строкой, состоящей только из терминальных символов, но не вносят вклад в L ( G ).

Единственное различие между этим определением Хомского и определением неограниченных грамматик состоит в том, что γ может быть пустым в неограниченном случае. ^[10]

Некоторые определения контекстно-зависимой грамматики требуют только, чтобы для любого продукционного правила вида u → v длина u была меньше или равной длине v. Это, казалось бы, более слабое требование на самом деле слабо эквивалентно , ^{[12 ]} см. Неконтактная грамматика # Преобразование в контекстно-зависимую грамматику .

Кроме того, правило формы

S → λ

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

Имя, зависящее от контекста , объясняется элементами α и β, которые формируют контекст A и определяют, можно ли заменить A на γ или нет. Это отличается от контекстно-свободной грамматики, в которой контекст нетерминала не принимается во внимание. В самом деле, каждое произведение контекстно-свободной грамматики имеет вид V → w, где V - единственный нетерминальный символ, а w - строка терминалов и / или нетерминалов; w может быть пустым.

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

В левом контексте - и правый контекст , чувствительные к грамматикам определяются путем ограничения правил только форм α → ау и просто β → γβ, соответственно. Языки, генерируемые этими грамматиками, также являются полным классом контекстно-зависимых языков. ^[13] Эквивалентность установлена нормальной формой Пенттонена . ^[14]

Примеры [ править ]

Следующая контекстно-зависимая грамматика с начальным символом S генерирует канонический неконтекстно -свободный язык { a ⁿ b ⁿ c ⁿ  : n ≥ 1}:

Правила 1 и 2 позволяют раздутие S в виде ^п до н.э. ( BC ) ^{п -1} ; правила с 3 по 6 позволяют последовательно заменять каждый CB на BC ( для этого необходимо четыре правила , поскольку правило CB → BC не вписывается в схему α A β → αγβ); правила 7–10 позволяют заменять нетерминалы B и C соответствующими терминалами b и c соответственно, при условии, что они находятся в нужном месте. Цепочка генерации для aaabbbccc :

S

→ ₂ АБК

→ ₂ ASBC до н.э.

→ ₁ а.о. до н.э. BCBC

→ ₃ аааБ ЦЗ ПГС

→ ₄ аааБ WZ CBC

→ ₅ аааБ WC CBC

→ ₆ аааБ BC CBC

→ ₃ аааBBC CZ C

→ ₄ аааBBC WZ C

→ ₅ аааBBC WC C

→ ₆ аааBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ аааББ WZ CC

→ ₅ аааББ WC CC

→ ₆ аааББ БК СС

→ ₇ аа AB BBCCC

→ ₈ ааа bb BCCC

→ ₈ aaab bb CCC

→ ₉ ааабб до н.э. CC

→ ₁₀ aaabbb cc C

→ ₁₀ aaabbbc cc

Более сложные грамматики можно использовать для синтаксического анализа { a ⁿ b ⁿ c ⁿ d ⁿ : n ≥ 1} и других языков с еще большим количеством букв. Здесь мы покажем более простой подход с использованием не-подрядным грамматика: Пуск с ядром регулярных производств , порождающих сентенциальной формой , а затем включены не договаривающиеся производства , , , , , , , , , .${\ displaystyle CSG}$${\ displaystyle (ABCD) ^ {n} abcd}$${\ displaystyle p_ {Da}: Da \ rightarrow aD}$${\ displaystyle p_ {Db}: Db \ rightarrow bD}$${\displaystyle p_{Dc}:Dc\rightarrow cD}$${\displaystyle p_{Dd}:Dd\rightarrow dd}$${\displaystyle p_{Ca}:Ca\rightarrow aC}$${\displaystyle p_{Cb}:Cb\rightarrow bC}$${\displaystyle p_{Cc}:Cc\rightarrow cc}$${\displaystyle p_{Ba}:Ba\rightarrow aB}$${\displaystyle p_{Bb}:Bb\rightarrow bb}$${\displaystyle p_{Aa}:Aa\rightarrow aa}$

A Non - заказчик грамматика (для которых есть эквивалент ) для языка определяется и , , , , , , .${\displaystyle CSG}$${\displaystyle L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}$${\displaystyle p_{1}:R\rightarrow aRC|aC}$${\displaystyle p_{3}:T\rightarrow BTd|Bd}$${\displaystyle p_{5}:CB\rightarrow BC}$${\displaystyle p_{0}:S\rightarrow RT}$${\displaystyle p_{6}:aB\rightarrow ab}$${\displaystyle p_{7}:bB\rightarrow bb}$${\displaystyle p_{8}:Cd\rightarrow cd}$${\displaystyle p_{9}:Cc\rightarrow cc}$

С помощью этих определений, дифференцирование для является: . ^{[ необходима цитата ]}${\displaystyle a^{3}b^{2}c^{3}d^{2}}$${\displaystyle S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}}$

Несжимающая грамматика для языка { a ^{2 i}  : i ≥ 1} построена в примере 9.5 (стр. 224) из (Hopcroft, Ullman, 1979): ^[15]

1. ${\displaystyle S\rightarrow [ACaB]}$
2. ${\displaystyle {\begin{cases}\ [Ca]a\rightarrow aa[Ca]\\\ [Ca][aB]\rightarrow aa[CaB]\\\ [ACa]a\rightarrow [Aa]a[Ca]\\\ [ACa][aB]\rightarrow [Aa]a[CaB]\\\ [ACaB]\rightarrow [Aa][aCB]\\\ [CaB]\rightarrow a[aCB]\end{cases}}}$
3. ${\displaystyle [aCB]\rightarrow [aDB]}$
4. ${\displaystyle [aCB]\rightarrow [aE]}$
5. ${\displaystyle {\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\rightarrow [ADa]a\\\ a[DaB]\rightarrow [Da][aB]\\\ [Aa][DaB]\rightarrow [ADa][aB]\end{cases}}}$
6. ${\displaystyle [ADa]\rightarrow [ACa]}$
7. ${\displaystyle {\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}}$
8. ${\displaystyle [AEa]\rightarrow a}$

Нормальная форма Куроды [ править ]

Любая контекстно-зависимая грамматика, которая не генерирует пустую строку, может быть преобразована в слабо эквивалентную грамматику в нормальной форме Курода . «Слабо эквивалентный» здесь означает, что две грамматики генерируют один и тот же язык. Нормальная форма, как правило, не зависит от контекста, но будет грамматикой без ограничения . ^{[16] [17]}

Нормальная форма Курода - это фактическая нормальная форма для несогласованных грамматик.

Свойства и использование [ править ]

Эквивалентность линейно ограниченному автомату [ править ]

Формальный язык может быть описан контекстно-зависимой грамматикой тогда и только тогда, когда он принимается некоторым линейным ограниченным автоматом (LBA). ^[18] В некоторых учебниках этот результат приписывается исключительно Ландвеберу и Куроде . ^[7] Другие называют это Myhill теоремой -Landweber-Курод. ^[19] (Майхилл представил концепцию детерминированной LBA в 1960 году. Питер С. Ландвебер опубликовал в 1963 году, что язык, принятый детерминированной LBA, является контекстно-зависимым. Курода ввел понятие недетерминированной LBA и эквивалентность между LBA и CSG в 1964. ^{[20] [21]} ).

По состоянию на 2010 год ^[update]остается открытым вопрос, может ли каждый контекстно-зависимый язык быть принят детерминированным LBA. ^[22]

Свойства закрытия [ править ]

Контекстно-зависимые языки закрыты для дополнения . Этот результат 1988 г. известен как теорема Иммермана – Селепсеньи . ^[19] Более того, они замкнуты относительно объединения , пересечения , конкатенации , подстановки , ^{[примечание 4],} обратного гомоморфизма и Клини плюс . ^[23]

Каждый рекурсивно перечислимый язык L может быть записан как h ( L ) для некоторого контекстно-зависимого языка L и некоторого гомоморфизма строк h . ^[24]

Вычислительные проблемы [ править ]

Проблема решения, которая спрашивает, принадлежит ли определенная строка s языку данной контекстно-зависимой грамматики G , является PSPACE-полной . Более того, существуют контекстно-зависимые грамматики, языки которых являются PSPACE-полными. Другими словами, существует контекстно-зависимая грамматика G, такая, что решение о том, принадлежит ли определенная строка s языку G, является PSPACE-полным (так что G фиксирован, и только s является частью входных данных проблемы). ^[25]

Проблема пустоты для контекстно-зависимых грамматик (для контекстно-зависимой грамматики G , является ли L ( G ) =?) Неразрешима . ^{[26] [примечание 5]}

Как модель естественного языка [ править ]

Савич доказал следующий теоретический результат, на котором он основывает свою критику CSG как основы естественного языка: для любого рекурсивно перечислимого множества R существует контекстно-зависимый язык / грамматика G, который можно использовать как своего рода прокси для проверки членство в R следующим образом: даны строка s , š в R , если и только если существует целое положительное число п , для которых подкожно ^п в G, где с является произвольным символом не является частью R . ^[10]

Было показано, что почти все естественные языки в целом могут характеризоваться контекстно-зависимыми грамматиками, но весь класс CSG кажется намного шире естественных языков. ^{[ необходимая цитата ]} Что еще хуже, поскольку вышеупомянутая проблема решения для CSG является PSPACE-полной, что делает их совершенно непригодными для практического использования, поскольку алгоритм с полиномиальным временем для PSPACE-полной задачи будет подразумевать P = NP .

Было доказано, что некоторые естественные языки не являются контекстно- зависимыми , на основе выявления так называемых кросс-последовательных зависимостей и явлений неограниченного скремблирования . Однако это не обязательно означает, что весь класс CSG необходим для улавливания «контекстной чувствительности» в разговорном смысле этих терминов на естественных языках. Например, строго более слабые (чем CSG) системы линейной бесконтекстной перезаписи (LCFRS) могут объяснять явление кросс-последовательных зависимостей; можно написать грамматику LCFRS для { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1} например. ^{[27] [28] [29]}

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

Совсем недавно класс PTIME был идентифицирован с грамматиками конкатенации диапазонов , которые теперь считаются наиболее выразительными из языков с умеренной контекстной зависимостью. ^[29]

См. Также [ править ]

• Иерархия Хомского
• Развитие контекстно-зависимой грамматики
• Грамматика с определенными предложениями # Неконтекстные грамматики
• Список генераторов парсеров для контекстно-зависимых грамматик

Заметки [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Медуна, Александр ; Швец, Мартин (2005). Грамматики с условиями контекста и их приложения . Джон Вили и сыновья. ISBN 978-0-471-73655-4.

Внешние ссылки [ править ]

• Анализ Эрли для контекстно-зависимых грамматик