Une machine de Turing pour le langage
X = { a2n | n ≥ 0}
Un machine M qui accepte le langage X est la suivante
- l'ensemble des états est Q = {0, 1, 2, 3, 4, 5},
- l'alphabet d'entrée est Σ = {a},
- l'alphabet de bande est Γ = {a, A, #},
- l'état initial est q0 = 0,
- le seul état final est l'état 5,
- l'ensemble des transitions est décrit par la figure ou le tableau
ci-dessous. Cette machine est déterministe.
Fig 1 - Diagramme des transitions
| δ |
a |
A |
# |
| 0 |
1,#,R |
0,A,R |
|
| 1 |
2,a,R |
1,A,R |
5,#,R |
| 2 |
3,A,R |
2,A,R |
4,#,L |
| 3 |
2,a,R |
3,A,,R |
|
| 4 |
4,a,L |
4,A,L |
0,#,R |
| 5 |
|
|
|
Fonction de transition.