как я могу показать, что язык является контекстно-зависимым с помощью недетерминированной машины Тьюринга?
я знаю, что язык, который принимается автоматом с линейной привязкой (LBA), является контекстно-зависимым языком. А LBA — это недетерминированная машина Тьюринга.
Любая идея, как я могу связать все это и показать, что язык является контекстно-зависимым?
Поскольку ответ templatetypedef имеет некоторые недостатки (на которые я укажу через секунду в комментарии), я даю быстрый ответ на ваш вопрос:
Язык является контекстно-зависимым, если (и только если) вы можете дать недетерминированную машину Тьюринга, используя линейное пространство, которое определяет L.
Пусть L = {a^n b^n a^n} для произвольного целого числа n; a^n здесь означает n конкатенаций символа a. Это типичный контекстно-зависимый язык. Вместо предоставления CSG вы можете указать LBA, чтобы показать, что L является контекстно-зависимым:
Машина Тьюринга M «угадывает» (благодаря недетерминизму) n [другими словами, вы можете сказать, что «каждая ветвь недетерминированного дерева поиска пробует другое n», а затем проверяет, соответствует ли ввод a^n b^n a^n. Вам нужно log n ячеек для хранения n, для сопоставления может потребоваться (если реализовано тривиально) еще log n ячеек. Поскольку n + 2log n ‹ 2n, этой машине требуется только линейное пространство, и поэтому она является LBA, следовательно, L контекстно-зависима.
Это не точный ответ, но поскольку контекстно-зависимые языки — это именно те, которые принимаются автоматом с линейными ограничениями (ТМ с O(n) пространством на ленте), то контекстно-зависимые языки — это именно те, которые находятся в DSPACE(n). ). Более того, мы знаем, что NTIME(n) = DSPACE(n). Это означает, что если вы можете найти NTM с линейным временем, который определяет принадлежность к некоторому языку L, этот язык должен быть контекстно-зависимым. Тем не менее, все еще может быть контекстно-зависимый язык, который не имеет NTM с линейным временем (я не знаю, есть ли на это окончательный ответ или это открытая проблема), так что это не точная характеристика .
Надеюсь это поможет!
