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

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

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

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

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

Примеры

Один из простейших контекстно-зависимых, но не контекстно-свободных языков : язык всех строк, состоящих из n вхождений символа «a», затем n «b», затем n «c» (abc, aabbcc , aaabbbccc и т. д.). Надмножество этого языка, называемое языком Баха, определяется как набор всех строк, где «a», «b» и «c» (или любой другой набор из трех символов) встречается одинаково часто (aabccb, baabcaccb и т. Д. ), а также зависит от контекста. ${\ 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 \}}$${\ displaystyle L_ {m ^ {3}} = \ {a ^ {m ^ {3}}: m> 1 \}}$

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

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

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

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

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

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

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

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

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

использованная литература

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