Бесконтекстный язык - Context-free language

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

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

Задний план

Бесконтекстная грамматика

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

Автоматы

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

Примеры

Примером контекстно-свободного языка является язык всех непустых строк четной длины, все первые половины которых являются буквами $a$ , а все вторые половины - $буквами b$ . $L$ порождается грамматикой . Этот язык не является регулярным . Это принимается автоматом выталкивания, где определяется следующим образом: ${\ 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 является объединение с . Этот набор контекстно-свободный, так как объединение двух контекстно-свободных языков всегда контекстно-свободное. Но нет способа однозначно проанализировать строки в (неконтекстно-независимом) подмножестве, которое является пересечением этих двух языков. ${\ 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 \ к SS ~ | ~ (S) ~ | ~ \ varepsilon}$

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

Бесконтекстный анализ

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

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

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

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

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

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

Закрытие

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

объединение из L и P ${\ Displaystyle L \ чашка P}$
обращение L
конкатенации из L и P ${\ Displaystyle L \ cdot P}$
Клини звезда из L ${\ Displaystyle L ^ {*}}$
изображение из L под гомоморфизм ${\ displaystyle \ varphi (L)}$ ${\ displaystyle \ varphi}$
изображение из L под обратным гомоморфизмом ${\ Displaystyle \ varphi ^ {- 1} (L)}$ ${\ displaystyle \ varphi ^ {- 1}}$
циклический сдвиг на L (язык ) ${\ displaystyle \ {vu: uv \ in L \}}$
префиксное замыкание L (множество всех префиксов строк из L )
фактор L / R из L с помощью обычного языка R

Незащищенность от пересечений, дополнений и различий

Контекстно-свободные языки не закрываются при пересечении. Это можно увидеть, взяв языки и , которые не зависят от контекста. Их пересечение есть , что может быть показано, что неконтекстно неконтекстно с помощью леммы о накачке для контекстно-свободных языков . Как следствие, контекстно-свободные языки не могут быть закрыты при комплементарности, как и для любых языков A и B , их пересечение может быть выражено профсоюзом и дополнения: . В частности, контекстно-свободный язык не может быть закрыт при разнице, так как дополнение может быть выражено разностью: . ${\ 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 - регулярный язык, то и их пересечение, и их различие являются контекстно-свободными языками. ${\ Displaystyle L \ cap D}$ ${\ Displaystyle L \ setminus D}$

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

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

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

Эквивалентность: есть ? ${\ Displaystyle L (A) = L (B)}$
Несвязанность: есть ? Однако пересечение контекстно-свободного языка и обычного языка является контекстно-независимым, поэтому вариант проблемы, когда B - регулярная грамматика, разрешим (см. «Пустота» ниже). ${\ Displaystyle L (A) \ крышка L (B) = \ emptyset}$
Сдерживание: есть ? Опять же , вариант задачи , где B является регулярной грамматикой разрешим, в то время , когда регулярно , как правило , нет. ${\ Displaystyle L (A) \ substeq L (B)}$
Универсальность: есть ? ${\ Displaystyle L (A) = \ Sigma ^ {*}}$
Регулярность: это регулярный язык? ${\ Displaystyle L (A)}$
Неоднозначность: всякая ли грамматика неоднозначна? ${\ Displaystyle L (A)}$

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

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

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

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

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

Заметки

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

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

Languages

In other projects