Remerciez-le!

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

1 1 Théorie des langages et des Théorie des langages et des automates automates

1 1 Théorie des langages et des Théorie des langages et des automates automates Ramzi Ramzi GUETARI GUETARI Année Universitaire 2011 / 2012 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Généralités Une bande infinie, décomposée en cellules au sein desquelles peuvent être stockés des caractères (issus d’un ensemble fini). Une tête de lecture / écriture pouvant :  Lire et modifier 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 (modifier la position courante). Un ensemble fini d’états internes permettant de conditionner le fonctionnement de la machine. 2 07/12/2011 Copyright © Ramzi GUETARI Une machine de Turing est un automate abstrait, constitué des éléments suivants: 2 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Gé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) 3 07/12/2011 Copyright © Ramzi GUETARI ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Généralités 4 07/12/2011 Copyright © Ramzi GUETARI accept or reject tape head can move left or right. "guts" of the machine tape read head input tape on/off switch tape head can read or write! tape read/write head 3 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Généralités Un ruban d’entrée avec un symbole à chaque position. Le ruban est taille infinie dans les deux directions. Les positions non occupées contiennent un symbole spécial “cellule- blanche” 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. 5 07/12/2011 Copyright © Ramzi GUETARI Une machine de Turing (TM) est un automate d’états fini avec une «déformation» : ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Généralités E est un ensebmle fini d’états. est l’alphabet d’entrée. est un ensemble fini de symboles (L’alphabet du ruban) est la fonction de transitions : : E E {L, R} B est un symbole spécial appelé blank. = - {B} e0 est l’état initial. F est l’ensemble des états d’acceptation. 6 07/12/2011 Copyright © Ramzi GUETARI Une TM M = (E, , , , B, e0, F), où 4 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Fonctionnement d’une Machine de Turing La bande est initialisée avec la séquence de caractères correspondant aux données d’entrées. Pour chaque déplacement: la TM écrit un symbole, effectue une transition entre deux états, et déplace la tête d’un cran, à gauche ou à droite. Si la TM accède à un état d’acceptation, elle s’arrête et accepte la bande d’entrée. 7 07/12/2011 Copyright © Ramzi GUETARI ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Fonctionnement d’une Machine de Turing Le déplacement de la tête de lecture est déterminé par l’état et le symbole courants. La tête de lecture/écriture est positionnées sur la première cellule de la bande. La TM commence à l’état initial et recherche le caractère non blanc le plus à gauche sur la bande. Accepteur : La machine accepte ou rejette une bande d'entrée par selon qu'elle se retrouve dans un état d’acceptation ou non. La TM effectue un calcul en modifiant la bande d’entrée pour fournir une sortie. 8 07/12/2011 Copyright © Ramzi GUETARI 5 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Les transition d’une machine de turing Diagramme d’états / transitions : Déplacement vers la droite: si la TM est dans l'état q, et que le symbole courant du ruban est a, écrire b à la place de a, se déplacer d'une position vers la droite, et se placer à l‘état r. Déplacement vers la gauche : même principe sauf que le déplacement s’effectue à gauche. 9 07/12/2011 Copyright © Ramzi GUETARI q r q r a/b, R a/b, L ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique Que peut une machine de turing faire ? Il est clair qu‘une TM peut accepter n'importe quel langage régulier. Il suffit pour cela de limiter les «instructions» de lecture de la bande d’entrée de gauche à droite et de ne jamais modifier son contenu. Qu’en est t-il des langages hors contextes ? Une TM peut elle accepter {anbn} ? Qu’en est-il de {anbncn} ? 10 07/12/2011 Copyright © Ramzi GUETARI 6 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique TM pour langages réguliers L (a*b*c*) 11 07/12/2011 Copyright © Ramzi GUETARI 1 2 4 3 a/a, R b/b, R b/b, R c/c, R c/c, R c/c, R B/B, R B/B, R B/B, R ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique TM pour les langages hors contexte L (anbn)  Effacer le premier symbole (a) et le dernier symbole (b) à chaque traitement; si le mot était {anbn}, il ne reste rien à la fin.  Cinq étapes : 1. Si le symbole courant est B, aller à l’étape 5. Si le symbole courant est a, écrire B par dessus et aller à l’étape 2. 2. Se déplacer à droite en ignorant tous les a et b rencontrés. Lorsqu’on arrive au premier caractère B se déplacer à gauche d’une case et aller à l’étape 3. 3. Si le symbole courant est b, écrire B par dessus et aller à l’étape 4. 4. Se déplacer à gauche en ignorant tous les a et b rencontrés. Lorsqu’on arrive au premier caractère B se déplacer à droite d’une case et aller à l’étape 1. 5. Accepter. 12 07/12/2011 Copyright © Ramzi GUETARI 7 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique TM pour les langages hors contexte L (anbn) 13 07/12/2011 Copyright © Ramzi GUETARI 1 2 4 3 a/a, R b/b, R B/B, R 5 a/B, R B/B, L b/B, L a/a, L b/b, L B/B, R ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique TM pour les langages hors contexte L (anbn) – Une autre approche : On marque chaque a et chaque b correspondant avec X. On va considérer le premier a et le premier b rencontrés à chaque phase de gauche à droite. Chaque fois qu’un symbole a est marqué, on se déplace à droite jusqu’à ce qu’on rencontre un symbole b. Marquer le symbole b et se déplacer à gauche jusqu’au premier symbole a restant. Répéter l’opération tant c’est possible. S’il n’y a plus de symboles a, se déplacer à droite pour vérifier qu’il n’y a plus de symboles b non plus. 14 07/12/2011 Copyright © Ramzi GUETARI 8 ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique TM pour les langages hors contexte L (anbn) 15 07/12/2011 Copyright © Ramzi GUETARI 1 2 6 3 5 4 a/X, R a/a, R X/X, R X/X, R b/X, L X/X, L a/a, L a/a, L X/X, R B/B, R 7 X/X, R B/B, R B/B, R b/X, L ّﺔ اﻟﻤﻌﮭﺪ اﻟﻌﺎﻟﻲ ﻟﻺﻋﻼﻣﯿISI I n s t i t u t S u p é r i e u r Informatique TM pour les langages hors contexte Stratégie pour anbncn 1. Si le symbole courant est B, aller à l’étape 7. Si le symbole courant est a, le remplacer par un X et aller à l’étape 2. 2. Se déplacer à droite en passant tous les symbole a et Y. au premier symbole b, le réécrire par Y et aller à l’étape 3. uploads/Litterature/ tla-ch05-machines-de-turing.pdf