Рекурсивные языки против контекстно-зависимых языков
В иерархии Хомского множество рекурсивных языков не определено. Я знаю, что рекурсивные языки являются подмножеством рекурсивно перечислимых языков и что все рекурсивные языки разрешимы.
Что меня интересует, так это то, как рекурсивные языки сравниваются с контекстно-зависимыми языками. Могу ли я предположить, что контекстно-зависимые языки являются строгим подмножеством рекурсивных языков, и поэтому все контекстно-зависимые языки разрешимы?
4 ответа
Чтобы распознать рекурсивный язык, вам нужен своего рода автомат с именем Decider. Это именно машина Тьюринга, обманутая ограниченным потоком управления, то есть она всегда будет останавливаться.
Что касается контекстно-зависимых языков, они действительно являются подходящим подмножеством рекурсивных языков. Тривиально, что минимальный автомат для распознавания контекстно-зависимого языка, линейно ограниченный автомат, строго менее мощный, чем решающий. Я думаю, что это также можно было бы продемонстрировать на основе правил ограничения грамматики.
Набор контекстно-зависимых языков является подходящим подмножеством рекурсивных языков. Вы не должны предполагать это, обратитесь к книге Питера Линца для доказательства.
Если ваш вопрос только в том случае, если каждый контекстно-зависимый язык входит в набор всех рекурсивных языков, вы должны попытаться доказать это классическим способом с помощью формальных автоматов. Спросите себя, какой формальный автомат может симулировать генерацию контекстно-зависимого языка и что используется для генерации рекурсивного языка. Тогда просто попытайтесь смоделировать одно, используя другое. Как только вы найдете нужные учебники в своем учебнике, вы наверняка сможете доказать, что вы хотите.
Согласно книге Пападимитриу (3.4.2 (e)), контекстно-зависимые грамматики эквивалентны NSPACE(n), который является надлежащим подмножеством рекурсивных языков. Так что да, ваше предположение верно.
Согласно моим ссылкам, я бы также сказал, что контекстно-зависимые языки являются правильным подмножеством набора всех рекурсивных языков. Вы можете найти это доказательство в любом стандартном учебнике, например
> Введение в формальные языки и автоматы (издание 5) Питера Линца