Comment faire pour déterminer si une langue est récursive ou récursivement énumérable?

J'ai pour déterminer si une langue (par exemple L={a^n b^m c^s | 0<=n<=m<=s}) est régulier, libre de tout contexte, récursive, récursivement énumérable ou aucun d'eux.

Je sais comment faire pour déterminer si un langage est régulier (trouver un DFA ou de l'expression régulière qui fonctionne) ou le contexte-gratuit (trouvez un PDA ou un contexte de grammaire qui fonctionne); je sais que récursive de la langue a une machine de Turing qui toujours s'arrête et qu'un récursivement énumérable langue a une machine de Turing qui ne peut pas s'arrêter.

La question est donc: est-il rapide des critères pour déterminer si la langue est récursive ou récursivement énumérable ou aucun des deux? Par exemple, je n'ai pas à construire un PDA pour comprendre qu'une langue est libre de tout contexte, je ne peux pas le voir par le fait qu'elle nécessite une pile; est-il un analogue rapide de l'approche pour le problème (qui, espérons-le sauve de la peine à construire une machine de Turing)?

OriginalL'auteur Jacob | 2011-02-16