-
Machine de Turing
Bonjour à tous
Voila je suis à la fac et on me demande de faire une machine de Turing en python mais disons que c'est une chose que je ne verrais qu'en 3eme année et pour être franc je vois pas du tout mais vraiment pas comment faire cela en python.
Je vous donne l'intitulé:
On ajoute à un automate fini déterministe une mémoire non borné constituée d'une bande infinie (des deux cotés). Cette bande est reliée à l'automate par une tête de lecture et d'écriture. A chaque étape, la machine lit le symbole face à sa tête et exécute,selon son état, les instruction données par sa table. Chaque instruction se compose de 3 éléments: l'état suivant, le symbole à écrire sur la bande à la position de la tête et la direction de déplacement de la tête. L'exécution d'une instruction consiste en:
- un changement d'état de l'automate fini
- l'écriture sur la bande d'un symbole à la place de celui qui a été lu
- un déplacement de la tête d'une case à gauche ou à droite
Toutes ces actions ne dépendent que du symbole lu et de l'état courant.
A partir d'une configuration initiale (état initial de l'automate, position de la tête,suite finie de symbole sur la bande) la machine exécute une suite de pas pour s'arrêter quand elle arrive dans un état final de l'automate. Le contenu de la bande représente alors (selon un codage) le résultat du calcul.
La tâche est la réalisation d'une machine de Turing par une classe. Le constructeur prend en argument la description de l'automate fini. La classe possède une méthode qui montre pas à pas l'exécution de la machine.Cette méthode prend en argument l'état initial de la bande.
En utilisant cette classe on pourra construire une machine qui vérifie l'accouplement correct d'une suite de parenthèses (vérification de parenthèsage). La machine pourrai procéder ainsi : dans l'état q0 elle cherche une parenthèse) sur la bande en allant vers la droite. Elle fait alors une transition q1 et elle remplace la parenthèse trouvée par x. Elle cherche maintenant ( en allant vers la gauche etc.
Voila pour être honnête je ne vois pas du tout comment faire cela, n'ayant rien vu de tout ça en cours, sachant que ce cours est à l'origine un cours de math où l'on fait un peut tout et n'importe quoi en Tp. J'espère que quelqu'un pourra m'aider à comprendre et me donner des indications sur comment faire cela.
-
A part le fait que simuler une bande infinie avec un ordinateur disposant d'une quantité de mémoire finie est impossible, cela ne me semble pas très difficile.
Sais-tu ce qu'est un automate fini déterministe ? Si non, commence pas te renseigner là-dessus. Ce n'est pas les ressources qui manquent sur le Web sur ce sujet. Ou est-ce la représentation en Python qui te bloque ?
-
C'est la représentation tout cours qui me bloque que ça soit en python ou dans un autre langage , on ma expliquer ce qu'était un automate fini déterministe mais je vois toujours pas plus comment faire.
-
Ben prenons les transitions par exemple; comment cela se passe-t-il ?
En entrée on a:
- le symbole lu sur la bande (un chaîne de caractères)
- l'état actuel de l'automatique (un entier)
En sortie:
- le nouvel état de l'automate (un entier)
- le symbole à écrire (chaîne de caractères)
- le sens de déplacement de la tête (ou l'indication qu'il s'agit d'un état final) (disons G pour gauche, D pour droite, A pour arrêt)
Il faut choisir une structure de données pour représenter ces transitions, par exemple un dictionnaire dont les clés seraient le couple (état actuel, symbole lu) et les valeurs un triple (nouvel état, symbole à écrire, déplacement). Par exemple:
Code:
transitions = { (1, '(') : (1,'(','D'), (1,')') : (2,'X','G'), ... }
Ce n'est qu'une proposition; j'espère que cela te donne des idées sur la façon de procéder...
