Все ли контекстно-зависимые языки разрешимы?

12

Я просматривал определение контекстно-зависимого языка в Википедии и обнаружил следующее:

Каждая категория языков является надлежащим подмножеством категории прямо над ней. Любой автомат и любая грамматика в каждой категории имеют эквивалентный автомат или грамматику в категории непосредственно над ней.

Я мог видеть, что линейно ограниченный автомат находится прямо под решающим элементом в порядке статьи. Если это так, то это означает, что все вычисления в LBA будут остановлены в какой-то момент (поскольку каждый LBA будет решающим). Но я чувствую, что могут быть некоторые вычисления, которые могут выполняться на LBA в то же время, чтобы никогда не останавливаться. Например, мы можем написать вычисление на LBA, которое бы

  1. прочитайте первый символ на ленте и двигайтесь вправо;
  2. прочитайте следующий символ и двигайтесь назад налево.

Это (бесполезное) вычисление (которое, очевидно, является вычислением LB) будет выполняться бесконечно с колебаниями влево и вправо и никогда не останавливаться и, следовательно, не может быть решающим. Где я не так думаю?

formal-grammars turing-machines undecidability context-sensitive bongubj
источник
1
Решение CSL не зависит от того, существуют ли LBA без завершения: для этого должен существовать только LBA.
Рафаэль

Ответы:

9

Во-первых, все контекстно-зависимые языки являются разрешимыми, поскольку они могут быть приняты LBA (как вы сказали), и машина Тьюринга является более мощной, чем LBA.

MM′MM′

A.Schulz
источник
Если кто-то все еще не понял этот ответ, я предлагаю вам обратиться к слайду 3-4 этой презентации для получения дополнительных пояснений.
Bongubj
0

Я предлагаю вам взглянуть на эту книгу: « Введение в языки и теория вычислений» Джона Е. Мартина

стр. 283. Все еще остаются открытые вопросы, касающиеся контекстно-зависимых языков, например, может ли каждый CSL быть принят детерминистическим LBA.

Амир Никабади
источник
Как это отвечает на вопрос? Все контекстно-зависимые языки являются разрешимыми, независимо от того, требуется ли вам детерминированное или недетерминированное линейное пространство.
Юваль