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

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

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

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

Фон

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

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

Автоматы

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

Примеры

Примером контекстно-свободного языка является , язык всех непустых строк четной длины, все первые половины которых являются a 's, а все вторые половины которых являются b 's. L генерируется грамматикой . Этот язык не является регулярным . Он принимается магазинным автоматом , где определяется следующим образом: ^{[примечание 1]} ${\displaystyle L=\{a^{n}b^{n}: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{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}}}$

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

язык Дик

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

Характеристики

Контекстно-свободный анализ

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

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

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

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

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

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

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

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

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

Незамкнутость относительно пересечения, дополнения и разности

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

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

Разрешимость

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

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

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

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

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

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

Языки, не являющиеся контекстно-свободными

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

Примечания

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

Ссылки

1. Хопкрофт и Ульман 1979, стр. 100, Теорема 4.7.
2. Валиант, Лесли Г. (апрель 1975 г.). «Общее контекстно-свободное распознавание за время, меньшее, чем кубическое» (PDF) . Журнал компьютерных и системных наук . 10 (2): 308–315. doi : 10.1016/s0022-0000(75)80046-8 .
3. Ли, Лиллиан (январь 2002 г.). «Быстрый контекстно-свободный анализ грамматики требует быстрого умножения булевых матриц» (PDF) . J ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242. S2CID  1243491. Архивировано (PDF) из оригинала 27.04.2003.
4. Кнут, Д. Э. (июль 1965 г.). «О переводе языков слева направо». Информация и управление . 8 (6): 607–639. doi :10.1016/S0019-9958(65)90426-2.
5. Hopcroft & Ullman 1979, стр. 131, Следствие теоремы 6.1.
6. Хопкрофт и Ульман 1979, стр. 142, упражнение 6.4d.
7. Хопкрофт и Ульман 1979, стр. 131-132, Следствие теоремы 6.2.
8. Хопкрофт и Ульман 1979, стр. 132, Теорема 6.3.
9. Хопкрофт и Ульман 1979, стр. 142-144, упражнение 6.4c.
10. Хопкрофт и Ульман 1979, стр. 142, упражнение 6.4b.
11. Хопкрофт и Ульман 1979, стр. 142, упражнение 6.4а.
12. Стивен Шейнберг (1960). «Заметка о булевых свойствах контекстно-свободных языков» (PDF) . Информация и управление . 3 (4): 372–375. doi : 10.1016/s0019-9958(60)90965-7 . Архивировано (PDF) из оригинала 2018-11-26.
13. Бейгель, Ричард; Гасарч, Уильям. «Доказательство того, что если L = L1 ∩ L2, где L1 — CFL, а L2 — Regular, то L — Context Free, который не использует PDA» (PDF) . Университет Мэриленда, кафедра компьютерных наук . Архивировано (PDF) из оригинала 2014-12-12 . Получено 6 июня 2020 г. .
14. Хопкрофт и Ульман 1979, стр. 203, Теорема 8.12(1).
15. Хопкрофт и Ульман 1979, стр. 202, Теорема 8.10.
16. Саломаа (1973), с. 59, теорема 6.7.
17. Хопкрофт и Ульман 1979, стр. 135, Теорема 6.5.
18. Хопкрофт и Ульман 1979, стр. 203, Теорема 8.12(2).
19. Хопкрофт и Ульман 1979, стр. 203, Теорема 8.12(4).
20. Хопкрофт и Ульман 1979, стр. 203, Теорема 8.11.
21. Хопкрофт и Ульман 1979, стр. 205, Теорема 8.15.
22. Хопкрофт и Ульман 1979, стр. 206, Теорема 8.16.
23. Хопкрофт и Ульман 1979, стр. 137, Теорема 6.6(а).
24. Хопкрофт и Ульман 1979, стр. 137, Теорема 6.6(b).
25. Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли.Здесь: Раздел 7.6, стр. 304 и Раздел 9.7, стр. 411
26. Иегошуа Бар-Гилель; Миша Ашер Перлз; Эли Шамир (1961). «О формальных свойствах простых грамматик фразовой структуры». Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143–172.
27. Хопкрофт и Ульман 1979.
28. «Как доказать, что язык не является контекстно-свободным?».

Цитируемые работы

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

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

• Отеберт, Жан-Мишель; Берстель, Жан; Боассон, Люк (1997). «Контекстно-свободные языки и автоматы с выдвижной книгой». В G. Rozenberg; A. Salomaa (ред.). Handbook of Formal Languages ​​(PDF) . Том 1. Springer-Verlag. С. 111–174. Архивировано (PDF) из оригинала 2011-05-16.
• Гинзбург, Сеймур (1966). Математическая теория контекстно-свободных языков . Нью-Йорк, США: McGraw-Hill.
• Sipser, Michael (1997). "2: Context-Free Languages". Введение в теорию вычислений . PWS Publishing. стр. 91–122. ISBN 0-534-94728-X.