http://www.nmt.edu/~prcm/turing/vtm.cgi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % w contient un nombre pair de zeros pair,0,impair,0,D pair,1,pair,1,D pair,_,ACCEPTE,_,D impair,0,pair,0,D impair,1,impair,1,D impair,_,REJETTE,_,D FIN % ACCEPTE : 11001010100 % REJETTE : 1100101010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % a^n b^n, n>0, Sigma={a,b} initial,_,ACCEPTE,_,D % mot vide initial,a,ch_b,A,D % premier a initial,b,REJETTE,b,D % REJETTE si le mot commence par un b ch_b,a,ch_b,a,D % cherche un b non marque ch_b,B,ch_b,B,D ch_b,b,ch_A,B,G % marque un b, retour a A ch_b,_,REJETTE,_,D % REJETTE si on ne trouve pas de b ch_A,B,ch_A,B,G % retour a A ch_A,a,ch_A,a,G ch_A,A,ch_a,A,D ch_a,a,ch_b,A,D % marque un a, cherche un b ch_a,B,test,B,D % plus de a, -> test test,A,test,A,D % teste si il reste des symboles test,B,test,B,D test,_,ACCEPTE,_,D % c est vide, accepte test,a,REJETTE,a,D % c est non vide test,b,REJETTE,b,D % c est non vide FIN % ACCEPTE : aaabbb % REJETTE : abab %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % a^n b^n c^n, n>0, Sigma={a,b,c} initial,a,ch_b,A,D % premier a initial,b,REJETTE,b,D % commence par un b initial,c,REJETTE,c,D % commence par un c ch_b,a,ch_b,a,D % cherche b ch_b,B,ch_b,B,D ch_b,b,ch_c,B,D ch_b,c,REJETTE,c,D % Trouve un c ch_b,C,REJETTE,C,D % Trouve un C ch_b,_,REJETTE,_,D % Trouve rien ch_c,b,ch_c,b,D % cherche c ch_c,C,ch_c,C,D ch_c,c,ch_A,C,G ch_c,a,REJETTE,a,D % Trouve un a ch_c,_,REJETTE,_,D % Trouve rien ch_A,C,ch_A,C,G % retour a A ch_A,b,ch_A,b,G ch_A,B,ch_A,B,G ch_A,a,ch_A,a,G ch_A,A,ch_a,A,D ch_a,a,ch_b,A,D % cherche a ch_a,B,test,B,D % plus de a test,B,test,B,D % teste si il reste des symboles test,C,test,C,D test,_,ACCEPTE,_,D test,a,REJETTE,a,D test,b,REJETTE,b,D test,c,REJETTE,c,D FIN % ACCEPTE : aaaabbbbcccc % REJETTE : aaabbbbccc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %addition unaire % w=1^k+1^l=1^k+l, k,G>0, sous ensemble de 1^+ + 1^+ = 1^+ initial,1,ch_+,_,D % efface le premier 1 ch_+,1,ch_+,a,D % cherche + et remplace les 1 par des a ch_+,+,ch_=,a,D ch_=,1,ch_=,a,D % cherche = et remplace les 1 par des a ch_=,=,1=b,b,D 1=b,1,1=b,b,D % remplace le reste par des b 1=b,_,efface,_,G efface,b,retour,_,G retour,b,retour,b,G % retour au debut du mot retour,a,retour,a,G retour,_,initial2,_,D initial2,a,ch_b,A,D % on réutilise le programme pour a^n+b^n initial2,b,REJETTE,b,D ch_b,a,ch_b,a,D ch_b,B,ch_b,B,D ch_b,b,ch_A,B,G ch_b,_,REJETTE,_,D ch_A,B,ch_A,B,G ch_A,a,ch_A,a,G ch_A,A,ch_a,A,D ch_a,a,ch_b,A,D ch_a,B,test,B,D test,A,test,A,D test,B,test,B,D test,_,ACCEPTE,_,D test,a,REJETTE,a,D test,b,REJETTE,b,D FIN % accepte: 111+1111=1111111 % rejette: 111+1111=111111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 1^(2^n), n dans N, Sigma={1} initial,_,REJETTE,_,D initial,1,impair,0,D pair,0,pair,0,D % cherche 1, pair pair,1,impair,0,D pair,_,retour,_,G impair,0,impair,0,D % cherche 1, impair impair,1,pair,1,D impair,_,dernier,_,G retour,0,retour,0,G % retour au debut (pair) retour,1,retour,1,G retour,_,pair,_,D dernier,0,dernier,0,G % retour au debut pour verifier qu'il ne reste qu'un 1 dernier,1,REJETTE,1,G dernier,_,ACCEPTE,_,D FIN % ACCEPTE: 11111111 % REJETTE: 111111111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %addition binaire % w="_x+y=z_", x,y,z >=0, x=y+z initial,0,ch_x_c=0,0,D %initial initial,1,ch_x_c=0,1,D % carry=0, cherche bit moins significatif de x ch_x_c=0,0,ch_x_c=0,0,D ch_x_c=0,1,ch_x_c=0,1,D ch_x_c=0,+,tr_x_c=0,+,G ch_x_c=0,X,tr_x_c=0,X,G tr_x_c=0,0,ch_y_c=0_x=0,X,D tr_x_c=0,1,ch_y_c=0_x=1,X,D tr_x_c=0,_,ch_y_c=0_x=0,_,D % carry=1, cherche bit moins significatif de x ch_x_c=1,0,ch_x_c=1,0,D ch_x_c=1,1,ch_x_c=1,1,D ch_x_c=1,+,tr_x_c=1,+,G ch_x_c=1,X,tr_x_c=1,X,G tr_x_c=1,0,ch_y_c=1_x=0,X,D tr_x_c=1,1,ch_y_c=1_x=1,X,D tr_x_c=1,_,ch_y_c=1_x=0,_,D % carry=0,x=0, cherche bit moins significatif de y ch_y_c=0_x=0,X,ch_y_c=0_x=0,X,D ch_y_c=0_x=0,+,ch_y_c=0_x=0,+,D ch_y_c=0_x=0,0,ch_y_c=0_x=0,0,D ch_y_c=0_x=0,1,ch_y_c=0_x=0,1,D ch_y_c=0_x=0,Y,tr_y_c=0_x=0,Y,G ch_y_c=0_x=0,=,tr_y_c=0_x=0,=,G tr_y_c=0_x=0,0,ch_z_c=0_z=0,Y,D tr_y_c=0_x=0,1,ch_z_c=0_z=1,Y,D tr_y_c=0_x=0,+,ch_z_c=0_z=0,+,D % carry=0,x=1, cherche bit moins significatif de y ch_y_c=0_x=1,X,ch_y_c=0_x=1,X,D ch_y_c=0_x=1,+,ch_y_c=0_x=1,+,D ch_y_c=0_x=1,0,ch_y_c=0_x=1,0,D ch_y_c=0_x=1,1,ch_y_c=0_x=1,1,D ch_y_c=0_x=1,Y,tr_y_c=0_x=1,Y,G ch_y_c=0_x=1,=,tr_y_c=0_x=1,=,G tr_y_c=0_x=1,0,ch_z_c=0_z=1,Y,D tr_y_c=0_x=1,1,ch_z_c=1_z=0,Y,D tr_y_c=0_x=1,+,ch_z_c=0_z=1,+,D % carry=1,x=0, cherche bit moins significatif de y ch_y_c=1_x=0,X,ch_y_c=1_x=0,X,D ch_y_c=1_x=0,+,ch_y_c=1_x=0,+,D ch_y_c=1_x=0,0,ch_y_c=1_x=0,0,D ch_y_c=1_x=0,1,ch_y_c=1_x=0,1,D ch_y_c=1_x=0,Y,tr_y_c=1_x=0,Y,G ch_y_c=1_x=0,=,tr_y_c=1_x=0,=,G tr_y_c=1_x=0,0,ch_z_c=0_z=1,Y,D tr_y_c=1_x=0,1,ch_z_c=1_z=0,Y,D tr_y_c=1_x=0,+,ch_z_c=0_z=1,+,D % carry=1,x=1, cherche bit moins significatif de y ch_y_c=1_x=1,X,ch_y_c=1_x=1,X,D ch_y_c=1_x=1,+,ch_y_c=1_x=1,+,D ch_y_c=1_x=1,0,ch_y_c=1_x=1,0,D ch_y_c=1_x=1,1,ch_y_c=1_x=1,1,D ch_y_c=1_x=1,Y,tr_y_c=1_x=1,Y,G ch_y_c=1_x=1,=,tr_y_c=1_x=1,=,G tr_y_c=1_x=1,0,ch_z_c=1_z=0,Y,D tr_y_c=1_x=1,1,ch_z_c=1_z=1,Y,D tr_y_c=1_x=1,+,ch_z_c=1_z=0,+,D % carry=0,z=0, cherche bit moins significatif de z ch_z_c=0_z=0,Y,ch_z_c=0_z=0,Y,D ch_z_c=0_z=0,=,ch_z_c=0_z=0,=,D ch_z_c=0_z=0,0,ch_z_c=0_z=0,0,D ch_z_c=0_z=0,1,ch_z_c=0_z=0,1,D ch_z_c=0_z=0,Z,tr_z_c=0_z=0,Z,G ch_z_c=0_z=0,_,tr_z_c=0_z=0,_,G tr_z_c=0_z=0,0,go_back_c=0,Z,G tr_z_c=0_z=0,=,check,=,G % carry=0,z=1, cherche bit moins significatif de z ch_z_c=0_z=1,Y,ch_z_c=0_z=1,Y,D ch_z_c=0_z=1,=,ch_z_c=0_z=1,=,D ch_z_c=0_z=1,0,ch_z_c=0_z=1,0,D ch_z_c=0_z=1,1,ch_z_c=0_z=1,1,D ch_z_c=0_z=1,Z,tr_z_c=0_z=1,Z,G ch_z_c=0_z=1,_,tr_z_c=0_z=1,_,G tr_z_c=0_z=1,1,go_back_c=0,Z,G % carry=1,z=0, cherche bit moins significatif de z ch_z_c=1_z=0,Y,ch_z_c=1_z=0,Y,D ch_z_c=1_z=0,=,ch_z_c=1_z=0,=,D ch_z_c=1_z=0,0,ch_z_c=1_z=0,0,D ch_z_c=1_z=0,1,ch_z_c=1_z=0,1,D ch_z_c=1_z=0,Z,tr_z_c=1_z=0,Z,G ch_z_c=1_z=0,_,tr_z_c=1_z=0,_,G tr_z_c=1_z=0,0,go_back_c=1,Z,G % carry=1,z=1, cherche bit moins significatif de z ch_z_c=1_z=1,Y,ch_z_c=1_z=1,Y,D ch_z_c=1_z=1,=,ch_z_c=1_z=1,=,D ch_z_c=1_z=1,0,ch_z_c=1_z=1,0,D ch_z_c=1_z=1,1,ch_z_c=1_z=1,1,D ch_z_c=1_z=1,Z,tr_z_c=1_z=1,Z,G ch_z_c=1_z=1,_,tr_z_c=1_z=1,_,G tr_z_c=1_z=1,1,go_back_c=1,Z,G % c=0, retour go_back_c=0,0,go_back_c=0,0,G go_back_c=0,1,go_back_c=0,1,G go_back_c=0,+,go_back_c=0,+,G go_back_c=0,=,go_back_c=0,=,G go_back_c=0,X,go_back_c=0,X,G go_back_c=0,Y,go_back_c=0,Y,G go_back_c=0,_,ch_x_c=0,_,D % c=1, retour go_back_c=1,0,go_back_c=1,0,G go_back_c=1,1,go_back_c=1,1,G go_back_c=1,+,go_back_c=1,+,G go_back_c=1,=,go_back_c=1,=,G go_back_c=1,X,go_back_c=1,X,G go_back_c=1,Y,go_back_c=1,Y,G go_back_c=1,_,ch_x_c=1,_,D % verifie X+Y=Z sans 0 ou 1 check,Y,check,Y,G check,+,check,+,G check,X,check,X,G check,_,ACCEPTE,_,D FIN % ACCEPTE: 101+110=1011 % REJETTE: 101+110=1010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % _1^p_ avec p premier, Sigma={1} initial,1,initial2,M,D initial2,1,initial3,0,D initial2,_,PREMIER,_,D initial3,1,copy,X,G initial3,_,PREMIER,_,G %sur le x passe de M000X1111111 a % 1111M000X111 copy,1,copy,1,G copy,0,copy2,1,D copy,M,next,X,D copy2,1,copy2,1,D copy2,X,copy3,X,D copy3,0,copy3,0,D copy3,1,copy4,0,G copy3,_,reset,_,G copy4,0,copy4,0,G copy4,X,copy,X,G next,1,next,1,D next,X,next2,M,D next2,0,next2,0,D next2,_,REJETTE,_,G next2,1,copy,X,G % reset et incremente reset,X,reset,X,G % retour au premier blanc reset,0,reset,1,G reset,1,reset,1,G reset,M,reset,M,G reset,_,reset2,_,D % incrementation reset2,M,reset3,M,D reset2,X,reset3,M,D reset3,1,reset3,0,D reset3,X,reset4,0,D reset3,M,reset4,0,D reset4,1,reset5,X,D reset4,_,ACCEPTE,_,D reset5,1,reset5,1,D % clear up reset5,X,reset5,1,D reset5,M,reset5,1,D reset5,_,reset6,_,G % retour reset6,1,reset6,1,G reset6,X,copy,X,G FIN % ACCEPTE: 11111 % REJETTE: 111111111111111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % x est premier initial,0,initial,0,D initial,1,initial,1,D initial,_,dec,_,G dec,0,dec,1,G dec,_,clear,_,D dec,1,dr,0,D clear,1,clear,_,D clear,_,test,_,D dr,0,dr,0,D dr,1,dr,1,D dr,_,inc,_,D inc,1,inc,1,D inc,_,ga,1,G ga,1,ga,1,G ga,_,dec,_,G % _1^p_ avec p premier. test,1,test2,M,D test2,1,test3,0,D test2,_,ACCEPT,_,D test3,1,copy,X,G test3,_,ACCEPTE,_,G %sur le x passe de M000X1111111 a % 1111M000X111 copy,1,copy,1,G copy,0,copy2,1,D copy,M,next,X,D copy2,1,copy2,1,D copy2,X,copy3,X,D copy3,0,copy3,0,D copy3,1,copy4,0,G copy3,_,reset,_,G copy4,0,copy4,0,G copy4,X,copy,X,G next,1,next,1,D next,X,next2,M,D next2,0,next2,0,D next2,_,REJETTE,_,G next2,1,copy,X,G % reset et incremente reset,X,reset,X,G % retour au premier blanc reset,0,reset,1,G reset,1,reset,1,G reset,M,reset,M,G reset,_,reset2,_,D % incrementation reset2,M,reset3,M,D reset2,X,reset3,M,D reset3,1,reset3,0,D reset3,X,reset4,0,D reset3,M,reset4,0,D reset4,1,reset5,X,D reset4,_,ACCEPTE,_,D reset5,1,reset5,1,D % nettoyage reset5,X,reset5,1,D reset5,M,reset5,1,D reset5,_,reset6,_,G % retour reset6,1,reset6,1,G reset6,X,copy,X,G FIN % ACCEPTE: 1101 % REJETTE: 110111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Devoir 2 % La machine accepte t'elle le mot vide? 1,_,2,1,G 1,1,3,1,D 2,_,3,1,G 2,1,2,1,G 3,_,4,1,G 3,1,5,_,D 4,_,1,1,D 4,1,4,1,D 5,_,ACCEPTE,1,G 5,1,1,_,D FIN