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

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

Формальный язык , который может быть описан контекстно-зависимой грамматикой или, что то же самое, несжимающей грамматикой или линейным ограниченным автоматом , называется контекстно-зависимым языком . В некоторых учебниках CSG фактически определяются как незаключенные, определил их не так хотя Ноам Хомский в 1959 году. Этот выбор определения не имеет значения с точки зрения создаваемых языков (т. е. два определения слабо эквивалентны ), но он имеет значение с точки зрения того, какие грамматики структурно считаются контекстно-зависимыми; последний вопрос был проанализирован Хомским в 1963 году.

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

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

Формальное определение

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

Обозначим формальную грамматику как $G=(N,\Sigma ,P,S)$, с $N$ набор нетерминальных символов, $\Sigma$ набор терминальных символов, $P$ набор производственных правил и $S\in N$ стартовый символ.

Строка $u\in (N\cup \Sigma )^{*}$ непосредственно дает или непосредственно наследует строку $v\in (N\cup \Sigma )^{*}$, обозначенный как $u\Rightarrow v$, если v можно получить из u применением некоторого правила производства в P , то есть если $u=\gamma L\delta$ и $v=\gamma R\delta$, где $(L\to R)\in P$ является производственным правилом, и $\gamma ,\delta \in (N\cup \Sigma )^{*}$ — это незатронутая левая и правая часть строки соответственно.В более общем смысле u говорят, что дает или приводит к , v , обозначаемому как $u\Rightarrow ^{*}v$, если v можно получить из u повторным применением правил производства, т. е. если $u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v$ для некоторого n ≥ 0 и некоторых строк $u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}$. Другими словами, отношение $\Rightarrow ^{*}$ есть рефлексивное транзитивное замыкание отношения $\Rightarrow$.

Язык : грамматики G представляет собой набор всех строк терминальных символов, выводимых из ее начального символа, формально $L(G)=\{w\in \Sigma ^{*}\mid S\Rightarrow ^{*}w\}$.Возможны производные, которые не заканчиваются строкой, состоящей только из терминальных символов, но не вносят вклад в L ( G ).

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

Формальная грамматика является контекстно-зависимой , если каждое правило в P имеет форму $S\to \varepsilon$ где $\varepsilon$ пустая строка или форма

а А б → агв

с A ∈ N , $\alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}$, и $\gamma \in (N\cup \Sigma \setminus \{S\})^{+}$.

Название «контекстно-зависимый» объясняется α и β, которые образуют контекст A и определяют, можно ли A заменить на γ или нет.Напротив, в бесконтекстной грамматике контекст отсутствует: левая часть каждого правила производства является просто нетерминалом.

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

(Слабо) эквивалентные определения

— Несжимающая грамматика это грамматика, в которой для любого производственного правила формы u → v длина u меньше или равна длине v .

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

Некоторые авторы используют термин «контекстно-зависимая грамматика» для обозначения несжимающих грамматик в целом.

Грамматики , чувствительные к левому и правому контексту, определяются путем ограничения правил только формой α A → αγ и только A β → γβ соответственно. Языки, созданные с помощью этих грамматик, также представляют собой полный класс контекстно-зависимых языков. Эквивалентность устанавливалась по нормальной форме Пенттонена .

Примеры

а ^н б ^н с ^н

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

1.		С	→	а	Б	С
2.		С	→	а	С	Б	С
3.	С	Б	→	С	С
4.	С	С	→	В	С
5.	В	С	→	В	С
6.	В	С	→	Б	С
7.	а	Б	→	а	б
8.	б	Б	→	б	б
9.	б	С	→	б	с
10.	с	С	→	с	с

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

С

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ ₉ aaabb bc CC

→ ₁₀ aaabbb cc C

→ ₁₀ aaabbbc cc

а ^н б ^н с ^н д ^н и т. д.

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

а ^м б ^н с ^м д ^н

Несжимающаяся грамматика (для которой существует эквивалентная CSG) для языка $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}\mid m\geq 1,n\geq 1\}$ определяется

$p_{1}:R\rightarrow aRC|aC$,

$p_{3}:T\rightarrow BTd|Bd$,

$p_{5}:CB\rightarrow BC$,

$p_{0}:S\rightarrow RT$,

$p_{6}:aB\rightarrow ab$,

$p_{7}:bB\rightarrow bb$,

$p_{8}:Cd\rightarrow cd$, и

$p_{9}:Cc\rightarrow cc$.

С помощью этих определений вывод для $a^{3}b^{2}c^{3}d^{2}$ является: $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}$.

а ^{2 я}

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

1. $S\rightarrow [ACaB]$
2. ${\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. $[aCB]\rightarrow [aDB]$
4. $[aCB]\rightarrow [aE]$
5. ${\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. $[ADa]\rightarrow [ACa]$
7. ${\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}$
8. $[AEa]\rightarrow a$

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

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

Нормальная форма Курода — это реальная нормальная форма для несжимающихся грамматик.

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

См. также: контекстно-зависимый язык

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

Формальный язык может быть описан контекстно-зависимой грамматикой тогда и только тогда, когда он принимается некоторым линейным ограниченным автоматом (LBA). В некоторых учебниках этот результат приписывается исключительно Ландвеберу и Куроде . Другие называют это теоремой Майхилла -Ландвебера-Куроды. (Майхилл представил концепцию детерминистического LBA в 1960 году. Питер С. Ландвебер опубликовал в 1963 году, что язык, принятый детерминистическим LBA, является контекстно-зависимым. Курода ввел понятие недетерминированного LBA и эквивалентности между LBA и CSG в 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, для которого sc ^н находится в G, где c не являющийся частью R. — произвольный символ ,

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

было доказано, что некоторые естественные языки не являются контекстно-свободными . На основе выявления так называемых перекрестных зависимостей и неограниченного скремблирования феномена Однако это не обязательно означает, что класс CSG необходим для отражения «контекстной чувствительности» в разговорном смысле этих терминов на естественных языках. Например, линейные системы контекстно-свободной перезаписи (LCFRS) строго слабее, чем CSG, но могут учитывать явление перекрестных последовательных зависимостей; можно написать грамматику LCFRS для { a ^н б ^н с ^н д ^н | n ≥ 1}, например.

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

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

См. также

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

Дальнейшее чтение

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

Внешние ссылки

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