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.