Бесконтекстный язык

В теории формальных языков , контекстно-свободный язык ( CFL ) представляет собой язык , порожденный контекстно-свободной грамматики (CFG).

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

Фон [ править ]

Бесконтекстная грамматика [ править ]

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

Автоматы [ править ]

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

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

Примером контекстно-свободного языка является язык всех непустых строк четной длины, все первые половины которых являются буквами $a$ , а все вторые половины - $буквами b$ . $L$ порождается грамматикой . Этот язык не является регулярным . Он принимается автоматом выталкивания, где определяется следующим образом: ^{[примечание 1]} ${\ Displaystyle L = \ {a ^ {n} b ^ {n}: п \ geq 1 \}}$ ${\ displaystyle S \ to aSb ~ | ~ ab}$ ${\ displaystyle M = (\ {q_ {0}, q_ {1}, q_ {f} \}, \ {a, b \}, \ {a, z \}, \ delta, q_ {0}, z , \ {q_ {f} \})}$ ${\ displaystyle \ delta}$

{\ displaystyle {\ begin {align} \ delta (q_ {0}, a, z) & = (q_ {0}, az) \\\ delta (q_ {0}, a, a) & = (q_ { 0}, aa) \\\ delta (q_ {0}, b, a) & = (q_ {1}, \ varepsilon) \\\ delta (q_ {1}, b, a) & = (q_ {1 }, \ varepsilon) \\\ delta (q_ {1}, \ varepsilon, z) & = (q_ {f}, \ varepsilon) \ end {align}}}

Однозначные CFL - это подходящее подмножество всех CFL: есть по своей сути неоднозначные CFL. Примером неоднозначного по своей сути CFL является объединение с . Этот набор контекстно-независимый, поскольку объединение двух контекстно-свободных языков всегда контекстно-независимое. Но нет способа однозначно проанализировать строки в (неконтекстно-независимом) подмножестве, которое является пересечением этих двух языков. ^[1] $\{a^{n}b^{m}c^{m}d^{n}|n,m>0\}$ $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$ $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$

Язык Дайка [ править ]

Язык всех правильно подобранных скобках порождается грамматикой . $S\to SS~|~(S)~|~\varepsilon$

Свойства [ править ]

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

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

Определение экземпляра проблемы членства ; т.е. по заданной строке определить, где находится язык, созданный данной грамматикой ; также известен как признание . Лесли Г. Валиант показал , что ^{неконтекстное} распознавание грамматик нормальных форм Хомского сводится к логическому умножению матриц , таким образом унаследовав верхнюю границу сложности O ( n ^2.3728639 ). ^[2]^{[примечание 2]} И наоборот, Лилиан Ли показала O ( n ^{3 − ε} $w$ $w\in L(G)$ $L$ $G$ ) логическое умножение матриц сводится к O ( n ^3−3ε ) ^{разбору} CFG, тем самым устанавливая некоторую нижнюю границу для последнего. ^[3]

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

Формально набор всех контекстно-свободных языков идентичен набору языков, принимаемых автоматами выталкивания (PDA). Алгоритмы Parser для контекстно-свободных языков включают алгоритм CYK и алгоритм Эрли .

Особым подклассом контекстно-свободных языков являются детерминированные контекстно-свободные языки, которые определяются как набор языков, принимаемых детерминированным автоматом выталкивания, и которые могут быть проанализированы парсером LR (k) . ^[4]

См. Также синтаксический анализ грамматики выражений как альтернативный подход к грамматике и синтаксическому анализатору.

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

Класс контекстно-свободных языков закрывается при следующих операциях. То есть, если L и P являются контекстно-независимыми языками, следующие языки также являются контекстно-независимыми:

объединение из L и P ^[5] $L\cup P$
обращение L ^[6]
конкатенации из L и P ^[5] $L\cdot P$
клиниевская звезда из L ^[5] $L^{*}$
изображение из L под гомоморфизм ^[7] $\varphi (L)$ $\varphi$
изображение из L под обратной гомоморфизм ^[8] $\varphi ^{-1}(L)$ $\varphi ^{-1}$
циклический сдвиг на L (язык ) ^[9] $\{vu:uv\in L\}$
префиксное замыкание L (множество всех префиксов строк из L ) ^[10]
фактор L / R из L с помощью регулярного языка R ^[11]

Незащищенность от пересечения, дополнения и различия [ править ]

Контекстно-свободные языки не закрываются при пересечении. Это можно увидеть, взяв языки и , которые не зависят от контекста. ^{[примечание 3]} Их пересечение есть , что можно показать неконтекстно-бесконтекстной леммой для контекстно-свободных языков . Как следствие, контекстно-свободные языки не могут быть закрыты при комплементарности, как и для любых языков A и B , их пересечение может быть выражено профсоюзом и дополнения: . В частности, контекстно-свободный язык не может быть закрыт при разнице, так как дополнение может быть выражено разностью: . ^[12] $A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}$ $B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}$ $A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}$ $A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}$ ${\overline {L}}=\Sigma ^{*}\setminus L$

Однако, если L - контекстно-свободный язык, а D - обычный язык, то и их пересечение, и их различие являются контекстно-свободными языками. ^[13] $L\cap D$ $L\setminus D$

Разрешимость [ править ]

В формальной теории языка вопросы о регулярных языках обычно разрешимы, а вопросы о контекстно-свободных языках - часто нет. Разрешаемо, является ли такой язык конечным, но не содержит ли он всех возможных строк, является ли он правильным, однозначным или эквивалентным языку с другой грамматикой. ^[14]

Следующие проблемы неразрешимы для произвольно заданных контекстно-свободных грамматик A и B:

Эквивалентность: есть ? ^[15] $L(A)=L(B)$
Несвязанность: есть ? ^[16] Однако пересечение контекстно-свободного языка и регулярного языка является контекстно-независимым, ^[17]^[18] поэтому вариант проблемы, когда B - регулярная грамматика, разрешим (см. «Пустота» ниже). $L(A)\cap L(B)=\emptyset$
Сдерживание: есть ? ^[19] Опять же, вариант проблемы, где B - регулярная грамматика, разрешим, ^[^{необходима цитата}^{], в} то время как вариант , в котором A является регулярным, обычно нет. ^[20] $L(A)\subseteq L(B)$
Универсальность: есть ? ^[21] $L(A)=\Sigma ^{*}$

Для произвольных контекстно-свободных языков разрешимы следующие проблемы :

Пустота: Учитывая контекстно-свободную грамматику A , есть ли? ^[22] $L(A)=\emptyset$
Конечность: Учитывая контекстно-свободную грамматику , является конечным? ^[23] $L(A)$
Членство: Учитывая контекстно-независимую грамматику G , да и слово , не так ли ? Эффективные алгоритмы полиномиального времени для задачи членства являются алгоритмом CYK и алгоритм Эрел . $w$ $w\in L(G)$

Согласно Hopcroft, Motwani, Ullman (2003), ^[24], многие из фундаментальных свойств замкнутости и (не) разрешимости контекстно-свободных языков были показаны в статье Бар-Гилеля , Перлеса и Шамира 1961 года ^[25].

Языки, которые не являются контекстно-независимыми [ править ]

Набор является контекстно-зависимым языком , но не существует контекстно-зависимой грамматики, генерирующей этот язык. ^[26] Итак, существуют контекстно-зависимые языки, которые не являются контекстно-независимыми. Чтобы доказать, что данный язык не является контекстно-независимым, можно использовать лемму о накачке для контекстно-свободных языков ^[25] или ряд других методов, таких как лемма Огдена или теорема Париха . ^[27] $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$

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

^ значениеаргументов и результатов: $\delta$ $\delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )$
^ В статье Валианта O ( n ^2.81 ) было тогда самой известной верхней границей. См. Раздел « Умножение матриц # Алгоритмы» для эффективного умножения матриц и « Алгоритм Копперсмита – Винограда» для улучшения границ с тех пор.
^ Контекстно-свободная грамматика для языка A задается следующими производственными правилами, принимая S в качестве начального символа: S → Sc | aTb | ε ; T → aTb | ε . Грамматика для B аналогична.

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

Перейти ↑ Hopcroft & Ullman 1979 , p. 100, теорема 4.7.
↑ Valiant, Лесли Г. (апрель 1975 г.). «Общее бесконтекстное распознавание менее чем за кубическое время» . Журнал компьютерных и системных наук . 10 (2): 308–315. DOI : 10.1016 / s0022-0000 (75) 80046-8 . Архивировано из оригинального 10 ноября 2014 года.
^ Ли, Лилиан (январь 2002 г.). «Быстрый анализ грамматики без контекста требует быстрого умножения логических матриц» (PDF) . J ACM . 49 (1): 1–15. arXiv : cs / 0112018 . DOI : 10.1145 / 505241.505242 .
↑ Knuth, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
^ a b c Hopcroft & Ullman 1979 , стр. 131, следствие теоремы 6.1.
Перейти ↑ Hopcroft & Ullman 1979 , p. 142, упражнение 6.4d.
Перейти ↑ Hopcroft & Ullman 1979 , p. 131-132, следствие теоремы 6.2.
Перейти ↑ Hopcroft & Ullman 1979 , p. 132, теорема 6.3.
Перейти ↑ Hopcroft & Ullman 1979 , p. 142–144, упражнение 6.4c.
Перейти ↑ Hopcroft & Ullman 1979 , p. 142, упражнение 6.4b.
Перейти ↑ Hopcroft & Ullman 1979 , p. 142, упражнение 6.4а.
^ Стивен Шейнберг (1960). «Примечание о логических свойствах контекстно-свободных языков» (PDF) . Информация и контроль . 3 : 372–375. DOI : 10.1016 / s0019-9958 (60) 90965-7 .
^ Бейгель, Ричард; Гасарх, Уильям. «Доказательство того, что если L = L1 ∩ L2, где L1 - CFL, а L2 - обычный, то L - контекстно-свободный, который не использует КПК» (PDF) . Департамент компьютерных наук Мэрилендского университета . Проверено 6 июня 2020 года .
^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 1138 . ISBN 1-57955-008-8.
Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.12 (1).
Перейти ↑ Hopcroft & Ullman 1979 , p. 202, теорема 8.10.
^ Саломаа (1973) , стр. 59, теорема 6.7
Перейти ↑ Hopcroft & Ullman 1979 , p. 135, теорема 6.5.
Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.12 (2).
Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.12 (4).
Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.11.
Перейти ↑ Hopcroft & Ullman 1979 , p. 137, теорема 6.6 (а).
Перейти ↑ Hopcroft & Ullman 1979 , p. 137, теорема 6.6 (b).
^ Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли. Здесь: раздел 7.6, стр.304 и раздел 9.7, стр.411.
^ а б Иегошуа Бар-Гиллель; Миха Ашер Перлес; Эли Шамир (1961). «О формальных свойствах грамматик простых фраз». Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143–172.
Перейти ↑ Hopcroft & Ullman 1979 .
^ Как доказать, что язык не является контекстно-зависимым?

Процитированные работы [ править ]

Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли.
Саломаа, Арто (1973). Формальные языки . Серия монографий ACM.

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

Отбер, Жан-Мишель; Берстель, Жан; Боассон, Люк (1997). «Контекстно-свободные языки и выталкивающие автоматы». У Г. Розенберга; А. Саломаа (ред.). Справочник формальных языков (PDF) . 1 . Springer-Verlag. С. 111–174.
Гинзбург, Сеймур (1966). Математическая теория контекстно-свободных языков . Нью-Йорк, Нью-Йорк, США: Макгроу-Хилл.
Сипсер, Майкл (1997). «2: Контекстно-свободные языки». Введение в теорию вычислений . PWS Publishing. С. 91–122. ISBN 0-534-94728-X.

[1] значениеаргументов и результатов: $\delta$ $\delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )$

[4] В статье Валианта O ( n ^2.81 ) было тогда самой известной верхней границей. См. Раздел « Умножение матриц # Алгоритмы» для эффективного умножения матриц и « Алгоритм Копперсмита – Винограда» для улучшения границ с тех пор.

[14] Контекстно-свободная грамматика для языка A задается следующими производственными правилами, принимая S в качестве начального символа: S → Sc | aTb | ε ; T → aTb | ε . Грамматика для B аналогична.

[FOOTNOTEHopcroftUllman1979100Theorem_4.7-2] Перейти ↑ Hopcroft & Ullman 1979 , p. 100, теорема 4.7.

[3] Valiant, Лесли Г. (апрель 1975 г.). «Общее бесконтекстное распознавание менее чем за кубическое время» . Журнал компьютерных и системных наук . 10 (2): 308–315. DOI : 10.1016 / s0022-0000 (75) 80046-8 . Архивировано из оригинального 10 ноября 2014 года.

[5] Ли, Лилиан (январь 2002 г.). «Быстрый анализ грамматики без контекста требует быстрого умножения логических матриц» (PDF) . J ACM . 49 (1): 1–15. arXiv : cs / 0112018 . DOI : 10.1145 / 505241.505242 .

[6] Knuth, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .

[FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1-7] Hopcroft & Ullman 1979 , стр. 131, следствие теоремы 6.1.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4d-8] Перейти ↑ Hopcroft & Ullman 1979 , p. 142, упражнение 6.4d.

[FOOTNOTEHopcroftUllman1979131-132Corollary_of_Theorem_6.2-9] Перейти ↑ Hopcroft & Ullman 1979 , p. 131-132, следствие теоремы 6.2.

[FOOTNOTEHopcroftUllman1979132Theorem_6.3-10] Перейти ↑ Hopcroft & Ullman 1979 , p. 132, теорема 6.3.

[FOOTNOTEHopcroftUllman1979142-144Exercise_6.4c-11] Перейти ↑ Hopcroft & Ullman 1979 , p. 142–144, упражнение 6.4c.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4b-12] Перейти ↑ Hopcroft & Ullman 1979 , p. 142, упражнение 6.4b.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4a-13] Перейти ↑ Hopcroft & Ullman 1979 , p. 142, упражнение 6.4а.

[Scheinberg.1960-15] Стивен Шейнберг (1960). «Примечание о логических свойствах контекстно-свободных языков» (PDF) . Информация и контроль . 3 : 372–375. DOI : 10.1016 / s0019-9958 (60) 90965-7 .

[16] Бейгель, Ричард; Гасарх, Уильям. «Доказательство того, что если L = L1 ∩ L2, где L1 - CFL, а L2 - обычный, то L - контекстно-свободный, который не использует КПК» (PDF) . Департамент компьютерных наук Мэрилендского университета . Проверено 6 июня 2020 года .

[17] Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 1138 . ISBN 1-57955-008-8.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(1)-18] Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.12 (1).

[FOOTNOTEHopcroftUllman1979202Theorem_8.10-19] Перейти ↑ Hopcroft & Ullman 1979 , p. 202, теорема 8.10.

[20] Саломаа (1973) , стр. 59, теорема 6.7

[FOOTNOTEHopcroftUllman1979135Theorem_6.5-21] Перейти ↑ Hopcroft & Ullman 1979 , p. 135, теорема 6.5.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(2)-22] Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.12 (2).

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(4)-23] Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.12 (4).

[FOOTNOTEHopcroftUllman1979203Theorem_8.11-24] Перейти ↑ Hopcroft & Ullman 1979 , p. 203, теорема 8.11.

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(a)-25] Перейти ↑ Hopcroft & Ullman 1979 , p. 137, теорема 6.6 (а).

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(b)-26] Перейти ↑ Hopcroft & Ullman 1979 , p. 137, теорема 6.6 (b).

[27] Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли. Здесь: раздел 7.6, стр.304 и раздел 9.7, стр.411.

[Bar-Hillel.Perles.Shamir.1961-28] а б Иегошуа Бар-Гиллель; Миха Ашер Перлес; Эли Шамир (1961). «О формальных свойствах грамматик простых фраз». Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143–172.

[FOOTNOTEHopcroftUllman1979-29] Перейти ↑ Hopcroft & Ullman 1979 .

[30] Как доказать, что язык не является контекстно-зависимым?

[примечание 1]