Chap. 7 - Automates à États Finis Non Déterministes (PDF) 2021 - 2022

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année INF 302 : Langages & Automates Chapitre 7 : Automates à États Finis Non Déterministes...

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année INF 302 : Langages & Automates Chapitre 7 : Automates à États Finis Non Déterministes Yliès Falcone [email protected] — www.ylies.fr Univ. Grenoble-Alpes, Inria - Laboratoire d’Informatique de Grenoble - www.liglab.fr Équipe de recherche LIG-Inria, Corse - team.inria.fr/corse/ Année Académique 2021 - 2022 Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 1 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes 2 Déterminisation des automates non-déterministes 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 2 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes Idée et motivation Définition et langage reconnu 2 Déterminisation des automates non-déterministes 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 3 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Idée, motivation Idée : Déterminisme : Pour chaque état et pour chaque symbole de l’alphabet, il existe au plus un état successeur (c’est-à-dire 0 ou 1). Non-déterminisme : Pour un état et un symbole, on peut avoir 0, 1 ou plusieurs états successeurs. Motivations Il est souvent plus facile de trouver un automate non-déterministe qui reconnaît un langage L qu’un automate déterministe. Pour certains langages, on peut trouver un automate non-déterministe reconnaisseur qui est plus petit que tout automate déterministe reconnaisseur. Mais Nous verrons qu’on ne pourra pas se passer des automates déterministes. Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 4 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Automates non-déterministes : exemple Soit = {0, 1}. Soit L3 le langage constitué des mots de longueur Ø 3 et dont le 3ieme symbole en partant de la droite est 1. 0,1 1 0,1 0,1 0 1 2 3 Le plus petit automate déterministe qui reconnaît L3 a 8 états. Plus généralement Soit Lk le langage constitué des mots de longueur Ø k et dont le kème symbole de droite est 1. Aucun automate déterministe avec moins de 2k états ne reconnaît Lk. Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 5 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes Idée et motivation Définition et langage reconnu 2 Déterminisation des automates non-déterministes 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 6 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Automates non-déterministes Définition Définition (Automate à états finis non-déterministes (AEFND)) Un AEFND est donné par un quintuplet (Q, , qinit , , F ) où : Q est un ensemble fini d’états, est l’alphabet de l’automate, qinit œ Q est l’état initial, ™Q◊ ◊ Q est la relation de transition, F ™ Q est l’ensemble des états accepteurs. Exemple (AEFND) 0,1 1 0,1 0,1 0 1 2 3 0,1 0,1 0 1 0 1 2 Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 7 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Automate à états Finis Non-déterministes Configuration, dérivation, exécution Soit A = (Q, , qinit , , F ) un AEFND. Définition (Configuration) Une configuration de l’automate A est un couple (q, u) où q œ Q et u œ ú. Définition (Relation de dérivation) On définit la relation æ de dérivation entre configurations : ’q œ Q, ’a œ , ’u œ ú : (q, a · u) æ (q Õ , u) ssi (q, a, q Õ ) œ. Définition (Exécution) Une exécution de l’automate A sur le mot u est une séquence de configurations (q0 , u0 ) · · · (qn , un ) telle que ’i œ {0,... , n ≠ 1} : (qi , ui ) æ (qi+1 , ui+1 ). u0 = u, un = ‘, q0 = qinit. On dénote par ≠æ la fermeture réflexive et transitive de ≠æ. ú Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 8 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Acceptation d’un mot par un AEFND Soit A = (Q, , qinit , , F ) un AEFND Définition (Acceptation d’un mot) Un mot u œ ú est accepté par A, s’il existe une exécution de A sur u telle que l’état de sa dernière configuration soit accepteur. Exemple (Acceptation d’un mot par un AEFND) 0,1 0,1 Mots acceptés : 01 car exécution (0, 01) · (1, 1) · (2, ‘) 0 0 1 1 2 001 car exécution (0, 001) · (0, 01) · (1, 1) · (2, ‘) Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 9 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Langage reconnu par un AEFND Définition (Langage reconnu) Le langage reconnu par A, noté L(A), est l’ensemble {u œ ú | u est accepté par A}. Exemple (Langage reconnu) Mots sur = {0, 1} qui contiennent un 0 suivi d’un 1 0,1 0,1 0 1 0 1 2 Mots sur = {0, 1} qui terminent par un 0 suivi d’un 1 0,1 0,1 0 OU... 0 1 0 1 0 1 2 0 1 2 Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 10 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année AEFNDs vs AEFDs Utiliser les AEFNDs facilite la conception d’un automate reconnaissant/définissant un langage. Nous avons évidemment : Tout AEFD est un AEFND Par définition. Nous allons montrer : Tout AEFND a un AEFD équivalent Par déterminisation (calcul des sous-ensembles). Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 11 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes 2 Déterminisation des automates non-déterministes Procédure de déterminisation Correction de la procédure de déterminisation À propos de la complexité de la déterminisation 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 12 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Procédure de déterminisation (subset construction) L’idée Objectif de la procédure : entrée : un AEFND, sortie : un AEFD qui reconnaît le même langage que l’automate d’entrée. Rabin & Scott (1959) On va coder dans un état accessible par un mot u dans l’automate déterministe tous les états qu’on peut atteindre avec u dans l’automate non-déterministe. Soit = {0, 1}. 0,1 0,1 0 1 0 1 2 0 1 0 1 0 0 1 0 0,1 0,2 0,1,2 1 Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 13 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Procédure de déterminisation Soit A = (Q, , qinit , , F ) un AEFND. Définition (Déterminisé d’un automate) Le déterminisé de A, noté Det(A), est l’automate à états fini déterministe : (P(Q), , {qinit }, ”, F ) où : ”(X , a) = {q Õ | ÷q œ X : (q, a, q Õ ) œ }, F = {X œ P(Q) | X fl F ”= ÿ} (cad. X œ F ssi X fl F ”= ÿ). Intuition L’ensemble des états du déterminisé (P(Q)) est l’ensemble des sous-ensembles d’états. À partir d’un ensemble d’états X ™ Q, l’ensemble des états sur un symbole est l’ensemble des états que l’on peut atteindre à partir des états de X avec ce symbole. Les états accepteurs du déterminisé sont ceux qui contiennent au moins un état accepteur. Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 14 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Procédure de déterminisation : exemple 0,1 1 0,1 0,1 0 1 2 3 0 0 02 03 1 1 0 0 1 0 01 013 0 1 0 1 1 0 012 023 1 0 0123 1 Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 15 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes 2 Déterminisation des automates non-déterministes Procédure de déterminisation Correction de la procédure de déterminisation À propos de la complexité de la déterminisation 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 16 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Procédure de Déterminisation Correction de la procédure Rappel : pour ” ™ Q ◊ ◊ Q une relation de transition (qui peut être une fonction), ” ú dénote la fermeture réflexive et transitive de ”. Extension des fonctions de transition Représenter l’ensemble d’états atteint depuis un ensemble d’états : à partir d’un symbole, i.e., ” : P(Q) ◊ æ P(Q), à partir d’un mot, i.e., ” ú : P(Q) ◊ ú æ P(Q). à partir automate déterministe automate non-déterministe (fonction de transition ”) (relation de transition ) t t d’un symbole ”(Q, a) = qœQ {”(q, a)} ”(q, a) = qœQ {q | (q, a, q ) œ Õ Õ } ” (Q, ‘) ú =Q d’un mot ” (Q, x · a) ú = ”(” ú (Q, x ), a) Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 17 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Procédure de Déterminisation Correction de la procédure Théorème : correction de la procédure de déterminisation L(Det(A)) = L(A) Preuve Soit D = (Q D , , {qinit }, ”D , F D ) un AEFD construit par déterminisation de N = (Q N , , qinit , ”N , F N ) Preuve de ”Dú ({qinit }, w ) = ”Nú (qinit , w ) par induction sur |w |. D et N acceptent tous deux w œ ú ssi ”Dú ({qinit }, w ) fl FN ”= ÿ et ”Nú (qinit , w ) fl FN ”= ÿ, respectivement. Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 18 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Procédure de déterminisation Preuve de la correction de la procédure Preuve de ”Dú ({qinit }, w ) = ”Nú (qinit , w ) par induction sur w Base |w | = 0, i.e., w = ‘. D’après les définitions des fonctions de transitions pour les AEFDs et les AEFNDs, on a : ”Dú ({qinit }, ‘) = ”Nú (qinit , ‘) = {qinit } Induct. Soit w = x · a un mot (x œ ú et a œ ) et supposons l’hypothèse vérifiée pour x. D’après l’hypothèse d’induction, on a ”D ú ({q N init }, x ) = ”N (qinit , x ) ™ Q ú Soit {p1 , p2 ,... , pk } cet état D’après la définition inductive de ”N ú , on a : k € ú ”N (qinit , w ) = ”N (pi , a) (Eq.1) i=1 D’après la procédure de déterminisation, on a : k € ”D ({p1 , p2 ,... , pk }, a) = ”N (pi , a). (Eq.2) i=1 En utilisant (Eq.2) et ”D ú (q init , x ) = {p1 , p2 ,... , pk } et la définition inductive de ”D ú pour les AEFDs : ú ({q ! " init }, w ) = ”D ”D ú ({q ”D init }, x ), a = ”D ({p1 , p2 ,... , pk }, a) tk = ” (p , a). i=1 N i (Eq.3) En utilisant (Eq.1) et (Eq.3), on a ”D ú ({q init }, w ) = ”N (qinit , w ). ú Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 19 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes 2 Déterminisation des automates non-déterministes Procédure de déterminisation Correction de la procédure de déterminisation À propos de la complexité de la déterminisation 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 20 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année À propos de la complexité de la déterminisation En pratique, la taille de l’AEFD généré est sensiblement la même que celle de l’AEFND initial. Exemple (Un exemple où les choses se passent mal) Soit = {0, 1} et soit Lk le langage constitué des mots de longueur Ø k et dont le k-ième symbole de droite est 1 : Lk = {a1 · · · an | n Ø k · an≠k+1 = 1} 0,1 1 0,1 0,1 0,1 0,1 0 1 2... k-1 k Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 21 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année À propos de la complexité de la déterminisation Sur cet exemple Lemme Aucun automate déterministe avec moins de 2k états ne reconnaît Lk. Preuve par contraposition Soit A = (Q, , qinit , ”, F ) un automate déterministe tel que |Q| < 2k et L(A) = Lk. Soient u = a1 · · · ak et v = b1 · · · bk deux mots différents de longueur k tels que ” ú (qinit , u) = ” ú (qinit , v ). De tels mots doivent exister car il existe 2k différents mots de longueur k et seulement |Q| < 2k états. Soit q = ” ú (qinit , u). Comme u et v sont différents, il existe i tel que ai ”= bi. Sans perte de généralité (symétrie de ”=), supposons ai = 1 et bi = 0. Soient u Õ = u0i≠1 et v Õ = v 0i≠1. Alors, u Õ (|u Õ | ≠ k + 1) = u Õ (k + i ≠ 1 ≠ k + 1) = u Õ (i) = ai = 1, et v Õ (|v Õ | ≠ k + 1) = bi = 0. Donc u Õ œ Lk et v Õ ”œ Lk. Ceci implique ” ú (q, 0i≠1 ) œ F et ” ú (q, 0i≠1 ) œ / F. Contradiction. Ainsi, ” ú (qinit , u Õ ) = ” ú (qinit , v Õ ) n’est pas possible. Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 22 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes 2 Déterminisation des automates non-déterministes 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 23 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Applications en informatique Plusieurs applications en informatique : Reconnaissance de texte (web-browser). Compilation : analyse lexicale (reconnaissance ces mots clés d’un langage de programmation). Spécification de systèmes : non-déterminisme utilisé pour modéliser l’inconnu (environnement). Exemple (Reconnaissance d’un ensemble de mots clés) ⌃ e b 1 2 2 ⌃ w 0 h ⌃ t t p 4 5 6 7 Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 24 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes 1 Automates à états finis non déterministes 2 Déterminisation des automates non-déterministes 3 Applications en informatique 4 Résumé Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 25 / 26 Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année Plan Chap. 7 - Automates à États Finis Non Déterministes Résumé Automates d’États-Finis Non-Déterministes Définition Critère d’acceptation, langage reconnu Concision des AEFND vs AEFD Procédure de déterminisation algorithme correction idée sur la complexité Applications des AEFNDs en informatique Y. Falcone (UGA - Inria) INF 302 : Langages & Automates Année Académique 2021 - 2022 26 / 26