Контекстно-зависимый язык с недетерминированной машиной Тьюринга
Как я могу показать, что язык чувствителен к контексту с недетерминированной машиной Тьюринга?
я знаю, что язык, который принимается линейно-связанным автоматом (LBA), является контекстно-зависимым языком. А LBA - это недетерминированная машина Тьюринга.
Любая идея, как я могу связать все это и показать, что язык чувствителен к контексту?
2 ответа
Поскольку ответ 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 ячеек. Поскольку n + 2log n <2n, этой машине требуется только линейное пространство, и поэтому он является LBA, следовательно, L является контекстно-зависимым.
Это не точный ответ, но поскольку контекстно-зависимые языки - это в точности те языки, которые принимаются автоматом с линейными ограничениями (ТМ с пространством O(n) на ленте), контекстно-зависимые языки - это именно те языки в DSPACE(n). Более того, мы знаем, что NTIME (n) = DSPACE (n). Это означает, что если вы можете найти NTM с линейным временем, который определяет членство в каком-либо языке L, этот язык должен быть контекстно-зависимым. Тем не менее, все еще может существовать контекстно-зависимый язык, который не имеет NTM с линейным временем (я не знаю, есть ли однозначный ответ на это или это открытая проблема), так что это не точная характеристика,
Надеюсь это поможет!