Paul Brunet

Paul Brunet

Exemples de machines de Turing

Voici une série d’exemples de machines de Turing. Ces exemples ne sont pas directement éditables, mais peuvent être chargés dans l’éditeur.

Machines de Turing

Teste si le mot d’entrée appartient au langage ab*(aa)*

1 rubans
5 états

Teste si le mot d’entrée contient plus de a que de b.

1 rubans
8 états

Teste si le mot d’entrée contient plus de a que de b.

2 rubans
6 états

Teste si le mot d’entrée contient plus de a que de b.

3 rubans
5 états

Teste si le mot d’entrée contient autant de a que de b que de c.

1 rubans
13 états

Teste si le mot d’entrée contient autant de a que de b que de c.

4 rubans
9 états

Teste si le mot d’entrée contient le motif abba

1 rubans
4 états

Teste si le mot d’entrée contient le motif abba

1 rubans
5 états

Teste si le mot d’entrée contient deux fois plus de a que de b

2 rubans
6 états

Teste si le mot d’entrée contient deux fois plus de a que de b

2 rubans
6 états

Teste si la longueur du mot d’entrée est une puissance de 2

1 rubans
7 états

Teste si le mot d’entrée est de la forme wXw

2 rubans
4 états

Teste si le mot d’entrée est de la forme wXw

1 rubans
8 états

Insère un X au milieu des mots de longueur paire.

2 rubans
6 états

Teste si le mot d’entrée est de la forme ww

2 rubans
10 états

Image mirroir d’une liste d’entiers

2 rubans
5 états

Sommation de liste

2 rubans
6 états

Calcul de la longueur d’une liste

2 rubans
6 états

Machine utilisée en exemple en cours.

1 rubans
6 états

Exemple de machine non-déterministe

2 rubans
5 états
non-déterministe

Automates

Exemple d'automate déterministe
3 états
Teste si le mot d'entrée appartient au langage `ab*(aa)*`.
5 états