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

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

Вычислительные свойства [ править ]

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

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

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

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

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

По аналогии:

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

${\ displaystyle L_ {MUL3} = \ {a ^ {m} b ^ {n} c ^ {mn}: m \ geq 1, n \ geq 1 \}}$ - еще один контекстно-зависимый язык (цифра «3» в названии этого языка предназначена для обозначения троичного алфавита); то есть операция «product» определяет контекстно-зависимый язык (но «сумма» определяет только контекстно-свободный язык как грамматику и показывает). Из-за коммутативности продукта наиболее интуитивно понятная грамматика для неоднозначна. Этой проблемы можно избежать, если использовать более ограничительное определение языка, например . Это может быть специализировано на and, from this, to , и т. Д. ${\ Displaystyle S \ rightarrow aSc | R}$ ${\ Displaystyle R \ rightarrow bRc | bc}$ ${\ displaystyle L_ {MUL3}}$ ${\ displaystyle L_ {ORDMUL3} = \ {a ^ {m} b ^ {n} c ^ {mn}: 1 <m <n \}}$ ${\ displaystyle L_ {MUL1} = \ {a ^ {mn}: m> 1, n> 1 \}}$ ${\ Displaystyle L_ {м ^ {2}} = \ {а ^ {м ^ {2}}: м> 1 \}}$ $L_{m^{3}}=\{a^{m^{3}}:m>1\}$

$L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}$ является контекстно-зависимым языком. Соответствующая контекстно-зависимая грамматика может быть получена как обобщение контекстно-зависимых грамматик для , и т.д. $L_{Square}=\{w^{2}:w\in \Sigma ^{*}\}$ $L_{Cube}=\{w^{3}:w\in \Sigma ^{*}\}$

$L_{EXP}=\{a^{2^{n}}:n\geq 1\}$ является контекстно-зависимым языком. ^[6]

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

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

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

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

Объединение, пересечение, конкатенация двух контекстно-зависимых языков зависит от контекста, а также Kleene plus контекстно-зависимого языка зависит от контекста. ^[9]
Дополнение контекстно-зависимого языка само по себе зависит от контекста ^[10], что известно как теорема Иммермана – Селепсеньи .
Принадлежность строки к языку, определенному произвольной контекстно-зависимой грамматикой или произвольной детерминированной контекстно-зависимой грамматикой, является полной проблемой PSPACE .

См. Также [ править ]

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

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

^ Роте, Йорг (2005), Теория сложности и криптология , Тексты в теоретической информатике. Серия EATCS, Берлин: Springer-Verlag, стр. 77, ISBN 978-3-540-22147-0, Руководство по ремонту 2164257.
^ Odifreddi, PG (1999), Классическая теория рекурсии. Vol. II , Исследования по логике и основам математики, 143 , Амстердам: North-Holland Publishing Co., стр. 236, ISBN 978-0-444-50205-6, MR 1718169.
^ Пуллум, Джеффри К. (1983). Контекстная свобода и компьютерная обработка человеческих языков . Proc. 21-е ежегодное собрание ACL .
Перейти ↑ Bach, E. (1981). «Прерывистые составляющие в обобщенных категориальных грамматиках». Архивировано 21 января 2014 г. в Wayback Machine . НЭЛС , т. 11. С. 1–12.
^ Джоши, А .; Виджай-Шанкер, К .; и Вейр Д. (1991). «Конвергенция умеренно контекстно-зависимых грамматических формализмов». В: Селлс, П., Шибер, С.М. и Вазоу, Т. (редакторы). Основные проблемы обработки естественного языка . Кембридж, Массачусетс: Брэдфорд.
^ Пример 9.5 (стр. 224) Хопкрофта, Джона Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли
↑ Дж. Хартманис и Х. Шэнк (июль 1968 г.). «О распознавании простых чисел автоматами» (PDF) . Журнал ACM . 15 (3): 382–389. DOI : 10.1145 / 321466.321470 .
^ Саломаа, Арто (1969), Теория автоматов , ISBN 978-0-08-013376-8 , Пергамон, 276 страниц. DOI : 10.1016 / C2013-0-02221-9
^ Джон Э. Хопкрофт; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли.; Упражнение 9.10, стр. 230. В издании 2000 года была опущена глава о контекстно-зависимых языках.
^ Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . SIAM J. Comput . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . DOI : 10.1137 / 0217058 .

Сипсер, М. (1996), Введение в теорию вычислений , PWS Publishing Co.

[1] Роте, Йорг (2005), Теория сложности и криптология , Тексты в теоретической информатике. Серия EATCS, Берлин: Springer-Verlag, стр. 77, ISBN 978-3-540-22147-0, Руководство по ремонту 2164257.

[2] Odifreddi, PG (1999), Классическая теория рекурсии. Vol. II , Исследования по логике и основам математики, 143 , Амстердам: North-Holland Publishing Co., стр. 236, ISBN 978-0-444-50205-6, MR 1718169.

[3] Пуллум, Джеффри К. (1983). Контекстная свобода и компьютерная обработка человеческих языков . Proc. 21-е ежегодное собрание ACL .

[4] Перейти ↑ Bach, E. (1981). «Прерывистые составляющие в обобщенных категориальных грамматиках». Архивировано 21 января 2014 г. в Wayback Machine . НЭЛС , т. 11. С. 1–12.

[5] Джоши, А .; Виджай-Шанкер, К .; и Вейр Д. (1991). «Конвергенция умеренно контекстно-зависимых грамматических формализмов». В: Селлс, П., Шибер, С.М. и Вазоу, Т. (редакторы). Основные проблемы обработки естественного языка . Кембридж, Массачусетс: Брэдфорд.

[6] Пример 9.5 (стр. 224) Хопкрофта, Джона Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли

[7] Дж. Хартманис и Х. Шэнк (июль 1968 г.). «О распознавании простых чисел автоматами» (PDF) . Журнал ACM . 15 (3): 382–389. DOI : 10.1145 / 321466.321470 .

[8] Саломаа, Арто (1969), Теория автоматов , ISBN 978-0-08-013376-8 , Пергамон, 276 страниц. DOI : 10.1016 / C2013-0-02221-9

[9] Джон Э. Хопкрофт; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли.; Упражнение 9.10, стр. 230. В издании 2000 года была опущена глава о контекстно-зависимых языках.

[10] Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . SIAM J. Comput . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . DOI : 10.1137 / 0217058 .

[1]