TD2 : Ensembles récursifs/récursivement énumérables
Énoncé (pas les mêmes numéros d’exercices)
TD 2
EX 1
On écrit le mot à l’envers sur le deuxième ruban, puis on compare lettre à lettre verticalement.
- Étape 1 : Aller jusqu’au bout du mot sur le premier ruban, à l’indice $k$.
- Étape 2 : écrire un caractère spécial en position $k$ sur le deuxième
- Étape 3 : revenir au début sur le premier ruban, copier le mot sur le deuxième à l’envers
-
Étape 4 : comparer les deux.
- $q_1$ : écrit le mot sur le deuxième ruban
- $q_2$ : revient au début sur le premier ruban
- $q_3$ : compare les deux mots lettre à lettre
$∀ a \neq b ∈ 𝛴$ :
$(a,b)$ | $(a,a)$ | $(B,_)$ | $($,_)$ | |
---|---|---|---|---|
$q_1$ | $q_1(a,a)→→$ | $q_1(a,a)→→$ | $q_2(B,B)←←$ | |
$q_2$ | $q_2(a,b)←↓$ | $q_1(a,a)←↓$ | $q_2($,_)→→$ | |
$q_1$ | reject | $q_1(a,a)→←$ | accept |
EX 2
- Intersection : les deux MT sont sur un ruban chacune ⟶ le dernier état est le $∧$ des deux états finaux des deux MT.
- Union : idem, avec $∨$.
- Complémentaire : idem, avec $\lnot$ (“accept” devient “reject” et réciproquement).
EX 3
On veut savoir si $w ∈ f(L)$ : Sur le ruban, on note $w$, un caractère spécial, et tous les éléments de $L$ juxtaposés par des caractères spéciaux. Puis : on calcule $f(w’)$, pour tous les $w’$ écrits sur le ruban (sauf le premier, qui est $w$), et on la compare à $w$ (si $w ∈L$ : ça termine, sinon : ça ne termine pas).
Soit $M_f$ calculant $f$.
Mq L ≝ \{f(w) \vert w ∈ 𝛴^* \} est récursivement énumérable.
EX 4
On exécute $M_1, M_2$ sur $w$ sur deux bandes différentes.
Ne marche pas pour le complémentaire, car on ne peut pas détecter les mots tels que la machine ne termine pas pour les accepter dans $\lnot M$.
EX 5
On aimerait bien faire quelque chose de similaire à l’exo 3, tester tous les mots successifs du langage sur la première bande, puis le placer sur la deuxième bande ⟶ MAIS : ne marche pas, car on peut rester indéfiniment sur un mot n’appartenant pas au langage.
Le langage $L$ est récursivement én. ssi ∃ M \text{ à deux rubans }; q_e ∈ Q_M ∧ \\ q_0,(𝜀, \$),(𝜀,\$)\vdash_M^* q_e, (𝜀,\$w'), (𝜀, \$w) ⟺ w ∈ L
- $⟹$ : On définit $M$ de la manière suivante :
À la $k$-ième grande étape, on a :
- Sur le premier ruban : les $k$ premiers mots de l’alphabet auxquels on appliqué $k$ étapes de la machine $M_L$ (on les stocke sous la forme $q_1\vert t_1\vert w_1#q_2\vert t_2\vert w_2⋯ #q_k\vert t_k\vert w_k)$
- Sur le deuxième ruban : on écrit tour à tour les $k$ mots du premier ruban en faisant progresser l’exécution de $M_L$ de 1 étape. Si $M_L$ accepte le mot, on l’écrit tout seul (sans $q_i\vert t_i\vert $) juste après (et on passe dans l’état $q_e$).
On passe d’un mot au suivant/ au précédent par la fonction $next()$/$prec()$.
- $⟸$ : À trois rubans : à chaque fois que $M$ est dans l’état $q_e$, on lit le mot sur le 3e ruban, et on le compare à $w$ sur le premier ruban.
EX 6
M1.
On procède de même qu’en EX3, en remplaçant $𝛴^*$ par $L$ ($L$ peut être énuméré, puisqu’il est récursivement énumérable (cf. EX5)).
M2. ∃ M_L \text{ à deux rubans }; q_e ∈ Q_{M_L} ∧ \\ q_0,(𝜀, \$),(𝜀,\$)\vdash_M^* q_e, (𝜀,\$w'), (𝜀, \$w) ⟺ w ∈ L
EX 7
Voici un langage récursivement énumérable mais non récursif : L = \{(⟨M⟩, w) \vert M(w) \text{ termine}\}
- $L$ est récursivement én., avec la MT Universelle : on peut simuler l’action de $M$ sur $w$ (qu’elle termine ou non).
- $L$ n’est pas récursif, car sinon on a une machine $L’$ qui résout le problème de l’arrêt.
M1. Si $L$ est réc.én., il existe une machine qui énumère ce langage, et en retourne le $n$-ième mot. La fonction qui à $n$ associe le $n$-ième mot est calculable, et l’image de cette fonction est $L$.
M2.
$f(⟨M⟩,w,n)$ simule $M$ sur $w$ pendant $n$ étapes, et si $M$ accepte, retourne $(⟨M⟩,w)$, sinon $𝜀$
$Im(f) = L$
Leave a comment