Automates d’états finis : Automates de Rabin Scott PDF

Chapitre 3 Automates d’états finis : Automates de Rabin Scott 1 Un automate d’état finis est composé d’une bande finie en entrée, d’un organe de commande et d’une tête de lecture (figure 1). L’automate d’états finis n’a pas de mémoire auxiliaire....

Chapitre 3 Automates d’états finis : Automates de Rabin Scott 1 Un automate d’état finis est composé d’une bande finie en entrée, d’un organe de commande et d’une tête de lecture (figure 1). L’automate d’états finis n’a pas de mémoire auxiliaire. Tête de lecture Organe de Commande Figure 1: Automate d’états finis 1. Automate d’états finis simple déterministe 1.1 Définition: Un automate d’états finis simple déterministe, noté A, est caractérisé par 5 paramètres que l’on définit comme suit :  X est l’alphabet d’entrée,  S est un ensemble fini d’états  S0 est l’état initial, S0  S,  F est l’ensemble des états finaux, F  S,  II est l’ensemble des instructions (fonction de transition), II : S x X S. Les éléments de II (ensemble d’instructions) sont des triplets (Si, xi, Sj) qu’on lit de la manière suivante : l’automate étant à l’état Si  S et lisant une lettre xi  X en entrée, passe à l’état Sj  S. 1.2 Représentation d’un automate d’états finis simple déterministe Pour décrire un automate d’états finis déterministe, il faut spécifier tous ses paramètres, en particulier l’ensemble des instructions que l’on peut représenter par une table de transition ou par un multigraphe. 1.2.1 Table de transition (représentation matricielle) Pour décrire l’ensemble des instructions II, on peut utiliser une matrice (figure 2). Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 2 Elts de X II x1 x2 … xi … xk S1 S2... Elts de S Si (Si, xi, Sj) Sj... Sn Figure 2: Représentation matricielle de l’ensemble des instructions II. Une entrée est un état Sj auquel l’automate arrive après avoir été à l’état S i et avoir lu, en entrée, la lettre xi. 1.2.2. Représentation graphique Un automate d’états finis déterministe peut-être représenté par un multigraphe orienté où chaque sommet est un état de S et les arcs sont étiquetés par des lettres de X. Une instruction (Si, xi, Sj) est représentée comme suit (figure 3) : xi Si Sj Figure 3 : Représentation graphique de l’instruction (Si, xi, Sj). L’état initial et les états finaux sont représentés respectivement comme dans la figure 4.a et 4.b. S Si Figure 4: a. Etat Initial b. Etat Final. Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 3 Exemple 10 : Automate d’états finis simple déterministe Soit A un automate d’état finis simple déterministe où X = {a, b}, S={S0,S1,S2,S3,S4,S5}, F = {S0, S2, S4 } et II = {(S0, a, S0), (S0, b, S1), (S1, b, S0), (S1, a, S2), (S2, a, S2), (S3, b, S0), (S4, a, S4), (S4, b, S5)} Représentation graphique de l’automate A : a a b a S0 S1 S2 b b a b S3 S4 S5 Figure 5 : Automate d’états finis simple déterministe. Définition: Soit A un automate d’états finis. A est simple si le passage d’un état à un autre se fait à la lecture d’une lettre de X. L’automate d’états finis de la figure 5 est simple. Définition : Soit A un automate d’états finis simple. A est déterministe si et seulement si :  Si, Sj, Sk  S, et  wi  X Si (Si, wi, Sj)  S et (Si, wi, Sk)  S alors Sj = Sk. L’automate d’états finis de la figure 5 est déterministe. 2 Langage reconnu par un automate d’états finis Définition: Soit A un automate d’états finis simple. La lecture d’une lettre wi  X en entrée, fait passer l’automate A de l’état Si à l’état Sj si et seulement si (Si, wi, Sj)  II. Cette lecture est notée Si wi Sj. A Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 4 Définition: Soit A un automate d’états finis simple et déterministe. La lecture d’un mot w  X* (w= w1 w2… wn) fait passer l’automate A de l’état Si  S à l’état Sj  S, w que l’on note Si Sj, s’il existe n-1 états S1, S2, …, Sn-1 tels que : A w1 w2 wn Si S1 S2 … Sn-1 Sj. w est appelé un chemin. A A A Exemple 11 : le mot w= bab est un chemin. Il fait passer l’automate de l’état S 1 à l’état S1 b a b S1 S0 S0 S1 A A A  On note Si Si le chemin vide. A Définition : Soit A un automate d’états finis simple. Un mot w  X* (w= w1 w2… wn) est reconnu par l’automate A s’il fait passer l’automate de l’état S0 à un état Sk  F: S0 w Sk. A w est appelé un chemin réussi. Exemple 12 : le mot w= baa est un chemin réussi. Il fait passer l’automate de l’état S 1 à l’état S1. b a a S0 S1 S2 S2 A A A Définition : Soit A un automate d’états finis simple et déterministe. Le langage reconnu par A, que l’on note L(A), est l’ensemble des mots reconnus par A : L(A) = {w  X* /  Sk F tq S0 w Sk }. A Définition : Soient A et A’ deux automates d’états finis. On dit que A et A’ sont équivalents si et seulement si L(A) = L(A’). 3 Réduction d’un automate simple Définition : Soit A un automate d’états finis simple. On dit qu’un état Si  S w est accessible dans l’automate A s’il existe un mot w  X* tel que S0 Si. A Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 5 Exemple 13 : L’état S2 est accessible dans l’automate de la figure 5. Si on prend w = ba, on a bien S0 ba Si. A Définition : Soit A un automate d’états finis simple. On dit qu’un état Sj  S w est co-accessible s’il existe un mot w  X* et Sk  F tels que Sj Sk. A Exemple 1 : L’état S1, de l’automate de la figure 5, est co-accessible. Si on prend w = ba, on a bien S1 aa S2. aA Proposition : si A est un automate d’états finis simple, et si A’ est l’automate obtenu à partir de A en éliminant les états non accessibles et non co-accessibles alors L(A) = L(A’). On dit que A et A’ sont équivalents. Exercice 1.1 : Démontrer la proposition 1. Cette démonstration se décompose en deux parties. La première consiste à donner l’algorithme de construction de A’ à partier de A. Puis de montrer que L(A) = L(A’). Exemple 14 : Automate réduit a a b a S0 S1 S2 b Figure 6 : Automate d’états finis simple déterministe réduit. La figure 6 représente l’automate réduit équivalent à l’automate de la figure 5. Automate d’états finis simple déterministe complet On dit qu’un automate d’états finis simple déterministe A est complet si et seulement si : wi  Si  S et  wi  X,  Sj  S tels que : SiSj. A Proposition : Pour tout automate d’états finis simple déterministe Asd, il existe un automate d’EF simple déterministe complet Asdc équivalent à Asd. Exercice : Donner la procédure qui permet de construire un automate simple déterministe complet A’ à partir d’un automate simple déterministe A. Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 6 4. Automate d’états finis simple non déterministe Définition 1 : Soit As un automate d’états finis simple. On dit que As est non déterministe s’il existe au moins un w  X* qui admet 2 lectures différentes dans As. Définition 2 : Un automate d’états finis simple non déterministe est un quintuplet Asnd où :  X est l’alphabet d’entrée,  S est un ensemble fini d’états de l’automate,  Sin est l’ensemble des états initiaux (Sin  S),  F est l’ensemble des états finaux (F  S),  II est l’ensemble des instructions (fonction de transition). I I : X x S P(S) wi (Si, wi) { Sj SSi / Sj } Asnd Remarque : Dans ce qui suit, nous supposerons que l’automate non déterministe n’a qu’un seul état initial. Exemple 15: Soit Asnd l’automate suivant: a a a/b a/b a SO S1 S2 Figure 7:Automate non déterministe. Cet automate n’est pas déterministe : Selon la définition 1, On peut trouver un mot w = aaa pour lequel il existe au moins 2 lectures différentes (2 chemins différents). En fait, il existe plusieurs lectures possibles pour aaa. Quelques lectures sont données ci-dessous: a a a S0 S0 S0 S0 Asnd Asnd Asnd a a a S0 S0 S1 S1 Asnd Asnd Asnd a a a S0 S1 S1 S2 Asnd Asnd Asnd Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 7 Selon la définition 2, il existe au moins un état à partir duquel la lecture d’une lettre de X peut faire passer l’automate à deux ou plusieurs états différents. L’état S0 répond à cette définition : a a S0 S0 et S0 S1 Asnd Asnd A partir de S0, l’automate peut lire la lettre a est rester à l’état S0 ou passer à l’état S1. Exemple 16: Soit Asnd l’automate suivant: 0 S1 1 1 SO 1 S2 0 Figure 8. : Automate non déterministe Voyons maintenant le comportement de cet automate à travers la lecture du mot w=1011. Il y a trois chemins possibles pour la lecture du mot 101, deux chemins mènent à S2 et un à S1 ( Figure 9). 0 1 S1 S1 S2 1 S1 1 S2 SO 1 0 1 S2 SO 1 S2 Figure 9 : Lecture du mot 1011 par l’automate Asnd. Lorsque l’automate arrive à l’état S2, il lui reste à lire la dernière lettre 1. Asnd se bloque car il n’existe aucune instruction de type (S2, 1, Si) dans II. Cependant, si Asnd se trouve à l’état S1 et lit 1, il se déplace vers l’état final S2. Le mot est alors accepté par l’automate. Il existe donc un chemin réussi pour ce mot. 4.1 Equivalence des automates d’états finis déterministe et non déterministes Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 8 Pour déterminer si un mot w est accepté par une automate simple non déterministe Asnd, il faut trouver au moins un chemin réussi pour ce mot dans Asnd. Cela revient à faire faire plusieurs lectures de ce mot par Asnd jusqu'à trouver un chemin réussi s’il existe (figure 9). Pour construire un automate d’états finis simple déterministe Asd, on peut simuler le comportement de l’automate d’états finis simple non déterministe. On peut ainsi supposer que l’automate déterministe équivalent passe par des combinaisons d’états (ensemble d’états), à chaque instant. Exemple 17 : l’exemple de la figure 9 peut être représenté comme suit : 1 0 1 1 {S0} {S1, S2} {S0, S1} {S1, S2 } {S2} Le sous-ensemble d’états vers lequel un mot w mène l’automate à partir de son état initial est appelé ensemble d’états accessibles pour ce mot. Les états de {S1, S2} sont accessibles pour w = 101. En appliquant le concept de sous ensemble d’états accessibles, on peut décrire le comportement de l’automate sur des mots de X* : Initialement, Asnd se trouve à l’état S0 puis à la lecture de 1, il peut se déplacer soit à S1 ou S2. Si Asnd se trouve à l’état S0 et lit 0, l’automate se bloque : 1 {S0} {S1, S2} Nous pouvons considérer que l’automate déterministe Asd à la lecture de 1 vas se déplacer vers un état {S1, S2}. Si Asnd se trouve à l’état S1 ou S2 et lit 0, l’automate se déplace soit à l’état S0 ou S1 (il se déplace vers S0 si l’état courant est S2 et vers S1 si l’état courant est S1. S’il lit 1, l’automate se déplace à l’état S2, seule possibilité : {S0, S1} 0 1 {S0} {S1, S2} 1 {S2} Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 9 En appliquant cette procédure, on obtient le diagramme suivant : {S1} 0 {S1} 0 1 {S2} {S0, S1} 0 1 1 {S1, S2} {S0} {S1, S2} 1 {S2} {S0} 0 Nous remarquons que certains sous ensembles se répètent. Nous allons les fusionner, ce qui donne le diagramme de la figure 10.a. Ce diagramme défini l’ensemble des instructions de l’automate déterministe (figure 10.b). (a) 1 0 {S0} {S1, S2} {S0, S1} 1 0 1 0 1 {S2} {S1} 0 (b) 1 0 SO S1S2 S0S1 1 0 1 0 1 S2 S1 0 Figure 10 : Construction d’un automate d’états finis déterministe. Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 10 L’exemple 17 donne les étapes de la construction d’un automate simple déterministe à partir d’un automate simple non déterministe. Soit Asnd un automate d’états finis simple non déterministe et soit Asd l’automate simple déterministe que l’on veut construire tel que L(Asnd)=L(Asd). Si Asnd lit le mot w  X*, l’automate peut se déplacer à l’un des états possibles. Soit S[w] l’ensemble de ces états: w S[w] = {Si  S/ S0 S}.i } A sn d S[w] contient tous les états accessibles pour le mot w dans Asnd. L’état initial de Asd est défini comme suit : S[] = {S0}. Pour chaque mot w=y.z, on peut exprimer S[y.z] en fonction de S[y]. Un état Si est accessible z pour y.z si et seulement si : Sk Si avec Sk  S[y]. Asd z S[y.z] = {Si  S’ / Sk snd des Sk  S[y]}. Si pour Asd snd Le nombre d’ensembles accessibles distinct est fini puisque chaque ensemble est un sous ensemble S, S étant fini. Si on fait correspondre à l’ensemble des états de l’automate Asd, S’, chaque ensemble accessible avec les transitions telles que définies dans l’exemple 2.3, nous obtenons un automate d’états finis simple déterministe. Les états finaux seront tous les sous-ensembles d’états de S’ contenant un état final de Asnd. Proposition : Pour tout automate d’états finis simple non déterministe Asnd, il existe un automate simple déterministe A’sd équivalent. Démonstration : La preuve se divise en deux parties : 1. Construire l’automate simple déterministe Asd à partir de l’automate d’états finis simple non déterministe Asnd. Cette construction revient à définir chaque paramètre de Asd à partir de ceux de Asnd. 2. Montrer que Asnd et A’sd sont équivalents (L(Asnd)= L(A’sd)). 1. Construction de A’sd Nous pouvons résumer les détails de la construction comme suit : Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 11 a) S’= {S[w] / w  X*} b) S[] est l’état initial de l’automate Asd c) l’ensemble des états finaux de Asd, F’ est défini comme suit F’ = { S[w]  S’ / S[w]  F   } d) Une transition de II’ est le triplet (S[w], xi, S[w.xi] ) où S[w.xi] = {Sk / (Si, xi, Sk)  II pour des Si  S[w]} 2. Démonstration de (L(Asnd)= L(Asd)) Un état S[w] de l’automate Asd est un état final si et seulement si S[w] contient un état final de l’automate Asnd. Pour montrer que L(Asnd)= L(Asd), Il suffit de montrer que chaque mot w, lu par Asnd, mène l’automate Asd de l’état initial S[] à l’état S[w]. Cette démonstration se fera par récurrence sur la longueur de w. Cas particulier : |w| = 0  w =   S[] S[] Asd Hypothèse de récurrence : snd Supposons que y S[] S[y] Asd snd Montrons que pour w = y.xi on a y S[] S[y] Asd snd Un état Sk est accessible pour w si y xi S0 Si Sk pour des états Si  S[y] , A A xi Sk  S[w] ssi Si Sk pour des Si  S[y] (Etape 4.de la méthode de construction de Asd) Asnd En conclusion on a : w S[] S[w]. Asd snd 5. Automate généralisé Définition : Un automate d’états finis généralisé est un 5-Uplets AG où  X est l’alphabet d’entrée,  SG est un ensemble fini d’états de l’automate, Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 12  S0G est l’état initial, S0G  SG1,  FG est l’ensemble des états finaux, FG  SG,  IIG l’ensemble des instructions (fonction de transition), II G : SG x X* P(SG). Définition : Un automate partiellement généralisé est un 5-uplets APG où  SPG est un ensemble fini d’états de l’automate,  S0PG est l’état initial, S0G  SG,  FPG est l’ensemble des états finaux, FPG  SPG,  II l’ensemble des instructions (fonction de transition), II : SPG x X  {} P(SPG). Les transitions dans ces automates sont causées par des lettres de X ou par le mot vide. Exemple 18: S1 ad ab f  SO e S2  Figure 11 : Automate généralisé. Le passage de l’état S0 à l’état S1 se fait à la lecture du mot ab, de longueur 2. Le passage de l’état S0 à l’état S2 se fait à la lecture de la lettre e Le passage de l’état S1 à l’état S2 se fait par transition spontanée, aucune lettre n’est lue pour ce passage. Dans un automate généralisé, il existe trois types de transitions :  Transitions causées par une lettre de X,  Transitions causées par des mots de longueur supérieure ou égale à 2, Transition causées par des mots vides que l’on appelle transitions spontanées. Proposition : Pour tout automate généralisé AG, il existe un automate simple équivalent A. Démonstration : Pour construire l’automate simple A, nous allons éliminer les transitions causées par des mots de longueur supérieure ou égale à 2, puis celles causées par les transitions spontanées. Pour 1 Un automate généralisé peut avoir plusieurs états initiaux, cependant dans ce qui suit nous n’en utiliserons qu’un seul. Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 13 cela nous allons faire appel aux automates partiellement généralisés dont la définition est donnée dans ce qui suit La démonstration de cette proposition se fera en cours. Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 14 Série d’exercices 3.1. Trouver l’automate simple déterministe B tel que L(B) = L(A). A étant l’automate suivant: 3.2. Soit A l’automate d’états finis suivant:  Donner l’automate d’états finis simple déterministe B tel que L(B) = L(A)  Donner l’automate d’états finis complet C tel que L(C) = L(B)  Donner l’automate d’états finis D tel que L(D) = L(C) 3.3. Soit A l’automate d’états finis dont la table de transition est donnée ci-dessous:  a b c S0 - S0,S1 - - S1 S0 - S2 - S2 S1 - - S0 Construire l’automate B tel que L(B) = LR(A) 3.4. Construire les automates non-déterministes qui reconnaissent les langages suivants sur l'alphabet {a,b}, rendre ces automates déterministes et donner les automates compléments.  Tous les mots qui contiennent abab  Tous les mots qui se terminent par abb ou par aaa.  Tous les mots qui commencent par abba ou ont la forme abababab....  L1={w  {a, b}*, |w|a = 2p, |w|b = 2q+1, p, q N}  L2={w  {a, b, c}*, |w|a  (|w|b + |w|c) mod 2 } Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 15 3.5. Construire l’automate reconnaissant le langage des entiers binaires qui sont multiples de 3 puis généraliser au cas des multiples de p, p 4. 3.6. On représente un texte par un mot sur l’alphabet _ = {$,#, ⊔,′′ , c} en adoptant les conventions suivantes : – $ représente une fin de texte ; – # représente une fin de ligne ; – ⊔ reprèsente le caractère espace ; – ′′ est le caractère quote ; – c représente un caractère alphabétique quelconque. Dans un tel texte, une suite de caractères est dite quotée si elle est précédée d’une quote ouvrante et suivie d’une quote fermante. Un texte est dit correctement écrit s’il vérifie les conditions suivantes : 1. les lignes ne commencent pas et ne finissent pas par un espace ; 2. il n’y a jamais 2 espaces consécutifs, sauf éventuellement à l’intérieur d’un texte quoté ; 3. chaque ligne contient un nombre pair de quotes (en particulier, un texte quoté ne peut contenir de fin de ligne, ni de fin de texte) ; 4. une quote ouvrante est soit le premier caractère du texte ou est toujours précédée d’un espace ou d’une fin de ligne et une quote fermante est toujours suivie d’un espace ou d’une fin de ligne ou d’une fin de texte ; 5. une ligne peut être vide. Le texte se termine obligatoirement par $. Construire un automate d’états fini déterministe pour reconnaître un texte correctement écrit. 3.7. Problème du loup, la chèvre et le chou. Mr. M. amène le loup L., la chèvre C. le chou H. au bord de la rivière qu'il veut traverser dans un bateau. Le bateau est tellement petit, que l'homme rentre dedans seul ou avec un seul compagnon. Sans surveillance humaine L. mange immédiatement C., et C. mange H. Comment toute l'équipe peut traverser la rivière? 1. Construire un automate A qui modélise la situation. Il faut retrouver à partir de l'énoncé  Les états de l'automate (S)  Les actions possibles  L'état initial (S0)  Les états finaux (F)  Et les instructions (II) 2. Aider Mr. M. à trouver la solution. 3.8. Construire les automates d’états finis simple déterministe acceptant les langages suivants: * *  ab  X* abX* X = {a, b}  ((ab)*(baa)*)*aa  (ab*a(ab)*aa(ab)*) Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 16  ((a*bc*)*acb*)*  10  (0  11) 0* 1.  (a  b)aab(a  b)*  (b  )((a  ab)*  (bb)*)*  b((aab  b)* a(aa)*)* b* 3.9. Pour les 4 automates suivants, déterminer les expressions régulières dénotant les langages reconnus par ces automates : a/ b/ c/ d/ 3. 10. Pour chacun des langages suivants, construire l’automate d’états finis qui le reconnaît: L1 = {w  X* / w commence par u } L2 = {w  X* / w se termine par v } L3 = {w  X* / w admet z comme facteur propre } Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 17 Montrer que le langage L est un langage régulier : L = { w  X* /w commence par u se termine par v et n’admet pas z comme facteur propre } 3. 11. Soit L un langage régulier, on note: FG(L) = {w  X* /  u  X* et wu  L } + FGP(L) = {w  X* /  u  X et wu  L } * * FD(L) = {w  X /  u  X et uw  L } * + FDP(L) = {w  X /  u  X et uw  L } * L//u = {w  X / uw  L} Etudier la nature ces langages. 3.12. Soit L le langage défini par l’expression régulière suivante E = 0 1 [(( 1 0)*  111 )*  0 ]* 1 Donner l’automate déterministe complet reconnaissant le langage L // 010111101 3.13. Soit une grammaire G SaS/bS/aA AaD/bD DA/ Donner la grammaire régulière droite du complément de L(G) 3.14. Les langages suivants sont-ils réguliers? Justifier vos réponses L1 = {w  0, 1} / w wR } L2 = {w  a, b, c} / |w| a = |w| b } L3 = {ai bj aj avec i, j  0 } L4 = {an bp / n  p} L5 = (01) j aa 0i+j, i, j  0 L6 = (ab) n c m (be)n+m, n, m  0 L7 = a i bj c bi+j , i > j 3.15. Exercice du contrôle final 2012 Soient L1 = {w  {a, b, c}* tq |w|a  0 } et L2 = { w  {a, b}* tq |w|b  1 } deux langages réguliers. 1. Donner les automates A1 et A2 reconnaissant respectivement les langages L1 et L2, 2. Construire l’automate A reconnaissant L1  L2 3. Soient L1 et L2 deux langages réguliers, montrer que L1  L2 est régulier. (Justifier vos réponses). 3.16 Exercice du contrôle final 2018 Soit l’expression régulière E= b*a(a*b U a)*a+ 1. Donner l’automate simple déterministe complet reconnaissant L(E) (Utiliser les dérivées). 2. Donner la grammaire régulière droite du complément de L(E)//b*aa Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI Chapitre 3 Automates d’états finis : Automates de Rabin Scott 18 3.17 Exercice du contrôle final 2018 Donnez les automates les plus adéquats reconnaissant les langages suivants L1 = {aib2i ai i ≥ 0} L2 = {0i1j2k | i≠j or j≠k} Benatchba - Sadeg - Boumahdi - Faisal - Khelifati- Tolba – Aries ESI