Рекурсивные языки против контекстно-зависимых языков

Question

В иерархии Хомского множество рекурсивных языков не определено. Я знаю, что рекурсивные языки являются подмножеством рекурсивно перечислимых языков и что все рекурсивные языки разрешимы.

Что мне интересно, так это сравнение рекурсивных языков с контекстно-зависимыми языками. Могу ли я предположить, что контекстно-зависимые языки являются строгим подмножеством рекурсивных языков, и поэтому все контекстно-зависимые языки разрешимы?

Answer 1

набор контекстно-зависимых языков является подходящим подмножеством рекурсивных языков.Вы не должны предполагать это, обратитесь к книге Питера Линца для доказательства.

Answer 2

Для распознавания рекурсивного языка вам нужен своего рода автомат с именем Decider . Это именно машина Тьюринга, обманутая ограниченным потоком управления, то есть она всегда будет останавливаться.

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

Answer 3

Если ваш вопрос только в том случае, если каждый контекстно-зависимый язык входит в набор всех рекурсивных языков, вы должны попытаться доказать это классическим способом с помощью формальных автоматов.Спросите себя, какой формальный автомат может симулировать генерацию контекстно-зависимого языка и что используется для генерации рекурсивного языка.Тогда просто попытайтесь смоделировать одно, используя другое.Как только вы найдете нужные учебники в своем учебнике, вы наверняка сможете доказать, что вы хотите.

Answer 4

Согласно книге Пападимитриу (3.4.2 (e)) контекстно-зависимые грамматики эквивалентны NSPACE (n), который является надлежащим подмножеством рекурсивных языков. Так что да, ваше предположение верно.