Remerciez-le!

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

UNIVERSITE DE BLIDA 1 Master 2 – Automatique et Informatique Industrielle Facul

UNIVERSITE DE BLIDA 1 Master 2 – Automatique et Informatique Industrielle Faculté de Technologie Département d’Electronique Module : Systèmes à Evénements Discrets Responsable du module : Mme AIT ABDESSLAM S3 -AU : 17/18 1 Chapitre II Modélisation des SED II.1 Langage et Machines à états finis II.1.1 Concepts fondamentaux de la théorie des automates a) Alphabet : un alphabet est un ensemble quelconque. Ses éléments sont appelés lettres ou symboles. Les lettres n’ont pas de propriétés particulières. On demande seulement de savoir tester si deux lettres sont égales ou différentes. Parmi les exemples d'alphabets, il y a bien sûr l’alphabet latin, et tous les alphabets des langues naturelles. Il y a aussi l’alphabet binaire, composé des symboles 0 et 1, l’alphabet hexadécimal, l’alphabet des acides aminés, etc. En informatique, on rencontre l’alphabet des lexèmes, c’est-à-dire des unités syntaxiques résultant de l’analyse lexicale d’un programme. b) Mots ou chaînes : un mot ou une chaîne sur un alphabet A est une suite finie d'éléments de A. On note : ou L'entier n est la longueur du mot. Il existe un seul mot de longueur 0, appelé le mot vide, et noté souvent ε. Le produit de concaténation de deux mots est le mot : obtenu par juxtaposition des deux mots. Le produit de concaténation est associatif, le mot vide est l'élément neutre pour cette opération, ce qui fait de l'ensemble des mots sur l'alphabet A un monoïde (En mathématiques, un monoïde est une des structures algébriques utilisées en algèbre générale. C'est un ensemble muni d'une loi de composition interne associative et d'un élément neutre). Ce monoïde est libre, et est noté A*. c) Langage formel : Un langage formel sur un alphabet A est un ensemble de mots sur A, donc un sous-ensemble de A* . Les opérations ensemblistes (union, intersection, complément) s'étendent bien entendu aux langages. d) Objectifs  La théorie des automates est l'étude des machines abstraites qui permettent de formaliser les méthodes de calcul. L'objet traité par un automate est un mot d'un langage. Pour arriver à la généralité souhaitée, on convertit un « problème » en un langage, et la résolution du problème, en l'analyse d'un élément de ce langage. 2  On représente chaque instance d'un « problème » par un mot. Savoir si l'instance du problème a une solution se ramène à tester si ce mot appartient au langage des mots représentant les instances de ce problème et qui ont une solution. Un automate qui résout le problème prend en entrée un mot et décide s'il est accepté ou non.  Par exemple, le problème de savoir si un entier N est premier (test de primalité) peut se traduire comme suit : on représente tous les entiers naturels par des chaînes binaires (écriture en base 2). Dans ce langage, les mots représentant des nombres premiers forment un sous-ensemble. Le problème du test de primalité consiste alors à savoir si la chaîne binaire représentant un nombre N appartient à ce sous-ensemble ou non. Un automate approprié prend en entrée une chaîne binaire et l'accepte précisément lorsqu'elle représente un nombre premier. e) Caractéristiques communes des automates Il existe de très nombreux modèles d'automates. Les caractéristiques communes aux automates sont les suivantes (avec des variantes possibles) :  Un automate prend en entrée des données discrètes (même si certains automates, appelés automates temporisés, ont des paramètres qui peuvent être des nombres réels). Ces entrées sont généralement des mots finis sur un alphabet fini, mais ce sont aussi des mots infinis, des arbres, des graphes, ou des structures encore plus compliquées.  Un automate possède un nombre fini de configurations internes, appelées états. Là aussi, on peut considérer des automates ayant un nombre infini d'états : par exemple, dans la théorie générale des automates, tout langage formel possède un automate minimal unique, qui n'est fini que si le langage est rationnel.  Un automate peut disposer, par ailleurs, d'une mémoire auxiliaire externe, structurée d'une certaine façon selon le type d'automate. Un automate fini n'a pas de mémoire auxiliaire, un automate à pile a une mémoire en pile ; il existe des automates à mémoire en structure de file, des automates à plusieurs piles, des automates à piles de pile, etc. Les machines de Turing ont une mémoire auxiliaire en forme de bande infinie sur laquelle elles peuvent se déplacer, lire et écrire.  Un automate évolue selon des règles. Ces règles sont en nombre fini. Chaque règle décrit, en fonction des symboles d'entrée, de l'état, et d'une information sur la mémoire auxiliaire, l'évolution de l'automate. Cette évolution peut être déterministe ou non. Elle est déterministe si une seule règle est applicable dans une configuration donnée, elle est non déterministe sinon.  Un automate possède un certain nombre de configurations d'acceptation. Si l'automate se trouve dans une telle configuration, la donnée lue est acceptée. Dans un automate fini, ces configurations sont des états distingués, dans un automate à pile, on peut accepter si la pile est vide, dans une machine de Turing, on accepte si l'état est acceptant. II.1.2 Automate à états finis a) Définition  Un automate fini est une construction abstraite, susceptible d'être dans un nombre fini d'états, un seul état à la fois ; l'état où il se trouve est appelé l'« état courant ». Le passage d'un état à un autre est dirigé par un événement ou une condition ; ce passage est appelé une « transition ». Un automate particulier est défini par la liste de ses états et par les conditions des transitions. La machine abstraite est issue des travaux de A. Turing.  Les automates finis peuvent modéliser un grand nombre de problèmes, parmi lesquels la conception assistée par ordinateur pour l'électronique, la conception de protocoles de communication, l'analyse syntaxique de langages et autres applications d’ingénierie. 3  Dans la recherche en biologie et en intelligence artificielle, les automates finis ou des hiérarchies de telles machines ont été employés pour décrire des systèmes neurologiques. En linguistique, ils sont utilisés pour décrire les parties simples de grammaires de langues naturelles. b) Eléments de l’automate  Un ensemble fni d'états possibles  Un ensemble fni de symboles en entrées  Une fonction de transition entre états II.1.3 Représentations des automates à états finis a) Diagrammes de transition : représentation « graphique ». Le graphe est orienté et étiqueté. Il comprend :  Nœuds : états de l'automate étiquetés par les noms des états. L’état final : double cercle  Arcs orientés : transitions de l'automate étiquetés par les symboles. L’état initial est marqué par un arc sans nœud d'origine Figure II.1 : Diagramme de transition  Pour la lisibilité, lorsque deux arcs de même orientation sont possibles entre deux nœuds, ils sont fusionnés (disjonction)  Un arc peut « boucler » un état sur lui-même  Des transitions peuvent partir de l'état final  Les transitions correspondent à la concaténation. On « suit » les arcs pour voir quel langage est accepté : 4  Le langage n'est pas forcément fini :  Peuvent être mis intuitivement (formellement aussi) en correspondance avec des expressions régulières b) Tables de transition  Équivalente à la représentation par diagramme de transitions  États en lignes, symboles en colonnes - Ligne de l'état initial marqué par une flèche → - Ligne de l'état final marqué par une étoile *  Contenu décrit les transitions depuis un état / symbole Figure II.2 : Diagramme de transition et sa table de transition correspondante 5 c) Notations formelles  Notations pour un automate « déterministe » (DFA)  Un ensemble fini d'états noté : Q = {q1, q2, q3...}  Un ensemble fini de symboles (alphabet) noté : S = {a, b, c, d...}  Une fonction de transition qui prend en paramètre un état et un symbole et qui renvoie un état notée : δ(qi, a) = qj ; (« signature » δ: Q × S → Q)  Un état initial noté : q0 ∈ Q  Un ensemble d'états finaux noté : F ⊆ Q (éventuellement vide)  Un automate à états finis est ainsi défini comme le quintuplé : A = (Q, S, d, q0, F)  Cette définition est équivalente aux diagrammes et tables de transition, elle repose sur la définition de la fonction de transition δ, souvent définie par extension (en listant les cas possibles). La fonction peut renvoyer Ø (par ex. δ (q1, d) = Ø) Théorème de Kleene : par définition, le langage reconnu par un automate à états finis est régulier (ou rationnel). d) Exemples Un premier exemple : un portillon Un exemple très simple d'un mécanisme que l'on peut modéliser par un automate fini est un Portillon d'accès. Un portillon, utilisé dans certains métros ou dans d'autres établissements à accès contrôlés est une barrière avec trois bras rotatifs à hauteur de la taille. Au début, les bras sont verrouillés et bloquent l'entrée, et empêchent les usagers de passer. L'introduction d'une pièce de monnaie ou d'un jeton dans une fente du portillon (ou uploads/s3/ chapii-1-m2-aii-sed-etud.pdf