programmer une machine de turing en java

programmer une machine de turing en java - Algo - Programmation

Marsh Posté le 02-04-2005 à 11:54:22    

J'ai réalisé une machine de turing permettant d'analyser la syntaxe d'une opération en binaire afin de savoir si elle est correcte ou pas.
Je l'ai testé avec succès sous jflap mais maintenant il me reste à la coder et là ça devient compliquer.
en effet je n'ai aucune méthode pour passer d'une machine de turing à algorithme classique facilement transposable à un langage.
 
voici la machine en question :  
 
http://www.geocities.com/sylvain_29/turing.jpg
 
je ne demande pas de mon pondre l'algo car il n'y aurait aucun intéret mais plutot de m'aider à trouver une méthode pour transformer la machine en un algo papier.
Merci d'avance !

Reply

Marsh Posté le 02-04-2005 à 11:54:22   

Reply

Marsh Posté le 02-04-2005 à 12:01:20    

C'est un simple graphe dirigé ?

Reply

Marsh Posté le 02-04-2005 à 12:10:45    

Pour les états tu peux faire comme pour un automate classique avec un enum des etats et et un tableau de transitions etc ...
Par contre pour la bande il faut bien entendu definir une longueur maximale au debut : un tableau (ou meme un fichier), une position de la tete, position du symbole suivant, position de symbole precedent.
 
Il y a pleins d'exemples sur google ...


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 02-04-2005 à 12:13:20    

WhatDe a écrit :

C'est un simple graphe dirigé ?


 
Non c'est pas un simple graphe dirigé, c'est comme un automate a pile sauf que la pile n'est plus une pile mais un ruban "infini" sur lequel on peux avancer, reculer, lire, ecrire.


Message édité par Chronoklazm le 02-04-2005 à 12:13:40

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 02-04-2005 à 12:16:32    

en fait ce qu'il faut que je fasse c'est parcourir ma bande (mon string en java dans mon cas) et faire un case sur tous les cas possibles c'est à dire un truc du style :
case bidule with
  (etatCourant, symbole lu, etatSuivant)-> traitement
  (etatCourant2, symbole lu, etatSuivant3)-> traitement2
  ...
  default : aucun tuple correspondant dans le tableau donc expression entree non correcte
end case
 
c'est bien ce genre de méthode qu'il faut que j'applique ou je me suis trompé ?

Reply

Marsh Posté le 02-04-2005 à 12:28:17    

lordankou a écrit :

en fait ce qu'il faut que je fasse c'est parcourir ma bande (mon string en java dans mon cas) et faire un case sur tous les cas possibles c'est à dire un truc du style :
case bidule with
  (etatCourant, symbole lu, etatSuivant)-> traitement
  (etatCourant2, symbole lu, etatSuivant3)-> traitement2
  ...
  default : aucun tuple correspondant dans le tableau donc expression entree non correcte
end case
 
c'est bien ce genre de méthode qu'il faut que j'applique ou je me suis trompé ?


 
Oui je pense que ca devrait le faire, mais ta chaine en entrée est une string et ta bande est une string aussi ? Pour les états moi je ferais un tableau avec 4 colonnes ...
 

Code :
  1. // tm sera du style   STATE     READ      ACTION    NEW STATE //
  2. read = "symbole lu";
  3. for( int i = 0; i < tm.length; i++ ) {
  4.    if( currentState.equals( tm[i][0] ) && read == tm[i][1].charAt( 0 ) ) {
  5.     found = true;
  6.     action = tm[i][2]; // L'action a effectuer
  7.     newState = tm[i][3]; // Le nouvel etat
  8.                                         ...
  11. // Apresen fonction de action tu fera le necessaire


Message édité par Chronoklazm le 02-04-2005 à 12:35:42

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 02-04-2005 à 12:35:25    

ok merci beaucoup ! je vais coder ça pendant le week-end et je mettrais ma solution après si ça peut aider quelqu'un !
mici pour tout !

Reply

Marsh Posté le 05-04-2005 à 10:21:53    

voilà : c'est pas forcément joli mais ça marche niquel !  :love:  
 

Code :
  1. // analyse syntaxique : va analyser l'expression et retourner un booleen si l'expression est correcte
  2.     // si erreur on retourne false sinon true
  3.     private boolean analyseurSyntaxique(String exp){
  4.         // declaration des variables
  5.         // tableau d'etat
  6.         String tableauEtat[][]=new String [23][3]; // tableau de 25 lignes et 3 colonnes -> etat courant, digit lut, etat suivant
  7.         String etatCourant[][]=new String [1][2]; // tableau pour contenir l'etat courant
  8.         // variable pour le parcours de la chaine
  9.         int longueur=0 ;
  10.         int i=0 ; // variable pour le parcours du tableau d'etat
  11.         // stockage temporaire pour une meilleure lisibilité
  12.         String etatString = new String();
  13.         String etatTableau= new String();
  14.         String caractereLu = new String();
  15.         String caractereAttendu = new String();
  16.         // variable indiquant si erreur dans la chaine
  17.         boolean analyseurOK=true;
  18.        
  19.         // initialisation du tableau d'etat
  20.         tableauEtat[0][0]="q0"; tableauEtat[0][1]="1"; tableauEtat[0][2]="q1";
  21.         tableauEtat[1][0]="q0"; tableauEtat[1][1]="0"; tableauEtat[1][2]="q1";
  22.         tableauEtat[2][0]="q1"; tableauEtat[2][1]="1"; tableauEtat[2][2]="q1";
  23.         tableauEtat[3][0]="q1"; tableauEtat[3][1]="0"; tableauEtat[3][2]="q1";
  24.         tableauEtat[4][0]="q1"; tableauEtat[4][1]="."; tableauEtat[4][2]="q2";
  25.         tableauEtat[5][0]="q1"; tableauEtat[5][1]="+"; tableauEtat[5][2]="q4";
  26.         tableauEtat[6][0]="q1"; tableauEtat[6][1]="-"; tableauEtat[6][2]="q4";
  27.         tableauEtat[7][0]="q1"; tableauEtat[7][1]="*"; tableauEtat[7][2]="q4";
  28.         tableauEtat[8][0]="q1"; tableauEtat[8][1]=""; tableauEtat[8][2]="q5";
  29.         tableauEtat[9][0]="q1"; tableauEtat[9][1]="/"; tableauEtat[9][2]="q6";
  30.         tableauEtat[10][0]="q2"; tableauEtat[10][1]="1"; tableauEtat[10][2]="q3";
  31.         tableauEtat[11][0]="q2"; tableauEtat[11][1]="0"; tableauEtat[11][2]="q3";
  32.         tableauEtat[12][0]="q4"; tableauEtat[12][1]="1"; tableauEtat[12][2]="q1";
  33.         tableauEtat[13][0]="q4"; tableauEtat[13][1]="0"; tableauEtat[13][2]="q1";
  34.         tableauEtat[14][0]="q6"; tableauEtat[14][1]="1"; tableauEtat[14][2]="q1";
  35.         tableauEtat[15][0]="q6"; tableauEtat[15][1]="0"; tableauEtat[15][2]="q6";
  36.         tableauEtat[16][0]="q6"; tableauEtat[16][1]="."; tableauEtat[16][2]="q7";
  37.         tableauEtat[17][0]="q3"; tableauEtat[17][1]="0"; tableauEtat[17][2]="q3";
  38.         tableauEtat[18][0]="q3"; tableauEtat[18][1]="1"; tableauEtat[18][2]="q3";
  39.         tableauEtat[19][0]="q3"; tableauEtat[19][1]="/"; tableauEtat[19][2]="q6";
  40.         tableauEtat[20][0]="q3"; tableauEtat[20][1]=""; tableauEtat[20][2]="q5";
  41.         tableauEtat[21][0]="q7"; tableauEtat[21][1]="0"; tableauEtat[21][2]="q7";
  42.         tableauEtat[22][0]="q7"; tableauEtat[22][1]="1"; tableauEtat[22][2]="q3";
  43.         // initialisation de l'etat courant
  44.         etatCourant[0][0]="q0";
  45.         etatCourant[0][1]="";
  46.            
  47.         // analyse de la chaine
  48.         // on parcours jusqu'à la fin de la chaine et sans erreur
  49.         while(longueur<exp.length() && analyseurOK){
  50.             // on met analyseurOK a vrai tant qu'on a pas trouve la transition
  51.             analyseurOK = false;
  52.             // definition du prochaine etat
  53.             etatCourant[0][1]=exp.substring(longueur,longueur+1);
  54.             // parcours de tous les sous etats
  55.             i=0;
  56.             while(i<23){
  57.                 // si les etats sont equivalents
  58.                 etatString = etatCourant[0][0] ;
  59.                 etatTableau = tableauEtat[i][0];
  60.                 caractereLu = etatCourant[0][1];
  61.                 caractereAttendu = tableauEtat[i][1];
  62.                 //expression.setText(expression.getText()+etatString+etatTableau+" "+caractereLu+caractereAttendu+" | " );
  63.                 // verification des etats
  64.                 if ( (etatString == etatTableau) && (caractereLu.equals(caractereAttendu)) ) {
  65.                     // modifie l'etat courant
  66.                     etatCourant[0][0]=tableauEtat[i][2];
  67.                     // l'analyse redevient bonne
  68.                     analyseurOK = true;
  69.                     // on sort de la boucle
  70.                     i=23;
  71.                 }
  72.                 // incrementation de i
  73.                 i++;
  74.             }
  75.             // incrementation de longueur
  76.             longueur++;
  77.         }
  78.        
  79.         //expression.setText(etatString);
  80.        
  81.         // on teste si on est arrivé à l'etat final
  82.         if ( (((etatCourant[0][0]).equals("q1" )) || ((etatCourant[0][0]).equals("q3" ))) && (longueur==exp.length()) ) { // q5 etat terminal de l'automate correspond accessible a partir de q1 et q3
  83.             // analyseurOK devient correcte
  84.             analyseurOK = true;
  85.         }
  86.         // sinon on est pas arrive à la fin
  87.         else {
  88.             // analyseurOK devient non correcte
  89.             analyseurOK = false;
  90.         }
  91.        
  92.         // si erreur on affiche l'endroit de l'erreur
  93.         if (!analyseurOK){
  94.             //JOptionPane.showMessageDialog(null,"essaie","essaie2",JOptionPane.WARNING_MESSAGE);
  95.         }
  96.        
  97.         // on retourne le resultat de l'analyse
  98.         return (analyseurOK);
  99.     }

Reply

Marsh Posté le 05-04-2005 à 10:33:33    

maintenant, va regarder le pattern "State" dans google et essaye de l'appliquer à ton cas.
http://www.google.fr/search?source [...] te+pattern
 
http://home.earthlink.net/~huston2/dp/state.html
 
Dans ce cas précis, ce sera probablement plus lisible mais avec plus de code, mais ça te servira de cas d'école pour quand tu en auras besoin dans la vraie vie.


---------------
trainoo.com, c'est fini
Reply

Marsh Posté le 05-04-2005 à 16:45:02    

euh joker je suis qu'en deuxième année de deug... :) (mais ça a l'air intéressant)
le design patern c l'année prochaine et en plus je dois rendre cette bip de calculatrice pour lundi...
et pour la lisibilité c'est clair que c'est nul mais le fait de manier que des strings et pas des floattant ça n'aide pas beaucoup !

Reply

Marsh Posté le 05-04-2005 à 16:45:02   

Reply

Marsh Posté le 05-04-2005 à 17:10:01    

C'est quoi l'interet d'implementer une Machine de Turing avec des state patterns ?
 
EDIT : Bon d'accord ca peut servir mais un marteau pour tuer une mouche  :sweat:


Message édité par Chronoklazm le 05-04-2005 à 17:20:00

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed