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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Роте, Йорг (2005), Теория сложности и криптология , Тексты по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag, стр. 77, ISBN 978-3-540-22147-0, г-н  2164257.
2. Одифредди, ПГ (1999), Классическая теория рекурсии. Том II , Исследования по логике и основаниям математики, том 143, Амстердам: North-Holland Publishing Co., стр. 236, ISBN 978-0-444-50205-6, г-н  1718169.
3. Пуллум, Джеффри К. (1983). Контекстная свобода и компьютерная обработка человеческих языков. Труды 21-го ежегодного собрания ACL .
4. Бах, Э. (1981). «Разрывные составляющие в обобщенных категориальных грамматиках» Архивировано 21 января 2014 г. в Wayback Machine . NELS , т. 11, стр. 1–12.
5. Джоши, А.; Виджай-Шанкер, К.; и Вейр, Д. (1991). «Конвергенция умеренно контекстно-зависимых грамматических формализмов». В: Селлс, П., Шибер, С.М. и Васоу, Т. (редакторы). Основополагающие вопросы обработки естественного языка . Кембридж, Массачусетс: Брэдфорд.
6. Пример 9.5 (стр. 224) Хопкрофта, Джона Э.; Ульмана, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли
7. J. Hartmanis и H. Shank (июль 1968). «О распознавании простых чисел автоматами» (PDF) . Journal of the ACM . 15 (3): 382–389. doi :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) . SIAM J. Comput . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . doi :10.1137/0217058. Архивировано (PDF) из оригинала 2004-06-25. 

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