Контексту-чувствительный язык

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

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

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

Этот набор языков также известен как nlinspace или nspace ( o ( n )), потому что их можно принять с использованием линейного пространства на неэтерминированной машине Тьюринга. ^{[ 1 ]} Класс Linspace (или Dspace ( O ( n ))) определяется так же, за исключением использования детерминированной машины Turing. Очевидно, что Linspace является подмножеством Nlinspace, но неизвестно, является ли Linspace = nlinspace. ^{[ 2 ]}

Примеры

Одним из самых простых контекстных, но не контекстных языков. $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ : Язык всех строк, состоящих из $N$ вхождений символа «a», затем $n$ "b" s, затем $n$ "c" s (abc, aabbcc, aaabbbccc и т. Д.). Суперсет этого языка, называемый языком Баха, ^{[ 3 ]} определяется как набор всех строк, где «A», «B» и «C» (или любой другой набор из трех символов) встречается одинаково часто (AABCCB, BAABCACCB и т. Д.) И также зависит от контекста. ^{[ 4 ]}^{[ 5 ]}

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

Сходным образом:

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

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

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

$L_{\textit {EXP}}=\{a^{2^{n}}:n\geq 1\}$ это контекстный язык. ^{[ 6 ]}

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

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

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

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

Союз . , пересечение , объединение двух контекстно-чувствительных языков является чувствительным к контексту, а также Kleene Plus контекстно-чувствительного языка является чувствительным к контексту ^{[ 9 ]}
Дополнение контекстно-чувствительного к контексту сама по себе является чувствительным к контексту ^{[ 10 ]} Результат, известный как теорема Иммермана -Валленти .
Членство строки на языке, определенном произвольной грамматикой, чувствительной к контексту, или произвольной детерминированной грамматикой, чувствительной к контексте, является проблемой , полной PSPACE .

Смотрите также

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

Ссылки

^ Rothe, Jörg (2005), Теория сложности и криптология , тексты в теоретической информатике. Серия Eatcs, Берлин: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0 , MR 2164257 .
^ Odifreddi, PG (1999), Классическая теория рекурсии. Тол. II , исследования по логике и основаниям математики, вып. 143, Амстердам: Северо-Голландия Publishing Co., p. 236, ISBN 978-0-444-50205-6 , Мистер 1718169 .
^ Пуллум, Джеффри К. (1983). Контекст-слазия и компьютерная обработка человеческих языков . Прокурор 21 -е годовое собрание ACL .
^ Bach, E. (1981). «Прерывистые избиратели в обобщенных категориальных грамматах» архивировали 2014-01-21 на машине Wayback . Нельс , вып. 11, с. 1–12.
^ Джоши, А.; Vijay-Shanker, K.; и Вейр Д. (1991). «Конвергенция слегка контекстно-чувствительных грамматических формализмов». В кн.: Sells, P., Shieber, SM и Wasow, T. (редакторы). Основополагающие проблемы в обработке естественного языка . Кембридж М., Брэдфорд.
^ Пример 9.5 (стр. 224) Hopcroft, John E.; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Аддисон-Уэсли
^ Дж. Харманис и Х. Шэнк (июль 1968 г.). . (PDF ) Журнал ACM 15 (3): 382–3 doi : 10.1145/321466.31470 . HDL : 1813/5864 . 17998039S2CID
^ Salomaa, Arto (1969), Теория Automata , ISBN 978-0-08-013376-8 , Pergamon, 276 страниц. Два : 10.1016/c2013-0-02221-9
^ Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 9780201029888 Полем ; Упражнение 9.10, с.230. В издании 2000 года глава о контекстно-чувствительных языках была опущена.
^ Immerman, Neil (1988). «Недейтерминированное пространство закрыто при комплементации» (PDF) . Siam J. Comput . 17 (5): 935–938. Citeseerx 10.1.1.54.5941 . doi : 10.1137/0217058 . Архивировано (PDF) из оригинала 2004-06-25.

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

[1] Rothe, Jörg (2005), Теория сложности и криптология , тексты в теоретической информатике. Серия Eatcs, Берлин: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0 , MR 2164257 .

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

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

[4] Bach, E. (1981). «Прерывистые избиратели в обобщенных категориальных грамматах» архивировали 2014-01-21 на машине Wayback . Нельс , вып. 11, с. 1–12.

[5] Джоши, А.; Vijay-Shanker, K.; и Вейр Д. (1991). «Конвергенция слегка контекстно-чувствительных грамматических формализмов». В кн.: Sells, P., Shieber, SM и Wasow, T. (редакторы). Основополагающие проблемы в обработке естественного языка . Кембридж М., Брэдфорд.

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

[7] Дж. Харманис и Х. Шэнк (июль 1968 г.). . (PDF ) Журнал ACM 15 (3): 382–3 doi : 10.1145/321466.31470 . HDL : 1813/5864 . 17998039S2CID

[8] Salomaa, Arto (1969), Теория Automata , ISBN 978-0-08-013376-8 , Pergamon, 276 страниц. Два : 10.1016/c2013-0-02221-9

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

[10] Immerman, Neil (1988). «Недейтерминированное пространство закрыто при комплементации» (PDF) . Siam J. Comput . 17 (5): 935–938. Citeseerx 10.1.1.54.5941 . doi : 10.1137/0217058 . Архивировано (PDF) из оригинала 2004-06-25.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]