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

  1. 5

    Il n'y a pas de solution structurelle pour vérifier si une langue est récursive contre récursivement énumérable. Il y a en fait un vraiment cool preuve qui dit que pour tout automate capable de reconnaître l'récursive langues, il y a au moins un RE langue qui n'est pas dans R que l'automate accepte aussi; c'est une variante de la diagonalisation de l'argument que vous utilisez pour montrer l'existence de indécidable problèmes.

    La principale façon dont vous le prouver, une langue est en RE, mais pas de R est de prouver que la langue est en RE (peut-être par la définition d'un TM), puis de réduire d'un problème connu dans RE, mais pas de R à ce problème. Par exemple, si vous pouvez montrer que toute instance du problème de l'arrêt peut être résolu en le transformant en une instance de votre problème, vous savez qu'il ne peut pas avoir une solution récursive, et si vous suivez ce avec un TM pour la langue que vous savez que la langue est en RÉ. Ensemble, vous avez une langue dans RE, mais pas R.

    C'est sûr, n'est pas la réponse que j'espérais 🙁 bien que cela clarifie un peu de doutes que j'avais, donc merci! Donc, si vous avez eu à résoudre l'exemple que j'ai écrit au début, comment procéderiez-vous (sachant qu'il n'est pas libre de tout contexte)?
    Êtes-vous sûr qu'il n'est pas libre de tout contexte?
    Assez sûr, ouais.. lemme de Pompage devrait l'exclure, aussi je ne peux pas trouver une grammaire qui serait à l'œuvre.
    Ok, cool. Il n'y a pas difficile et rapidement la règle sur la façon de vérifier si quelque chose dans R ou RE - R, mais rappelez-vous que la R est un outil très puissant de la classe de langues. La plupart des choses impliquant le comptage dans R, et une bonne règle de base est que si vous pouvez penser à un programme informatique simple pour le résoudre, alors il est dans R. Dans ce cas, pourriez-vous écrire un programme qui pourrait vérifier si la chaîne correcte condition était vrai?
    Oui, je suppose que ce serait assez facile.. si vous pensez que ce serait une bonne estimation de dire que c'est dans R, droite?

    OriginalL'auteur templatetypedef

  2. 5

    Pour la mise en contexte de langue gratuit une méthode rapide est juste de voir le nombre de comparisions.

    Dans l'exemple voir n<=m et m<=s. Il y a donc deux comparaisons impliqués. Ainsi, vous pouvez le sortir tout simplement dire qu'il n'est pas sans contexte. Si il y a une seule comparaison impliqués ensuite appeler comme un contexte de langue gratuit.

    Même est le cas avec les langages réguliers. Il devrait y avoir aucune relation entre les deux variables, je veux dire, il ne doit y avoir aucune sorte de comparaison. Par Exemple, considérons les langues- 0^m+n 1^n 0^m. Soigneusement voir qu'il y a juste une seule comparaison faite qui est m+n = n+m(pousser et de l'éclatement de l'symboles) de Sorte qu'il est sans contexte.

    Maintenant voir 0^n+m 1^n+m 0^m clairement voir la comparaison entre les 2 premiers et les deux suivants.

    J'ai pris un certain temps à le comprendre. Mais il faudra un peu de prendre les décisions. Croyez-moi, ça fonctionne vraiment. Voici le dernier exemple de langage régulier. a^n b^2m est régulière( Voir il n'y a pas de comparaison entre n et m) et {a^n b^m |n=2m} est sans contexte comme il n'a qu'une comparaison(non régulier)

    Espère que cette aide

    saurabh srivastav que diriez-vous de L={a^n b^m| n,m>=1}, est-ce de la LCF?
    Je dirais que L est un langage régulier depuis le début, vous n'avez pas vraiment à la relation entre le nombre de a et le nombre de b, vous vous contentez de vous dire que chaque chaîne de caractères dans la langue a commencer par des non-vide préfixe de a de taille n (il n'est cependant pas définie, ce que n doit être suivi par une séquence non-vide de b (où m est la limite supérieure de la durée n'est pas limitée), si vous pouvez réellement construire une expression régulière pour cette langue. Veuillez me corriger si je me suis trompé. Je viens de prendre un cours en informatique théorique à mon collège.

    OriginalL'auteur Saurabh Srivastava