Изменения

Если язык <tex>L</tex> принимается линейно ограниченным автоматом, то <tex>L</tex> — контекстно-зависимый язык.

|proof=

Для доказательства этой теоремы построим контекстно-зависимую грамматику, которая моделирует линейно ограниченный автомат.

Нетерминалы контекстно-зависимой грамматики должны указывать не только первоначальное содержание некоторой ячейки ленты lba, но также и то, является ли эта ячейка смежной с концевым маркером слева или справа. Такие ячейки в обозначении нетерминалов мы будем снабжать маркерами <tex>\#</tex> и <tex>\$</tex>, обозначающими, что ячейка граничит соответственно с левым, правым или обоими концевыми маркерами. В обозначении нетерминала состояние lba должно также комбинироваться с символом, находящимся под головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных символов для концевых маркеров и состояния линейно ограниченного автомата, потому что эти символы должны были бы заменяться на пустые цепочки, когда строка превращается в терминальную, а <tex>\epsilon</tex>-порождения в контекстно-зависимой грамматике запрещены.

* Операции, которые симулируют некоторую последовательность действий lba <tex>M</tex>. Во время их выполнения, одна из двух копий оригинальной строки остается неизменной, другая же представляет из себя входную ленту <tex>M</tex> и соответствующе изменяется.

* Операции, которые могут удалить всё кроме не измененной копии строки. Применяются, когда, симулированная на другой копии исходной строки, последовательность действий lba <tex>M</tex> привела к принимающему состоянию.

}}