Next PDF List

Automates ch1 1CH. 1) Automates finis•1. 1) Les automates finis déterministes•1. 2) Les automates finis non déterministes•1. 3) Les automates avec e-transitions•1. 4) Les expressions régulières•1. 5) L'équivalence des modèlesAutomates ch1 21.

1) Les automates finis déterministesM = (Q, S, d, q0, F) est un AFDQ ensemble fini d'étatsS alphabet finiq0 état initialF ensemble des états terminauxd fonction de transitio x S ® QFonction de transition étendue aux mots :1- d'(q, e) = q2- d'(q, wa) = d(d'(q, w), a)Les deux coïncident sur les lettresAutomates ch1 3Mot x accepté ou reconnu si d'(q0, x) est terminal.Reconnaissance de x en temps O(n).Langage accepté L(M) = ensemble des mots acceptés.Langage reconnaissable = langage accepté par un AFDExemple23ab01ababab L(M) = mots se terminant par aabAutomates ch1 41.

2) Les automates finis non déterministesA priori plus général. Utilité théorique, mais aussiplus facile à construire.

Mais plus coûteux à utiliser.M = (Q, S, d, q0, F) est un AFNSeule différence :d fonction de transitio x S ® 2QFonction de transition étendue aux mots :1- d'(q, e) = {q}2- d'(q, wa) = {p : $r Î d'(q, w) et p Î d(r, a)}Les deux coïncident sur les lettres3- d'(P, w) = È d'(q, w)Automates ch1 5Exemple23b01aa, baL(N) = mots se terminant par aabMot x accepté ou reconnu si d'(q0, x) contient unétat terminal = il existe un chemin de q0 vers un étatterminal dont la suite des étiquettes vaut x.Reconnaissance de x en temps O(2n).Langage accepté L(N) = ensemble des mots acceptés.Théorème : Si L est accepté par un AFN, alors il est acceptépar un AFD.Automates ch1 61.

3) Les automates avec e-transitionsComme les AFN, mais il peut aussi y avoir des transitions surle mot vide e.eabaabeeeeeee1234567891011ExempleL(N) = mots se terminant par aabAutomates ch1 7Mot x accepté ou reconnu s'il existe un chemin de q0vers un état terminal dont la suite des étiquettes vaut x.Le mot vide est neutre pour la concaténation, donc tousles chemins ne sont pas de longueur n.Reconnaissance de x en temps O(2n).Langage accepté L(N) = ensemble des mots acceptés.Notion importante : la e-clôture.clot(q) = {p : il existe un chemin étiqueté e de q à p}La détermination de la e-clôture se fait par un algorithmed'exploration du graphe obtenu en ne conservant que lestransitions vides.Automates ch1 8Théorème : Si L est accepté par un AFN avec e-transitions,alors il est accepté par un AFN sans e-transitions.Corollaire : Les langages acceptés par les AFD, les AFNsans e-transitions et les AFN avec e-transitions coïncident.Automates ch1 91.

4) Les expressions régulièresElles permettent de spécifier a priori un langage, alors que lesautomates permettent de tester l'appartenance d'un mot à un langagedéjà spécifié.Opérations régulières sur les langages :- réunion ensembliste È ou +- produit de concaténation- fermeture transitive *Les expressions régulières sont des chaînes de caractères contituées delettres et de e, de parenthèses et de symboles opératoires +, . ou ,*.

Cette chaîne peut être vide, notée AE.Automates ch1 10Expressions régulières : i) L'expression régulière e représente{e} ; ii) Si a est une lettre, alors c'est une expression régulière qui représente{a} ; iii) Si r et s sont des expressions régulières qui représentent L(r) et L(s), alors : • r + s représente L(r) È L(s) (ou r | s) • rs représente L(r)L(s) • r* représente L(r)*.Langage régulier = langage représenté par expression régulière.Tous les langages finis sont réguliers.Automates ch1 11Exemples :(a + b)* représente tous les mots sur {a, b}a*(ba*)* représente le même langage(a + b)*aab représente les mots se terminant par aab.Théorème : Tout langage régulier est reconnaissable par un AFNavec e-transitions.Corollaire : Tout langage régulier est reconnaissable.Démonstration : Algorithme de ThompsonDécrit l'assemblage des automates correspondant aux opérationssur les expressions régulières.Exemple : on retrouve l'AFN avec e-transitions de la p.6 à partir der = (a + b)*aab.Automates ch1 12e• pour e : N(e)• pour a : N(a)• pour r + s : N(r + s )aN(r)N(s)eeeeeN(r)N(s)• pour rs : N(rs)N(r)eee• pour r* : N(r*)Automates ch1 131.

5) L'équivalence des modèlesDémonstrations des théorèmes des paragraphes 2 et 3.Théorème : Si L est accepté par un AFN, alors il est acceptépar un AFD.Démonstration :Donnée : un AFN sans e-transition N.Résultat : un AFD M acceptant le même langage.Les états de M sont des ensembles d'états de N.L'état initial de M est [q0].Si P est un ensemble d'états de N, on définitd'(P, a) = Èp Î P{q : q Î d(p, a)}.Ceci définit récursivement un l'ensemble des états de M.Un état P de M est terminal s'il contient un état terminal de N.Automates ch1 14Remarques :Si P = AE, c'est un état "poubelle" de M.Si d'(P, a) = Q, alors tout état de N qui apparaît dans Q peut être atteint à partir d'un état qui apparaît dans P par une flèche étiquetée a.Cette dernière remarque permet d'établir que d'([q0], w) est final dans M si et seulement si il existe dans N un chemin étiqueté w de q0 à un état terminal de N.Ceci établit le théorème.Exemple : automate du paragraphe 2.Automates ch1 150,1,20,3ab00,1ababab 23b01aa, baOn retrouve l'AFD du paragraphe 1.Automates ch1 16Théorème : Si L est accepté par un AFN avec e-transitions,alors il est accepté par un AFD.Démonstration :Donnée : un AFN avec e-transition N.Résultat : un AFD M acceptant le même langage.Les états de M sont des ensembles d'états de N.Il faut faire attention aux e-clôtures.L'état initial de M est Clot([q0]).Si P est un ensemble d'états de N, on définitd'(P, a) = Èp Î PClot({q : q Î d(p, a)}).Ceci définit récursivement un l'ensemble des états de M.Un état P de M est terminal s'il contient un état terminal de N.Automates ch1 17Remarques :Si d'(P, a) = Q, alors tout état de N qui apparaît dans Q peut être atteint à partir d'un état qui apparaît dans P par une flèche étiquetée a ou par un chemin étiqueté aeeee Cette dernière remarque permet d'établir que d'(Clot([q0]), w) est final dans M si et seule