// ----------------------------------------------------------------------
// Classes utiles
// ----------------------------------------------------------------------
class Tete {
private int position;
public Tete() {
position = Turing.POSITION_INITIALE;
}
public int getPosition() {
return position;
}
public void setPosition(int position) {
this.position = position;
}
public void avance() {
position++;
}
public void recule() {
position--;
}
}
class Transition {
private int etat;
private char caractere;
private int deplacement;
public Transition(int etat, char caractere, int deplacement) {
this.etat = etat;
this.caractere = caractere;
this.deplacement = deplacement;
}
public int getEtat() {
return etat;
}
public char getCaractere() {
return caractere;
}
public int getDeplacement() {
return deplacement;
}
}
class TMachine {
private int etatActuel;
private String bande;
private Tete tete;
private Transition table [][];
public TMachine(Transition[][] table) {
etatActuel = Turing.ETAT_INITIAL;
bande = "";
tete = new Tete();
tete.setPosition(Turing.POSITION_INITIALE);
this.table = table;
}
/**
* Réinitialise une machine et écrit les données d'entrée sur la bande.
* @param entree Les données d'entrée
*/
public void reinitialise(final String entree) {
etatActuel = Turing.ETAT_INITIAL;
bande = entree;
tete.setPosition(Turing.POSITION_INITIALE);
}
/**
* Lit le caractère courant sur une bande doublement infinie.
* Simule l'aspect infini négatif en ajoutant un caractère en début de
* chaîne puis en décalant la valeur de la tête (càd la remettre à 0)
* @return Le caractère lu
*/
private char lecture() {
// simulation du ruban pour les positions négatives
while (tete.getPosition() < 0) {
bande = Turing.EPSILON + bande;
tete.avance();
}
// insertion des EPSILON nécessaires pour les position positives
while (tete.getPosition() >= bande.length()) {
bande = bande + Turing.EPSILON;
}
// lecture du caractère
return bande.charAt(tete.getPosition());
}
/**
* Écrit un caractère sur une bande doublement infinie.
* Simule l'aspect infini négatif en ajoutant un caractère en début de
* chaîne puis en décalant la valeur de la tête (càd la remettre à 0)
* @param Le caractère à écrire
*/
private void ecriture(char c) {
// simulation du ruban pour les positions négatives
while (tete.getPosition() < 0) {
bande = Turing.EPSILON + bande;
tete.avance();
}
// insertion des EPSILON nécessaires pour les positions positives
while (tete.getPosition() >= bande.length()) {
bande = bande + Turing.EPSILON;
}
// écriture du caractère
bande = bande.substring(0, tete.getPosition()) + c
+ bande.substring(tete.getPosition() + 1, bande.length());
}
/**
* Affiche l'état de la machine de Turing
*/
private void affiche() {
System.out.println(" --------------------------------");
System.out.println(" Etat actuel : " + etatActuel);
System.out.println(" Bande :");
System.out.println(" " + bande);
System.out.print(" ");
for (int i = -1; i < tete.getPosition(); i++) {
System.out.print(" ");
}
System.out.println("^ (Tete : " + tete.getPosition() + ")");
System.out.println(" --------------------------------");
}
/**
* Lance l'exécution de la machine de Turing
*/
public void lance() {
System.out.println("Lancement de la machine de Turing");
affiche();
while (etatActuel != UNDEF) {
// Cherche la position à lire dans la table de transition
// Indice de ligne
int i = etatActuel - 1;
// Indice de colonne (caractère lu)
System.out.print(" lu : " + lecture() + ",");
int j = 0;
switch (lecture()) {
case '0':
j = 0;
break;
case '1':
j = 1;
break;
case EPSILON:
j = 2;
break;
default:
System.out.println("ERREUR: j'ai lu un caractère inconnu: " + lecture());
affiche();
}
// Mise à jour de la machine
etatActuel = table[i][j].getEtat();
System.out.print(" nouvel état : " + etatActuel + ",");
ecriture(table[i][j].getCaractere());
System.out.print(" écrit : " + table[i][j].getCaractere() + ",");
switch (table[i][j].getDeplacement()) {
case 1:
tete.avance();
System.out.println(" avance");
break;
case -1:
tete.recule();
System.out.println(" recule");
break;
default:
System.out.println("ERREUR: déplacement inconnu: "
+ table[i][j].getDeplacement());
affiche();
}
affiche();
}
System.out.println("Arrêt de la machine de Turing.");
}
}
/**
* Classe Principale
*/
class Turing {
public static final char EPSILON = 'e';
public static final int POSITION_INITIALE = 0;
public static final int UNDEF = 0;
public static final int ETAT_INITIAL = 1;
public static void main(String[] args) {
// Définit la table pour le calcul de parité
Transition[][] table1 = {
{new Transition(1, '0', +1), new Transition(1, '1', +1), new Transition(2, EPSILON, -1)},
{new Transition(3, EPSILON, -1), new Transition(4, EPSILON, -1), new Transition(UNDEF, EPSILON, -1)},
{new Transition(3, EPSILON, -1), new Transition(3, EPSILON, -1), new Transition(5, '1', +1)},
{new Transition(4, EPSILON, -1), new Transition(4, EPSILON, -1), new Transition(5, '0', +1)},
{new Transition(UNDEF, EPSILON, -1), new Transition(UNDEF, EPSILON, -1), new Transition(UNDEF, EPSILON, -1)}
};
// La table pour l'inversion des bits est donnée ci-après
// A vous de "l'injecter" dans votre programme dans le bon format
// voir table ci-dessus.
/* { { 2, '0', +1}, { 3, '1', +1}, {UNDEF, EPSILON, +1} },
{ { 2, '0', +1}, { 3, '1', +1}, { 4, EPSILON, +1} },
{ { 2, '0', +1}, { 3, '1', +1}, { 5, EPSILON, +1} },
{ { 4, '0', +1}, { 4, '1', +1}, { 6, '0', -1} },
{ { 5, '0', +1}, { 5, '1', +1}, { 6, '1', -1} },
{ { 6, '0', -1}, { 6, '1', -1}, { 7, EPSILON, -1} },
{ { 8, EPSILON, -1}, { 8, EPSILON, -1}, { 7, EPSILON, -1} },
{ { 10, '0', +1}, { 11, '1', +1}, { 9, EPSILON, +1} },
{ {UNDEF, '0', -1}, {UNDEF, '1', -1}, { 9, EPSILON, +1} },
{ { 4, '0', +1}, { 4, '1', +1}, { 10, EPSILON, +1} },
{ { 5, '0', +1}, { 5, '1', +1}, { 11, EPSILON, +1} }
};*/
TMachine m = new TMachine(table1);
//m.reinitialise("10");
m.reinitialise("1101");
m.lance();
}
}
Admin CliCours
