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

редактировать

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

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

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

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

Содержание

1 Формальное определение
2 Примеры
3 Нормальная форма Курода
4 Свойства и использование
- 4.1 Эквивалентность линейному ограниченному автомату
- 4.2 Свойства замыкания
- 4.3 Вычислительные проблемы
- 4.4 Как модель естественных языков
5 См. Также
6 Примечания
7 Ссылки
8 Дополнительная литература
9 Внешние ссылки

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

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

αAβ → αγβ

где A ∈ N, α, β ∈ (N∪Σ) и γ ∈ (N∪Σ).

Строка u ∈ (N∪Σ) непосредственно дает, или непосредственно выводится из, строки v ∈ (N∪Σ), обозначаемой как u ⇒ v, если u можно записать как lαAβr, а v можно записать как lαγβr для некоторого производственного правила (αAβ → αγβ) ∈ P и некоторые контекстные строки l, r ∈ (N∪Σ). В более общем смысле, u называется yield, или происходит от, v, обозначается как u ⇒ v, если u = u 1 ⇒... ⇒ u n = v для некоторого n≥0 и некоторых строк u 2,..., u n-1 (N∪Σ). То есть отношение (⇒) является рефлексивным транзитивным замыканием отношения (⇒).

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

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

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

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

S → λ

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

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

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

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

Примеры

Следующая контекстно-зависимая грамматика со стартовым символом S генерирует канонический неконтекстный язык, не связанный с контекстом, {abc : n ≥ 1}:

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

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

→2aSBC

→2aaSBC BC

→1aaaBC BCBC

→3aaaB CZ CBC

→4aaaB WZ CBC

→5aaaB WC CBC

→6aaaB BC CBC

→3aaaBBC CZC

→4aaaBBC WZC

→5aaaBBC WCC

→6aaaBBC BCC

→3aaaBB CZCC

→4aaaBB WZCC

→5aaaBB WCCC

→6aaaBB BCCC

→7aaabBBCCC

→8aaa bb BCCC

→8aaab bb CCC

→9aaabb bcCC

→10aaabbb ccC

→10aaabbbc cc

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

Несогласованная грамматика (для которой существует эквивалент $CSG {\ displaystyle CSG}$ ${\ displaystyle CSG}$ ) для LAN guage $LC ross = {ambncmdn: m ≥ 1, n ≥ 1} {\ displaystyle L_ {Cross} = \ {a ^ {m} b ^ {n} c ^ {m} d ^ {n}: m \ geq 1, n \ geq 1 \}}$ ${\ displaystyle L_ {Cross} = \ {a ^ {m} b ^ {n} c ^ {m} d ^ {n}: m \ geq 1, п \ geq 1 \}}$ определяется как $p 1: R → a RC | a C {\ displaystyle p_ {1}: R \ rightarrow aRC | aC}$ ${\ displaystyle p_ {1}: R \ rightarrow aRC | aC}$ и $p 3: T → B T d | B d {\ displaystyle p_ {3}: T \ rightarrow BTd | Bd}$ ${\ displaystyle p_ {3}: T \ rightarrow BTd | Bd}$ , $p 5: CB → BC {\ displaystyle p_ {5}: CB \ rightarrow BC}$ ${\ displaystyle p_ {5}: CB \ rightarrow BC}$ , $p 0: S → RT {\ displaystyle p_ {0}: S \ rightarrow RT}$ ${\ displaystyle p_ {0}: S \ rightarrow RT}$ , $p 6: a B → ab {\ displaystyle p_ {6}: aB \ rightarrow ab}$ ${\ displaystyle p_ {6}: aB \ rightarrow ab}$ , $p 7: b B → bb {\ displaystyle p_ {7 }: bB \ rightarrow bb}$ ${\ displaystyle p_ {7}: bB \ rightarrow bb}$ , $p 8: C d → cd {\ displaystyle p_ {8}: Cd \ rightarrow cd}$ ${\ displaystyle p_ {8}: Cd \ rightarrow cd}$ , $p 9: C c → cc {\ displaystyle p_ {9}: Cc \ rightarrow cc}$ ${\ displaystyle p_ {9}: Cc \ rightarrow cc}$ .

С этими определениями вывод для $a 3 b 2 c 3 d 2 {\ displaystyle a ^ {3} b ^ {2} c ^ {3} d ^ {2}}$ ${\ displaystyle a ^ {3} b ^ {2} c ^ {3} d ^ {2}}$ это: $S ⇒ p 0 RT ⇒ p 1 2 p 2 a 3 C 3 T ⇒ p 3 p 4 a 3 C 3 B 2 d 2 ⇒ p 5 6 a 3 B 2 C 3 d 2 ⇒ p 6 p 7 a 3 b 2 C 3 d 2 ⇒ p 8 p 9 2 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}}$ ${\ 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: i ≥ 1} в Примере 9.5 (стр. 224) из (Hopcroft, Ullman, 1979):

$S → [AC a B] {\ displaystyle S \ rightarrow [ACaB]}$ ${\ displaystyle S \ rightarrow [ACaB]}$
${[C a] a → aa [C a] [C a] [a B] → aa [C a B] [AC a] a → [A a] a [C a] [AC a] [a B] → [A a] a [C a B] [AC a B] → [A a] [a CB] [C a B] → a [a CB] {\ 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 {case}}}$ ${\ 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}}}$
$[CB] → [DB] {\ displaystyle [aCB] \ rightarrow [aDB]}$ ${\ displaystyle [aCB] \ rightarrow [aDB]}$
$[ a CB] → [a E] {\ displaystyle [aCB] \ rightarrow [aE]}$ ${\ displaystyle [aCB] \ rightarrow [aE]}$
${a [D a] → [D a] a [DB] → [D a B] [A a] [ D a] → [AD a] aa [D a B] → [D a] [a B] [A a] [D a B] → [AD a] [a B] {\ 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}}}$ ${\ displaystyle {\ begin {case} \ 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}}}$
$[AD a] → [AC a] {\ di splaystyle [ADa] \ rightarrow [ACa]}$ ${\ displaystyle [ADa] \ rightarrow [ACa]}$
${a [E a] → [E a] a [a E] → [E a] [A a] [E a] → [AE a] a {\ displaystyle {\ begin {cases} \ a [Ea] \ rightarrow [Ea] a \\\ [aE] \ rightarrow [Ea] \\\ [Aa] [Ea] \ rightarrow [AEa] a \ end {cases}} }$ ${\ displaystyle {\ begin {cases} \ a [Ea] \ rightarrow [Ea] a \\\ [aE] \ rightarrow [Ea] \\\ [Aa] [Ea] \ rightarrow [AEa] a \ end {cases}}}$
$[AE a] → a {\ displaystyle [AEa] \ rightarrow a}$ ${\ displaystyle [AEa] \ rightarrow a}$

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

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

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

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

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

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

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

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

Контекстно-зависимые языки закрыты под дополнение. Этот результат 1988 года известен как теорема Иммермана – Селепсеньи. Более того, они замкнуты при union, пересечении, конкатенации, подстановке, обратном гомоморфизме и <138.>Kleene plus.

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

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

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

Проблема пустоты для контекстно-зависимых грамматик (для контекстно-зависимой грамматики G, является ли L (G) = ∅?) неразрешима.

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

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

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

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

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

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

См. Также

Примечания

Ссылки

Дополнительная литература

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

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

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

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

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

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