Décidabilité de la langue
Une langue s'appelle Decidable ou Recursive s'il y a une machine de Turing qui accepte et s'arrête sur chaque chaîne d'entrée w. Chaque langue décidable est Turing-Acceptable.
Un problème de décision P est décidable si la langue L de toutes les instances oui à P est décidable.
Pour un langage décidable, pour chaque chaîne d'entrée, la TM s'arrête soit à l'état d'acceptation, soit à l'état de rejet, comme illustré dans le diagramme suivant -
Exemple 1
Découvrez si le problème suivant est décidable ou non -
Un nombre «m» est-il premier?
Solution
Nombres premiers = {2, 3, 5, 7, 11, 13, ………… ..}
Divisez le nombre ‘m’ par tous les nombres entre «2» et «√m» à partir de «2».
Si l'un de ces nombres produit un reste zéro, alors il passe à «l'état Rejeté», sinon il passe à «l'état Accepté». Donc, ici, la réponse pourrait être faite par «Oui» ou «Non».
Hence, it is a decidable problem.
Exemple 2
Étant donné une langue régulière L et ficelle w, comment pouvons-nous vérifier si w ∈ L?
Solution
Prenez le DFA qui accepte L et vérifiez si w est accepté
Certains problèmes plus décidables sont -
- DFA accepte-t-il la langue vide?
- Est-ce que L 1 ∩ L 2 = ∅ pour les ensembles réguliers?
Note -
Si une langue L est décidable, alors son complément L' est également décidable
Si une langue est décidable, alors il y a un énumérateur pour elle.