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