Я просматривал определение контекстно-зависимого языка в Википедии и обнаружил следующее:
Каждая категория языков является надлежащим подмножеством категории прямо над ней. Любой автомат и любая грамматика в каждой категории имеют эквивалентный автомат или грамматику в категории непосредственно над ней.
Я мог видеть, что линейно ограниченный автомат находится прямо под решающим элементом в порядке статьи. Если это так, то это означает, что все вычисления в LBA будут остановлены в какой-то момент (поскольку каждый LBA будет решающим). Но я чувствую, что могут быть некоторые вычисления, которые могут выполняться на LBA в то же время, чтобы никогда не останавливаться. Например, мы можем написать вычисление на LBA, которое бы
- прочитайте первый символ на ленте и двигайтесь вправо;
- прочитайте следующий символ и двигайтесь назад налево.
Это (бесполезное) вычисление (которое, очевидно, является вычислением LB) будет выполняться бесконечно с колебаниями влево и вправо и никогда не останавливаться и, следовательно, не может быть решающим. Где я не так думаю?
Ответы:
Во-первых, все контекстно-зависимые языки являются разрешимыми, поскольку они могут быть приняты LBA (как вы сказали), и машина Тьюринга является более мощной, чем LBA.
источник
Я предлагаю вам взглянуть на эту книгу: « Введение в языки и теория вычислений» Джона Е. Мартина
стр. 283. Все еще остаются открытые вопросы, касающиеся контекстно-зависимых языков, например, может ли каждый CSL быть принят детерминистическим LBA.
источник