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

Question

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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