Контекстно-свободный язык

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

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

Предыстория [ править ]

Контекстно-свободная грамматика [ править ]

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

Автоматический [ править ]

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

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

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

{\begin{aligned}\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{aligned}}

Однозначные КЛЛ являются подмножеством всех КЛЛ: существуют по своей сути неоднозначные КЛЛ. Примером неоднозначного по своей сути КЛЛ является объединение $\{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\}$ который является пересечением этих двух языков. ^[1]

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

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

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

Контекстно-свободный анализ [ править ]

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

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

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

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

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

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

Свойства замыкания [ править ]

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

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

и различии Незамыкание при пересечении, дополнении

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

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

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

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

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

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

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

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

По данным Хопкрофта, Мотвани, Ульмана (2003), ^[25] Многие фундаментальные свойства замыкания и (не)разрешимости контекстно-свободных языков были показаны в статье Бар-Хиллеля , Перлза и Шамира 1961 года. ^[26]

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

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

Примечания [ править ]

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

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

^ Хопкрофт и Ульман 1979 , с. 100, Теорема 4.7.
^ Валиант, Лесли Г. (апрель 1975 г.). «Общее контекстно-свободное распознавание менее чем за кубическое время» (PDF) . Журнал компьютерных и системных наук . 10 (2): 308–315. дои : 10.1016/s0022-0000(75)80046-8 .
^ Ли, Лилиан (январь 2002 г.). «Быстрый контекстно-свободный анализ грамматики требует быстрого умножения логических матриц» (PDF) . Дж АСМ . 49 (1): 1–15. arXiv : cs/0112018 . дои : 10.1145/505241.505242 . S2CID 1243491 . Архивировано (PDF) из оригинала 27 апреля 2003 г.
^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо». Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 .
^ Jump up to: Перейти обратно: ^а ^б ^с Хопкрофт и Ульман 1979 , с. 131, следствие теоремы 6.1.
^ Хопкрофт и Ульман 1979 , с. 142, Упражнение 6.4d.
^ Хопкрофт и Ульман 1979 , с. 131-132, Следствие теоремы 6.2.
^ Хопкрофт и Ульман 1979 , с. 132, Теорема 6.3.
^ Хопкрофт и Ульман 1979 , с. 142-144, Упражнение 6.4c.
^ Хопкрофт и Ульман 1979 , с. 142, Упражнение 6.4б.
^ Хопкрофт и Ульман 1979 , с. 142, Упражнение 6.4а.
^ Стивен Шейнберг (1960). «Примечание о логических свойствах контекстно-свободных языков» (PDF) . Информация и контроль . 3 (4): 372–375. дои : 10.1016/s0019-9958(60)90965-7 . Архивировано (PDF) из оригинала 26 ноября 2018 г.
^ Бейгель, Ричард; Гасарч, Уильям. «Доказательство того, что если L = L1 ∩ L2, где L1 — CFL, а L2 — обычный, то L — контекстно-свободный, который не использует КПК» (PDF) . Факультет компьютерных наук Университета Мэриленда . Архивировано (PDF) из оригинала 12 декабря 2014 г. Проверено 6 июня 2020 г.
^ Хопкрофт и Ульман 1979 , с. 203, теорема 8.12(1).
^ Хопкрофт и Ульман 1979 , с. 202, Теорема 8.10.
^ Соломон (1973) , с. 59, теорема 6.7.
^ Хопкрофт и Ульман 1979 , с. 135, Теорема 6.5.
^ Хопкрофт и Ульман 1979 , с. 203, теорема 8.12(2).
^ Хопкрофт и Ульман 1979 , с. 203, теорема 8.12(4).
^ Хопкрофт и Ульман 1979 , с. 203, Теорема 8.11.
^ Хопкрофт и Ульман 1979 , с. 205, Теорема 8.15.
^ Хопкрофт и Ульман 1979 , с. 206, Теорема 8.16.
^ Хопкрофт и Ульман 1979 , с. 137, теорема 6.6(а).
^ Хопкрофт и Ульман 1979 , с. 137, теорема 6.6(б).
^ Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Уллман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли. Здесь: Раздел 7.6, стр. 304 и Раздел 9.7, стр. 411.
^ Jump up to: Перейти обратно: ^а ^б Иеошуа Бар Гилель; Мика Ашер Перлз; Эли Шамир (1961). «О формальных свойствах простых грамматик фразовой структуры». Журнал фонетических, лингвистических и коммуникативных исследований . 14 (2): 143–172.
^ Хопкрофт и Ульман 1979 .
^ «Как доказать, что язык не контекстно-свободный?» .

Цитируемые работы [ править ]

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

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

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

[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 | аТБ | е ; Т → аТб | ε . Грамматика для B аналогична.

[FOOTNOTEHopcroftUllman1979100Theorem_4.7-2] Хопкрофт и Ульман 1979 , с. 100, Теорема 4.7.

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

[5] Ли, Лилиан (январь 2002 г.). «Быстрый контекстно-свободный анализ грамматики требует быстрого умножения логических матриц» (PDF) . Дж АСМ . 49 (1): 1–15. arXiv : cs/0112018 . дои : 10.1145/505241.505242 . S2CID 1243491 . Архивировано (PDF) из оригинала 27 апреля 2003 г.

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

[FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1-7] Jump up to: Перейти обратно: ^а ^б ^с Хопкрофт и Ульман 1979 , с. 131, следствие теоремы 6.1.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4d-8] Хопкрофт и Ульман 1979 , с. 142, Упражнение 6.4d.

[FOOTNOTEHopcroftUllman1979131-132Corollary_of_Theorem_6.2-9] Хопкрофт и Ульман 1979 , с. 131-132, Следствие теоремы 6.2.

[FOOTNOTEHopcroftUllman1979132Theorem_6.3-10] Хопкрофт и Ульман 1979 , с. 132, Теорема 6.3.

[FOOTNOTEHopcroftUllman1979142-144Exercise_6.4c-11] Хопкрофт и Ульман 1979 , с. 142-144, Упражнение 6.4c.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4b-12] Хопкрофт и Ульман 1979 , с. 142, Упражнение 6.4б.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4a-13] Хопкрофт и Ульман 1979 , с. 142, Упражнение 6.4а.

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

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

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(1)-17] Хопкрофт и Ульман 1979 , с. 203, теорема 8.12(1).

[FOOTNOTEHopcroftUllman1979202Theorem_8.10-18] Хопкрофт и Ульман 1979 , с. 202, Теорема 8.10.

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

[FOOTNOTEHopcroftUllman1979135Theorem_6.5-20] Хопкрофт и Ульман 1979 , с. 135, Теорема 6.5.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(2)-21] Хопкрофт и Ульман 1979 , с. 203, теорема 8.12(2).

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(4)-22] Хопкрофт и Ульман 1979 , с. 203, теорема 8.12(4).

[FOOTNOTEHopcroftUllman1979203Theorem_8.11-23] Хопкрофт и Ульман 1979 , с. 203, Теорема 8.11.

[FOOTNOTEHopcroftUllman1979205Theorem_8.15-24] Хопкрофт и Ульман 1979 , с. 205, Теорема 8.15.

[FOOTNOTEHopcroftUllman1979206Theorem_8.16-25] Хопкрофт и Ульман 1979 , с. 206, Теорема 8.16.

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(a)-26] Хопкрофт и Ульман 1979 , с. 137, теорема 6.6(а).

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(b)-27] Хопкрофт и Ульман 1979 , с. 137, теорема 6.6(б).

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

[Bar-Hillel.Perles.Shamir.1961-29] Jump up to: Перейти обратно: ^а ^б Иеошуа Бар Гилель; Мика Ашер Перлз; Эли Шамир (1961). «О формальных свойствах простых грамматик фразовой структуры». Журнал фонетических, лингвистических и коммуникативных исследований . 14 (2): 143–172.

[FOOTNOTEHopcroftUllman1979-30] Хопкрофт и Ульман 1979 .

[31] «Как доказать, что язык не контекстно-свободный?» .

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

[1]

[2]

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

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

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

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]