Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Tla ch05 machines de turing

Théorie des langages et des automates Ramzi GUETARI Année Universitaire ISI I n s t i t u t Supérieur Informatique ? ? ? ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ?? ?? ISI I n s t i t u t Supérieur Informatique ? ? ? ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ?? ?? Généralités Une machine de Turing est un automate abstrait constitué des éléments suivants ? Une bande in ?nie décomposée en cellules au sein desquelles peuvent être stockés des caractères issus d ? un ensemble ?ni ? Une tête de lecture écriture pouvant ? Lire et modi ?er le caractère stocké dans la cellule correspondant à la position courante de la tête le caractère courant ? se déplacer d ? une cellule vers la gauche ou vers la droite modi ?er la position courante ? Un ensemble ?ni d ? états internes permettant de conditionner le fonctionnement de la machine Copyright ? Ramzi GUETARI ISI I n s t i t u t Supérieur Informatique ? ? ? ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ?? ?? CGénéralités ? une table de transitions indiquant pour chaque couple état interne caractère courant les nouvelles valeurs pour ce couple ainsi que le déplacement de la tête de lecture écriture Dans la table de transitions chaque couple est donc associé à un triplet état interne nouveau caractère nouveau déplacement Copyright ? Ramzi GUETARI ISI I n s t i t u t Supérieur Informatique ? ? ? ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ?? ?? Généralités on o ? switch input tape Copyright ? Ramzi GUETARI guts of the machine rteaaphhtdeaee paawreeddraitde accept or reject tape head can move left or right tape head can read or write ISI I n s t i t u t Supérieur Informatique ? ? ? ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ?? ?? CGénéralités Une machine de Turing TM est un automate d ? états ?ni avec une déformation ? ? Un ruban d ? entrée avec un symbole à chaque position ? Le ruban est taille in ?nie dans les deux directions ? Les positions non occupées contiennent un symbole spécial ??celluleblanche ? noté B on peut aussi utiliser ? La TM a une tête de lecture écriture pouvant se déplacer dans les deux sens gauche et droite ? La tête est initialement placée sur le premier symbole d ? entrée ? Le contenu d ? un emplacement case dans la ruban d ? entrée peut être remplacé par un autre symbole Copyright ? Ramzi GUETARI ISI I n s t i t u t Supérieur Informatique ? ? ? ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ?? ?? Généralités Une TM M E ?? ?? ? B e F o? ?