Контекстно-зависимый язык

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

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

Содержание

1 Вычислительные свойства
2 Примеры
3 Свойства контекстно-зависимых языков
4 См. Также
5 Ссылки

Вычислительные свойства

В вычислительном отношении контекстно-зависимый язык эквивалентен линейно ограниченной недетерминированной машине Тьюринга, также называемой линейно-ограниченным автоматом. Это недетерминированная машина Тьюринга с лентой только из $kn {\ displaystyle kn}$ ${\ displaystyle kn}$ ячеек, где $n {\ displaystyle n}$ $n$ - размер вход и $k {\ displaystyle k}$ $k$ - константа, связанная с машиной. Это означает, что каждый формальный язык, который может быть определен такой машиной, является контекстно-зависимым языком, и любой контекстно-зависимый язык может быть определен такой машиной.

Этот набор языков также известен как NLINSPACE или NSPACE (O (n)), потому что они могут быть приняты с использованием линейного пространства на недетерминированном Тьюринге. машина. Класс LINSPACE (или DSPACE (O (n))) определяется одинаково, за исключением использования детерминированной машины Тьюринга. Очевидно, что LINSPACE является подмножеством NLINSPACE, но неизвестно, LINSPACE = NLINSPACE .

Примеры

Один из Самый простой контекстно-зависимый, но не контекстно-свободный язык: $L = {anbncn: n ≥ 1} {\ displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n}: n \ geq 1 \}}$ $L = \ {a ^ {n} b ^ {n} c ^ {n}: n \ geq 1 \}$ : язык всех строк, состоящих из n вхождений символа "a", затем n "b", затем n "c" (abc, aabbcc, aaabbbccc и т. Д..). Надмножество этого языка, называемое языком Баха, определяется как набор всех строк, где «a», «b» и «c» (или любой другой набор из трех символов) встречается одинаково часто (aabccb, baabcaccb и т. Д.), а также является контекстно-зависимым.

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

Аналогично:

$LC ross = {ambncmdn: m ≥ 1, n ≥ 1} {\ displaystyle L_ {Cross} = \ {a ^ {m} b ^ {n} c ^ {m} d ^ {n}: m \ geq 1, n \ geq 1 \}}$ ${\ displaystyle L_ {Cross} = \ {a ^ {m} b ^ {n } c ^ {m} d ^ {n}: m \ geq 1, n \ geq 1 \}}$ - еще один контекстно-зависимый язык; соответствующую контекстно-зависимую грамматику можно легко спроецировать, начиная с двух контекстно-свободных грамматик, генерирующих предложения в форматах $am C m {\ displaystyle a ^ {m} C ^ {m}}$ ${\ displaystyle a ^ {m} C ^ {m}}$ и $B ndn {\ displaystyle B ^ {n} d ^ {n}}$ ${\ displaystyle B ^ {n} d ^ {n}}$ с последующим добавлением к ним перестановки, например $CB → BC {\ displaystyle CB \ rightarrow BC}$ ${\ displaystyle CB \ rightarrow BC}$ , новый начальный символ и стандартный синтаксический сахар.

$LMUL 3 = {ambncmn: m ≥ 1, n ≥ 1} {\ displaystyle L_ {MUL3} = \ {a ^ {m} b ^ {n} c ^ {mn}: m \ geq 1, n \ geq 1 \}}$ ${\ displaystyle L_ {MUL3} = \ {a ^ {m} b ^ {n} c ^ {mn}: m \ geq 1, n \ geq 1 \}}$ - еще один контекстно-зависимый язык (цифра «3» в названии этого языка означает троичный алфавит); то есть операция «product» определяет контекстно-зависимый язык (но «сумма» определяет только контекстно-свободный язык как грамматика $S → a S c | R {\ displaystyle S \ rightarrow aSc | R}$ ${\ displaystyle S \ rightarrow aSc | R}$ и $R → b R c | bc {\ displaystyle R \ rightarrow bRc | bc}$ ${\ displaystyle R \ rightarrow bRc | bc}$ показывает). Из-за коммутативности продукта наиболее интуитивная грамматика для $L M U L 3 {\ displaystyle L_ {MUL3}}$ ${\ displaystyle L_ {MUL3}}$ неоднозначна. Этой проблемы можно избежать, если использовать более ограничительное определение языка, например $L O R D M U L 3 = {a m b n c m n: 1 < m < n } {\displaystyle L_{ORDMUL3}=\{a^{m}b^{n}c^{mn}:1$ ${\ displaystyle L_ {ORDMUL3} = \ {a ^ {m} b ^ {n} c ^ {mn}: 1 <m <n \}}$ . Это может быть специализировано на $LMUL 1 = {amn: m>1, n>1} {\ displaystyle L_ {MUL1} = \ {a ^ {mn}: m>1, n>1 \}}$ $L_{MUL1}=\{a^{mn}:m>1, n>1 \}$ и отсюда до $L m 2 = {am 2: m>1} {\ displaystyle L_ {m ^ {2}} = \ {a ^ {m ^ {2}}: m>1 \}}$ $L_{m^{2}}=\{a^{m^{2}}:m>1 \}$ , $L m 3 = {am 3: m>1} {\ displaystyle L_ {m ^ {3}} = \ {a ^ {m ^ {3}}: m>1 \} }$ $L_{m^{3}}=\{a^{m^{3}}:m>1 \}$ и т. д.

$LREP = {w | w |: w ∈ Σ ∗} {\ displaystyle L_ {REP} = \ {w ^ {| w |}: w \ in \ Sigma ^ {*} \} }$ ${\ displaystyle L_ { REP} = \ {w ^ {| w |}: w \ in \ Sigma ^ {*} \}}$ - это контекстно-зависимый язык. Соответствующая контекстно-зависимая грамматика может быть получена как обобщение контекстно-зависимой грамматики. Марс для $LS quare = {w 2: w ∈ Σ ∗} {\ displaystyle L_ {Square} = \ {w ^ {2}: w \ in \ Sigma ^ {*} \}}$ ${\ displaystyle L_ {Squar e} = \ {w ^ {2}: w \ in \ Sigma ^ {*} \}}$ , $LC ube = {w 3: w ∈ Σ ∗} {\ displaystyle L_ {Cube} = \ {w ^ {3}: w \ in \ Sigma ^ {*} \}}$ ${\ displaystyle L_ {Cube} = \ {w ^ {3}: w \ in \ Сигма ^ {*} \}}$ и т. д.

$LEXP = {a 2 n: n ≥ 1} {\ displaystyle L_ {EXP} = \ {a ^ {2 ^ {n}}: n \ geq 1 \}}$ ${\ displaystyle L_ {EXP} = \ {a ^ {2 ^ {n}}: п \ geq 1 \}}$ - это контекстно-зависимый язык.

$LPRIMES 2 = {w: | w | является простым} {\ displaystyle L_ {PRIMES2} = \ {w: | w | {\ t_dv {is prime}} \}}$ ${\ displaystyle L_ {PRIMES2} = \ {w: | w | {\ t_dv {равно prime}} \}}$ является контекстно-зависимым языком («2» в названии этот язык предназначен для обозначения двоичного алфавита). Это было доказано Хартманисом с помощью лемм о накачке для обычных и контекстно-свободных языков над двоичным алфавитом и, после этого, наброска линейного ограниченного многоленточного автомата, принимающего $LPRIMES 2 {\ displaystyle L_ {PRIMES2}}$ ${\ displaystyle L_ {PRIMES2}}$ .

$LPRIMES 1 = {ap: p является простым} {\ displaystyle L_ {PRIMES1} = \ {a ^ {p}: p {\ t_dv {is prime}} \}}$ ${\ displaystyle L_ {PRIMES1} = \ {a ^ {p}: p {\ t_dv {is prime}} \}}$ - это контекстно-зависимый язык (" 1 "в названии этого языка означает унарный алфавит). Это было приписано А. Саломаа Матти Сойттоле с помощью линейного ограниченного автомата над унарным алфавитом (страницы 213-214, упражнение 6.8), а также Марти Пенттонену с помощью контекстно-зависимой грамматики также над унарным алфавитом (см. : Формальные языки А. Саломаа, стр. 14, пример 2.5).

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

Свойства контекстно-зависимых языков

Объединение, пересечение, конкатенация двух контекстно-зависимых языков зависит от контекста, также Клини плюс контекстно-зависимого языка является контекстом -чувствительный.
Дополнение контекстно-зависимого языка само по себе является контекстно-зависимым результатом, известным как теорема Иммермана – Селепсеньи.
Принадлежность строки к языку, определенному произвольным контекстом. чувствительная грамматика, или произвольная детерминированная контекстно-зависимая грамматика, является проблемой PSPACE-complete.

См. также

Линейный ограниченный автомат
Список генераторов синтаксического анализатора для контекстно-зависимых языков
Иерархия Хомского
Индексированные языки - строгое подмножество контекстно-зависимых языков
Иерархия Вейра

Ссылки

Сипсер, М. (1996), Введение в теорию вычислений, PWS Издательская компания