Langue acceptée et langue choisie

Un TM accepte un langage s'il entre dans un état final pour toute chaîne d'entrée w. Un langage est récursivement énumérable (généré par la grammaire de type 0) s'il est accepté par une machine de Turing.

Un TM décide d'une langue s'il l'accepte et entre dans un état de rejet pour toute entrée non dans la langue. Un langage est récursif s'il est décidé par une machine de Turing.

Il peut y avoir des cas où une MT ne s'arrête pas. Un tel TM accepte la langue, mais il ne le décide pas.

Concevoir une machine de Turing

Les principes de base de la conception d'une machine de Turing ont été expliqués ci-dessous à l'aide de quelques exemples.

Exemple 1

Concevez une TM pour reconnaître toutes les chaînes composées d'un nombre impair de α.

Solution

La machine de Turing M peut être construit par les mouvements suivants -

  • Laisser q1 être l'état initial.

  • Si M est dans q1; au balayage α, il entre dans l'étatq2 et écrit B (Vide).

  • Si M est dans q2; au balayage α, il entre dans l'étatq1 et écrit B (Vide).

  • D'après les mouvements ci-dessus, nous pouvons voir que M entre dans l'état q1 s'il scanne un nombre pair de α, et qu'il entre dans l'état q2s'il scanne un nombre impair de α. Par conséquentq2 est le seul État acceptant.

Par conséquent,

M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}

où δ est donné par -

Symbole de l'alphabet de bande État actuel 'q 1 ' État actuel 'q 2 '
α BRq 2 BRq 1

Exemple 2

Concevez une machine de Turing qui lit une chaîne représentant un nombre binaire et efface tous les 0 en tête de la chaîne. Cependant, si la chaîne ne comprend que des 0, elle conserve un 0.

Solution

Supposons que la chaîne d'entrée se termine par un symbole vide, B, à chaque extrémité de la chaîne.

La machine de Turing, M, peut être construit par les mouvements suivants -

  • Laisser q0 être l'état initial.

  • Si M est dans q0, à la lecture de 0, il se déplace à droite, entre dans l'état q1 et efface 0. A la lecture de 1, il entre dans l'état q2 et se déplace à droite.

  • Si M est dans q1, à la lecture de 0, il se déplace vers la droite et efface 0, c'est-à-dire qu'il remplace les 0 par des B. En atteignant le 1 le plus à gauche, il entreq2et se déplace à droite. S'il atteint B, c'est-à-dire que la chaîne ne comprend que des 0, il se déplace vers la gauche et entre dans l'étatq3.

  • Si M est dans q2, en lisant 0 ou 1, il se déplace vers la droite. En atteignant B, il se déplace à gauche et entre dans l'étatq4. Cela confirme que la chaîne ne comprend que des 0 et des 1.

  • Si M est dans q3, il remplace B par 0, se déplace vers la gauche et atteint l'état final qf.

  • Si M est dans q4, en lisant 0 ou 1, il se déplace vers la gauche. En atteignant le début de la chaîne, c'est-à-dire quand il lit B, il atteint l'état finalqf.

Par conséquent,

M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}

où δ est donné par -

Symbole de l'alphabet de bande État actuel 'q 0 ' État actuel 'q 1 ' État actuel 'q 2 ' État actuel 'q 3 ' État actuel 'q 4 '
0 BRq 1 BRq 1 ORq 2 - OLq 4
1 1Rq 2 1Rq 2 1Rq 2 - 1Lq 4
B BRq 1 BLq 3 BLq 4 OLq f BRq f