Éléments d’ informatique théorique Série 11

Exercice 11.1 Montrez que tout langage sensible au contexte est récursif.

Exercice 11.2 Montrez que le problème de déterminer si une machine de Turing s’arrête pour tout mot d’entrée est indécidable.

Exercice 11.3 Les deux problèmes suivants sont-ils décidables ou indécidables:

1. Étant donnés une machine de Turing M, un état q et une chaîne w, déterminer si M atteindra l’état q sachant qu’elle commence dans l’ état initial et que w lui est fourni en entrée.

2. Déterminer si une machine de Turing donnée M s’arrête après un nombre de mouvements constant k sachant qu’elle commence dans l’ état initial et qu’une chaîne w lui est fournie en entrée.

Exercice 11.4 On se donne les propriétés ci-dessous, et les propriétés des langages récursivement énumérables associées. Utilisez le théorème de Rice pour les langages récursifs afin de déterminer dans chaque cas si la propriété engendre un problème L_{P} = {< M > | L(M) ∈ P } décidable:

1. L ≠ Σ^{∗}

2. L ∩ X ≠ ∅ avec X un ensemble récursivement énumérable donné

3. L contient au moins deux chaînes

4. L est infini

5. L est un langage hors-contexte

6. L = L^{R}