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

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

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

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

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

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

А формальная грамматика грамм = (N, Σ, п, S), куда N - набор нетерминальных символов, Σ - набор терминальных символов, п это набор производственных правил, и S это начальный символ, является контекстно-зависимый если все правила в п имеют форму

αАβ → αγβ

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

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

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

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

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

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

S → λ

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

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

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

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

Примеры

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

1.		S	→	а	B	C
2.		S	→	а	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	а	B	→	а	б
8.	б	B	→	б	б
9.	б	C	→	б	c
10.	c	C	→	c	c

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

S

→₂ aSBC

→₂ аaSBCдо н.э

→₁ ааABCBCBC

→₃ аааБCZCBC

→₄ аааБWZCBC

→₅ аааБТуалетCBC

→₆ аааБдо н.эCBC

→₃ aaaBBCCZC

→₄ aaaBBCWZC

→₅ aaaBBCТуалетC

→₆ aaaBBCдо н.эC

→₃ aaaBBCZCC

→₄ aaaBBWZCC

→₅ aaaBBТуалетCC

→₆ aaaBBдо н.эCC

→₇ ааabBBCCC

→₈ аааbbBCCC

→₈ ааабbbCCC

→₉ aaabbдо н.эCC

→₁₀ aaabbbccC

→₁₀ aaabbbccc

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

Несокращающаяся грамматика (для которой есть эквивалент ${displaystyle CSG}$) для языка ${displaystyle L_{Cross}={a^{m}b^{n}c^{m}d^{n}:mgeq 1,ngeq 1}}$ определяется${displaystyle p_{1}:Rightarrow aRC|aC}$и${displaystyle p_{3}:Tightarrow BTd|Bd}$,${displaystyle p_{5}:CBightarrow BC}$, ${displaystyle p_{0}:Sightarrow RT}$, ${displaystyle p_{6}:aBightarrow ab}$, ${displaystyle p_{7}:bBightarrow bb}$, ${displaystyle p_{8}:Cdightarrow cd}$, ${displaystyle p_{9}:Ccightarrow cc}$.

С этими определениями вывод для ${displaystyle a^{3}b^{2}c^{3}d^{2}}$ является:${displaystyle SRightarrow _{p_{0}}RTRightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}TRightarrow _{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я : i ≥ 1} построено в примере 9.5 (стр. 224) из (Hopcroft, Ullman, 1979):^[14]

1. ${displaystyle Sightarrow [ACaB]}$
2. ${displaystyle {egin{cases} [Ca]aightarrow aa[Ca] [Ca][aB]ightarrow aa[CaB] [ACa]aightarrow [Aa]a[Ca] [ACa][aB]ightarrow [Aa]a[CaB] [ACaB]ightarrow [Aa][aCB] [CaB]ightarrow a[aCB]end{cases}}}$
3. ${displaystyle [aCB]ightarrow [aDB]}$
4. ${displaystyle [aCB]ightarrow [aE]}$
5. ${displaystyle {egin{cases} a[Da]ightarrow [Da]a [aDB]ightarrow [DaB] [Aa][Da]ightarrow [ADa]a a[DaB]ightarrow [Da][aB] [Aa][DaB]ightarrow [ADa][aB]end{cases}}}$
6. ${displaystyle [ADa]ightarrow [ACa]}$
7. ${displaystyle {egin{cases} a[Ea]ightarrow [Ea]a [aE]ightarrow [Ea] [Aa][Ea]ightarrow [AEa]aend{cases}}}$
8. ${displaystyle [AEa]ightarrow a}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

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

1. Линц, Питер (2011). Введение в формальные языки и автоматы. Издательство "Джонс и Бартлетт". п. 291. ISBN  978-1-4496-1552-9.
2. Медуна, Александр (2000). Автоматы и языки: теория и приложения. Springer Science & Business Media. п. 730. ISBN  978-1-85233-074-3.
3. Дэвис, Мартин; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. п. 189. ISBN  978-0-08-050246-5.
4. Мартин, Джон С. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: Макгроу-Хилл. п. 277. ISBN  9780073191461.
5. Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. п. 26. ISBN  978-90-272-3250-2.
6. Дэвис, Мартин; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. С. 330–331. ISBN  978-0-08-050246-5.
7. Хомский, Н. (1963). «Формальные свойства грамматики». В Luce, R.D .; Bush, R. R .; Галантер, Э. (ред.). Справочник по математической психологии. Нью-Йорк: Вили. С. 360–363.
8. Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. С. 125–126. ISBN  978-90-272-3250-2.
9. Карлос Мартин Виде, изд. (1999). Вопросы математической лингвистики: семинар по математической лингвистике, Государственный колледж, Пенсильвания, апрель 1998 г.. Издательство Джона Бенджамина. С. 186–187. ISBN  90-272-1556-1.
10. Чжан, Да-Цянь, Кан Чжан и Цзяньнун Цао. "Контекстно-зависимый формализм грамматики графов для спецификации визуальных языков. »Компьютерный журнал 44.3 (2001): 186–200.
11. Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли.; п. 223–224; Упражнение 9, с. 230. В издании 2003 г. была опущена глава о CSG.
12. Хазевинкель, Михиэль (1989). Энциклопедия математики. 4. Springer Science & Business Media. п. 297. ISBN  978-1-55608-003-6. также в https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive
13. Ито, Масами; Кобаяши, Юдзи; Сёдзи, Кунитака (2010). Автоматы, формальные языки и алгебраические системы: Труды AFLAS 2008, Киото, Япония, 20–22 сентября 2008 г.. World Scientific. п. 183. ISBN  978-981-4317-60-3. цитируя Пенттонен, Марти (август 1974 г.). «Односторонний и двусторонний контекст в формальных грамматиках». Информация и контроль. 25 (4): 371–392. Дои:10.1016 / S0019-9958 (74) 91049-3.
14. Они получили грамматику путем систематического преобразования неограниченная грамматика, данные в Exm. 9.4, а именно:
    1. ${displaystyle Sightarrow ACaB}$,
    2. ${displaystyle Caightarrow aaC}$,
    3. ${displaystyle CBightarrow DB}$,
    4. ${displaystyle CBightarrow E}$,
    5. ${displaystyle aDightarrow Da}$,
    6. ${displaystyle ADightarrow AC}$,
    7. ${displaystyle aEightarrow Ea}$,
    8. ${displaystyle AEightarrow varepsilon }$.
    В контекстно-зависимой грамматике строка, заключенная в квадратные скобки, например ${displaystyle [ACaB]}$, считается одним символом (аналогично, например, <name-part> в Форма Бэкуса – Наура ). Имена символов выбраны так, чтобы они напоминали неограниченную грамматику. Точно так же группы правил в контекстно-зависимой грамматике нумеруются в соответствии с правилом неограниченной грамматики, из которого они возникли.
15. Курода, Сигэ-Юки (Июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы». Информация и контроль. 7 (2): 207–223. Дои:10.1016 / с0019-9958 (64) 90120-2.
16. Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты теории классического языка». В Розенберг, Гжегож; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика. Springer-Verlag. С. 175–252. ISBN  3-540-61486-9., Здесь: теорема 2.2, с. 190
17. (Hopcroft, Ullman, 1979); Теорема 9.5, 9.6, с. 225–226
18. https://www.cs.cmu.edu/~flac/pdf/ContSens.pdf
19. Медуна, Александр (2000). Автоматы и языки: теория и приложения. Springer Science & Business Media. п. 755. ISBN  978-1-85233-074-3.
20. Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. С. 126–127. ISBN  978-90-272-3250-2.
21. Мартин, Джон С. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: Макгроу-Хилл. п. 283. ISBN  9780073191461.
22. (Hopcroft, Ullman, 1979); Упражнение S9.10, с. 230–231
23. (Hopcroft, Ullman, 1979); Упражнение S9.14, с. 230–232. час отображает каждый символ на себя или на пустую строку.
24. Пример такой грамматики, предназначенной для решения QSAT проблема, дается в Лита, К. В. (2016-09-01). «О сложности проблемы обнаружения полиморфных вирусов ограниченной длины». 2016 18-й Международный симпозиум по символьным и числовым алгоритмам для научных вычислений (SYNASC): 371–378. Дои:10.1109 / SYNASC.2016.064. ISBN  978-1-5090-5707-8.
25. (Hopcroft, Ullman, 1979); Упражнение S9.13, с. 230–231
26. Каллмейер, Лаура (2011). «Слегка контекстно-зависимые формализмы грамматики: естественные языки не являются контекстно-зависимыми» (PDF).
27. Каллмейер, Лаура (2011). "Грамматические формализмы с умеренной зависимостью от контекста: линейные бесконтекстные системы перезаписи" (PDF).
28. Каллмейер, Лаура (2010). Анализ вне контекстно-свободных грамматик. Springer Science & Business Media. С. 1–5. ISBN  978-3-642-14846-0.

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

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

внешняя ссылка

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