Введение

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

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

С точки зрения вычислений, контекстно-зависимый язык эквивалентен линейно ограниченной недетерминированной машине Тьюринга, также называемой линейно ограниченным автоматом. Это недетерминированная машина Тьюринга с лентой, содержащей только *n* ячеек, где *n* – размер входных данных, а *k* – константа, связанная с машиной. Это означает, что любой формальный язык, распознаваемый такой машиной, является контекстно-зависимым, и любой контекстно-зависимый язык может быть распознан такой машиной. Этот класс языков также известен как NLINSPACE или NSPACE(O(n)), поскольку они могут быть распознаны с использованием линейного пространства на недетерминированной машине Тьюринга. Класс LINSPACE (или DSPACE(O(n))) определяется аналогично, но с использованием детерминированной машины Тьюринга. Очевидно, что LINSPACE является подмножеством NLINSPACE, но неизвестно, верно ли, что LINSPACE = NLINSPACE.

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

Союз, пересечение и конкатенация двух контекстно-зависимых языков являются контекстно-зависимыми, а также звездой Клине контекстно-зависимого языка является контекстно-зависимым. Дополнение контекстно-зависимого языка само является контекстно-зависимым, что известно как теорема Иммермана — Селепчени. Проверка принадлежности строки языку, определенному произвольной контекстно-зависимой грамматикой или произвольной детерминированной контекстно-зависимой грамматикой, является задачей, полной по классу PSPACE.