Поскольку у ответа templatetypedef есть некоторые недостатки (которые я укажу через секунду в комментарии), я даю быстрый ответ на ваш вопрос:
Язык является контекстно-зависимым, если (и только если) вы можете дать недетерминированную машину Тьюринга, используя линейное пространство, которое определяет L.
Пусть L = {a ^ n b ^ n a ^ n} для произвольного целого числа n; a ^ n здесь означает n конкатенаций символа a. Это типичный контекстно-зависимый язык. Вместо предоставления CSG вы можете указать LBA, чтобы показать, что L является контекстно-зависимым:
Машина Тьюринга M «угадывает» (благодаря недетерминизму) n [другими словами, вы можете сказать, что «каждая ветвь недетерминированного дерева поиска пробует другой n], а затем проверяет, соответствует ли входные данные ^ nb ^ na ^ п. Вам нужно зарегистрировать n ячеек для хранения n, для соответствия может потребоваться (если реализуется тривиально) другой журнал n ячеек. Поскольку n + 2log n <2n, этой машине требуется только линейное пространство, и поэтому он является LBA, поэтому L является контекстно-зависимым. </p>