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

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

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

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

Содержание

1 Предпосылки
- 1.1 Контекстно-свободная грамматика
- 1.2 Автоматы
2 Примеры
- 2.1 Язык Dyck
3 Свойства
- 3.1 Контекстно-зависимый анализ
- 3.2 Замыкание
  - 3.2.1 Незакрытие при пересечении, дополнении и различии
- 3.3 Разрешимость
- 3.4 Языки, не зависящие от контекста
4 Примечания
5 Ссылки
- 5.1 Цитируемые работы
6 Дополнительная литература

Предпосылки

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

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

Автоматы

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

Примеры

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

δ (q 0, a, z) = (q 0, az) δ (q 0, a, a) = (q 0, aa) δ (q 0, b, a) = (q 1, ε) δ (q 1, b, a) знак равно (q 1, ε) δ (q 1, ε, z) = (qf, ε) {\ 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}}}

{\ 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 является объединение ${a n b m c m d n | n, m>0} {\ displaystyle \ {a ^ {n} b ^ {m} c ^ {m} d ^ {n} | n, m>0 \}}$ $\{a^{n}b^{m}c^{m}d^{n}|n,m>0 \}$ с ${anbncmdm | n,>0} {\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} d ^ {m} | n, m>0 \}}$ $\{a^{n}b^{n}c^{m}d^{m}|n,m>0 \}$ . Этот набор контекстно-свободный, так как объединение двух контекстно-свободных языков всегда контекстно-независимое. Но нет способа однозначно проанализировать строки в (неконтекстно-независимом) подмножестве ${a n b n c n d n | п>0} {\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | n>0 \}}$ $\{a^{n}b^{n}c^{n}d^{n}|n>0 \}$ , который является пересечением этих двух языков.

Язык Дейка

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

Свойства

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

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

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

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

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

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

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

Закрытие

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

union $L ∪ P {\ displaystyle L \ cup P}$ $L \ cup P$ из L и P
обращение L
к конкатенации $L ⋅ P {\ displaystyle L \ cdot P}$ $L \ cdot P$ L и P
звезда Клини $L ∗ {\ displaystyle L ^ {*}}$ $L^{*}$ of L
изображение $φ (L) {\ displaystyle \ varphi (L)}$ $\ varphi (L)$ из L при гомоморфизме $φ {\ displaystyle \ varphi}$ $\ varphi$
изображение $φ - 1 (L) {\ displaystyle \ varphi ^ {- 1} (L)}$ $\ varphi ^ {- 1} (L)$ из L при обратном гомоморфизме $φ - 1 {\ displaystyle \ varphi ^ {- 1}}$ $\ varphi ^ {- 1}$
круговой сдвиг L (язык ${vu: uv ∈ L} {\ displaystyle \ {vu: uv \ in L \}}$ $\ {vu: uv \ in L \}$ )
префиксное закрытие L (набор всех префиксов строк из L)
частное L / R L на регулярном языке R

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

Контекстно-свободный язык участки не закрываются при пересечении. Это можно увидеть, взяв языки $A = {anbncm ∣ m, n ≥ 0} {\ displaystyle A = \ {a ^ {n} b ^ {n} c ^ {m} \ mid m, n \ geq 0 \}}$ $A = \ {a ^ {n} b ^ {n} c ^ {m} \ mid m, n \ geq 0 \}$ и $B = {ambncn ∣ m, n ≥ 0} {\ displaystyle B = \ {a ^ {m} b ^ {n} c ^ {n} \ mid m, n \ geq 0 \}}$ $B = \ {a ^ {m} b ^ {n} c ^ {n} \ mid m, n \ geq 0 \}$ , которые не зависят от контекста. Их пересечение: $A ∩ B = {anbncn ∣ n ≥ 0} {\ displaystyle A \ cap B = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ geq 0 \} }$ $A \ cap B = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ geq 0 \}$ , который может быть показан как неконтекстный с помощью леммы о перекачке для контекстно-свободных языков. Как следствие, контекстно-свободные языки не могут быть закрыты при дополнении, поскольку для любых языков A и B их пересечение может быть выражено объединением и дополнением: $A ∩ B = A ¯ ∪ B ¯ ¯ {\ displaystyle A \ cap B = {\ overline {{\ overline {A}} \ cup {\ overline {B}}}}}$ $A \ cap B = {\ overline { {\ overline {A}} \ cup {\ overline {B}}}}$ . В частности, контекстно-свободный язык нельзя замкнуть под разницей, поскольку дополнение может быть выражено разницей: $L ¯ = Σ ∗ ∖ L {\ displaystyle {\ overline {L}} = \ Sigma ^ {*} \ setminus L}$ ${\ displaystyle {\ overline {L}} = \ Sigma ^ {*} \ setminus L}$ .

Однако, если L - контекстно-свободный язык, а D - обычный язык, то их пересечение $L ∩ D {\ displaystyle L \ cap D}$ $L \ cap D$ и их различие $L ∖ D {\ displaystyle L \ setminus D}$ $L \ setminus D$ - это контекстно-свободные языки.

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

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

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

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

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

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

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

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

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

Примечания

Ссылки

Цитированные работы

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

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