Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2021 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  programmer une machine de turing en java

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

programmer une machine de turing en java

n°1033040
lordankou
Posté le 02-04-2005 à 11:54:22  profilanswer
 

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 !

mood
Publicité
Posté le 02-04-2005 à 11:54:22  profilanswer
 

n°1033043
WhatDe
Posté le 02-04-2005 à 12:01:20  profilanswer
 

C'est un simple graphe dirigé ?

n°1033046
Chronoklaz​m
Posté le 02-04-2005 à 12:10:45  profilanswer
 

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 !
n°1033048
Chronoklaz​m
Posté le 02-04-2005 à 12:13:20  profilanswer
 

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 !
n°1033051
lordankou
Posté le 02-04-2005 à 12:16:32  profilanswer
 

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é ?

n°1033054
Chronoklaz​m
Posté le 02-04-2005 à 12:28:17  profilanswer
 

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 !
n°1033060
lordankou
Posté le 02-04-2005 à 12:35:25  profilanswer
 

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 !

n°1035360
lordankou
Posté le 05-04-2005 à 10:21:53  profilanswer
 

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.     }

n°1035387
nraynaud
lol
Posté le 05-04-2005 à 10:33:33  profilanswer
 

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
n°1036082
lordankou
Posté le 05-04-2005 à 16:45:02  profilanswer
 

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 !

mood
Publicité
Posté le 05-04-2005 à 16:45:02  profilanswer
 

n°1036126
Chronoklaz​m
Posté le 05-04-2005 à 17:10:01  profilanswer
 

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 !

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  programmer une machine de turing en java

 

Sujets relatifs
Quel logicile choisir pour programmer ?Pb d'utilisation de Java
[Java] Afficher un fichier textePopup par java marche pas sous ie mais sous mozilla, pkoi?
[Java/Struts] Déclencher des actions (.do) dans une Action...[java][applet]inserer des jpanel dans un gridlayout
[C] récupérer @IP machine hoteOuvrir un fichier pdf depuis une application Java
Java et le vectoriel... animé !projet java SWING/JDBC/MySQL
Plus de sujets relatifs à : programmer une machine de turing en java

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.089 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR