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

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

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

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

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

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

Одним из простейших контекстно-зависимых, но не контекстно-свободных языков является $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ : язык всех строк, состоящих из $n$ вхождений символа «a», затем $n$ «b», затем $n$ «c» (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» в названии этого языка означает троичный алфавит); то есть операция «произведение» определяет контекстно-зависимый язык (но «сумма» определяет только контекстно-свободный язык, поскольку грамматика $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), а также Марти Пенттонену с помощью контекстно-зависимой грамматики также по унарному алфавиту (см.: Формальные языки А. Саломаа, стр. 14, пример 2.5).

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

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

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

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

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

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

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

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

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

[2] Одифредди, П.Г. (1999), Классическая теория рекурсии. Том. II , Исследования по логике и основам математики, том. 143, Амстердам: Издательство Северной Голландии, с. 236, ISBN 978-0-444-50205-6 , МР 1718169 .

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

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

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

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

[7] Дж. Хартманис и Х. Шанк (июль 1968 г.). «О распознавании простых чисел автоматами» (PDF) . Журнал АКМ . 15 (3): 382–389. дои : 10.1145/321466.321470 . hdl : 1813/5864 . S2CID 17998039 .

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

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

[10] Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . СИАМ Дж. Компьютер . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . дои : 10.1137/0217058 . Архивировано (PDF) из оригинала 25 июня 2004 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]