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

Тип формальной грамматики

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

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

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

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

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

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

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

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

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

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

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

α А β → αγβ

с A ∈ N , ^{[примечание 1]} , ^{[примечание 2]} и . ^{[заметка 3]} ${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$ ${\displaystyle \gamma \in (N\cup \Sigma \setminus \{S\})^{+}}$

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

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

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

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

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

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

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

Примеры

а н б н с н

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

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

С

→ ₂ АСБК

→ ₂ aSBC BC​

→ ₁ аа aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ аааБ WZ CBC

→ ₅ aaaB WC CBC

→ ₆ аааБ BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC Туалет C

→ ₆ аааBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ аааBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ аааBB BC CC

→ ₇ аа аб BBCCC

→ ₈ ааа бб BCCC

→ ₈ аааб бб CCC

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

→ ₁₀ аааббб куб.см C

→ ₁₀ аааbbc куб.см

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

Для анализа { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1 } и другие языки с еще большим количеством букв. Здесь мы показываем более простой подход с использованием несжимающих грамматик: ^{[ нужна цитация ]} Начните с ядра регулярных продукций, генерирующих формы предложений , а затем включите несжимающие постановки , , , , , , , , , . ${\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}$

а м б н см д н​

Несжимающая грамматика (для которой существует эквивалентная CSG) для языка определяется формулой ${\displaystyle L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}\mid 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}}$

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

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

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

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

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

Вычислительные проблемы

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

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

Как модель естественных языков

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

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

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

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

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

Смотрите также

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

Примечания

1. т. е. A - единственный нетерминал
2. т.е. строки α и β нетерминалов (кроме начального символа) и терминалов
3. т.е. γ — непустая строка нетерминалов (кроме начального символа) и терминалов
4. более формально: если L ⊆ Σ ^* является контекстно-зависимым языком и f отображает каждый a ∈ Σ в контекстно-зависимый язык f ( a ), f ( L ) снова является контекстно-зависимым языком
5. Это также следует из того, что (1) контекстно-свободные языки также являются контекстно-зависимыми, (2) контекстно-зависимые языки замкнуты при пересечении, но (3) непересекаемость контекстно-свободных языков неразрешима .

Рекомендации

1. (Хопкрофт, Ульман, 1979); п.9.4, стр.227
2. Линц, Питер (2011). Введение в формальные языки и автоматы. Издательство Джонс и Бартлетт. п. 291. ИСБН 978-1-4496-1552-9.
3. Медуна, Александр (2000). Автоматы и языки: теория и приложения. Springer Science & Business Media. п. 730. ИСБН 978-1-85233-074-3.
4. Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. п. 189. ИСБН 978-0-08-050246-5.
5. Мартин, Джон К. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. п. 277. ИСБН 9780073191461.
6. Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. п. 26. ISBN 978-90-272-3250-2.
7. Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. стр. 330–331. ISBN 978-0-08-050246-5.
8. Хомский, Н. (1963). «Формальные свойства грамматики». В Люсе, РД; Буш, Р.Р.; Галантер, Э. (ред.). Справочник по математической психологии . Нью-Йорк: Уайли. стр. 360–363.
9. Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. стр. 125–126. ISBN 978-90-272-3250-2.
10. Карлос Мартин Виде, изд. (1999). Проблемы математической лингвистики: семинар по математической лингвистике, Государственный колледж, Пенсильвания, апрель 1998 г. Издательство John Benjamins Publishing. стр. 186–187. ISBN 90-272-1556-1.
11. Чжан, Да-Цянь, Кан Чжан и Цзяньнун Цао. «Контекстно-зависимый формализм графовой грамматики для спецификации визуальных языков». Компьютерный журнал 44.3 (2001): 186–200.
12. Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 9780201029888.; п. 223–224; Упражнение 9, с. 230. В издании 2003 года глава о РГС была опущена.
13. Хазевинкель, Мишель (1989). Энциклопедия математики. Том. 4. Springer Science & Business Media. п. 297. ИСБН 978-1-55608-003-6.также на https://www.encyclepediaofmath.org/index.php/Grammar,_context-sensitivity
14. Ито, Масами; Кобаяши, Юдзи; Сёдзи, Кунитака (2010). Автоматы, формальные языки и алгебраические системы: материалы AFLAS 2008, Киото, Япония, 20–22 сентября 2008 г. World Scientific. п. 183. ИСБН 978-981-4317-60-3.со ссылкой на Пенттонена, Мартти (август 1974 г.). «Односторонний и двусторонний контекст в формальных грамматиках». Информация и контроль . 25 (4): 371–392. дои : 10.1016/S0019-9958(74)91049-3 .
15. Они получили грамматику путем систематического преобразования неограниченной грамматики , приведенной в Exm. 9.4, а именно:
    1. ${\displaystyle S\rightarrow ACaB}$,
    2. ${\displaystyle Ca\rightarrow aaC}$,
    3. ${\displaystyle CB\rightarrow DB}$,
    4. ${\displaystyle CB\rightarrow E}$,
    5. ${\displaystyle aD\rightarrow Da}$,
    6. ${\displaystyle AD\rightarrow AC}$,
    7. ${\displaystyle aE\rightarrow Ea}$,
    8. ${\displaystyle AE\rightarrow \varepsilon }$.
    В контекстно-зависимой грамматике строка, заключенная в квадратные скобки, например , считается одним символом (аналогично, например, в форме Бэкуса-Наура ). Имена символов выбраны так, чтобы напоминать неограниченную грамматику. Аналогично, группы правил в контекстно-зависимой грамматике нумеруются по правилу неограниченной грамматики, из которого они произошли. ${\displaystyle [ACaB]}$<name-part>
16. Курода, Сиге-Юки (июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы». Информация и контроль . 7 (2): 207–223. дои : 10.1016/s0019-9958(64)90120-2 .
17. Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты классической теории языка». В Розенберге, Гжегож ; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Спрингер-Верлаг. стр. 175–252. ISBN 3-540-61486-9., Здесь: Теорема 2.2, с. 190
18. (Хопкрофт, Ульман, 1979); Теоремы 9.5, 9.6, с. 225–226
19. Сатнер, Клаус (весна 2016 г.). «Контекстно-зависимые грамматики» (PDF) . Университет Карнеги Меллон . Архивировано из оригинала (PDF) 3 февраля 2017 г. Проверено 29 августа 2019 г.
20. PS Ландвебер (1963). «Три теоремы о грамматиках фразовой структуры типа 1». Информация и контроль . 6 (2): 131–136. дои : 10.1016/s0019-9958(63)90169-4 .
21. Медуна, Александр (2000). Автоматы и языки: теория и приложения. Springer Science & Business Media. п. 755. ИСБН 978-1-85233-074-3.
22. Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. стр. 126–127. ISBN 978-90-272-3250-2.
23. Мартин, Джон К. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. п. 283. ИСБН 9780073191461.
24. (Хопкрофт, Ульман, 1979); Упражнение S9.10, с. 230–231
25. (Хопкрофт, Ульман, 1979); Упражнение S9.14, с. 230–232. h отображает каждый символ сам на себя или на пустую строку.
26. Пример такой грамматики, предназначенной для решения проблемы QSAT , приведен в Lita, CV (01.09.2016). «О сложности проблемы обнаружения полиморфных вирусов ограниченной длины». 2016 18-й Международный симпозиум по символьным и числовым алгоритмам для научных вычислений (SYNASC) . стр. 371–378. дои : 10.1109/SYNASC.2016.064. ISBN 978-1-5090-5707-8. S2CID  18067130.
27. (Хопкрофт, Ульман, 1979); Упражнение S9.13, с. 230–231
28. Калмейер, Лаура (2011). «Слегка контекстно-зависимые грамматические формализмы: естественные языки не являются контекстно-свободными» (PDF) . Архивировано (PDF) из оригинала 19 августа 2014 г.
29. Калмейер, Лаура (2011). «Слегка контекстно-зависимые грамматические формализмы: линейные системы контекстно-свободной переписывания» (PDF) . Архивировано (PDF) из оригинала 19 августа 2014 г.
30. Калмейер, Лаура (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 1–5. ISBN 978-3-642-14846-0.

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

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

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

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