Plus de a que de b (2 rubans)

2 rubans

6 états

Cette machine prend en entrée un mot sur l’alphabet {a,b}. Elle teste si ce mot contient strictement plus d’occurences du symbole a que du symbole b.

Dans cette machine, le deuxième ruban sert de compteur. On code ce compteur avec un symbole 0 sur la position initiale : la distance entre ce symbole et la position de la tête de lecture correspond à la valeur du compteur. La machine que l’on construit a en outre un état q+ et un état q-, pour donner le signe de l’entier stocké. Autrement dit:

• dans l’état q+:
  • incrémenter le compteur revient à déplacer la tête de lecture vers la droite
  • décrémenter le compteur revient à déplacer la tête de lecture vers la gauche si on est (strictement) à droite de la position 0
  • si la tête pointe sur la position 0, alors pour décrémenter le compteur il faut aller dans l’état q- et déplace la tête vers la droite;
• dans l’état q-:
  • décrémenter le compteur revient à déplacer la tête de lecture vers la droite
  • incrémenter le compteur revient à déplacer la tête de lecture vers la gauche si on est (strictement) à droite de la position 0
  • si la tête pointe sur la position 0, alors pour incrémenter le compteur il faut aller dans l’état q+ et déplace la tête vers la droite.

Simulateur

Spécification de la machine

name: #a > #b init: q0 accept: a>b // On commence par initialiser le deuxième ruban, // en introduisant le symbole 0. q0,[ab],_ q+,$1,0,-,- // On va ensuite dans l'état q+. // (on pourrait aussi aller dans l'état q-, puisque 0=-0). // ensuite, dans les états q+ et q-, on lit le mot sur // le premier ruban de gauche à droite, en incrémente // le compteur avec des a et en le décrémentant avec des b. q+,a,[0_] q+,a,$2,>,> q+,b,_ q+,b,_,>,< q+,b,0 q-,b,0,>,> q-,a,_ q-,a,_,>,< q-,a,0 q+,a,0,>,> q-,b,[_0] q-,b,$2,>,> //lorsequ'on a finit de lire l'entrée : // * si le compteur est à la position 0, // il y a autant de a que de b q+,_,0 a=b,_,+,<,- q-,_,0 a=b,_,_,<,- // * si le compteur a une valeur strictement positive // on accepte q+,_,_ a>b,_,_,<,- // * s'il a une valeur strictement négative // il y avait plus de b que de a. q-,_,_ a<b,_,_,<,-

Messages de sortie du compilateur

https://machines.brunet-zamansky.fr