Remerciez-le!

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

Expose automates 1 Introduction Un automate est un outil fondamental en Informatique o? il intervient notamment en compilation des langages informatiques procédé permettant de passer d'un langage de haut niveau en langage machine binaire En e ?et les auto

Introduction Un automate est un outil fondamental en Informatique o? il intervient notamment en compilation des langages informatiques procédé permettant de passer d'un langage de haut niveau en langage machine binaire En e ?et les automates interviennent dans le cadre de deux phases d'analyse analyse lexicale automates ?nis et analyse syntaxique automates à pile Qu'est ce qu'un automate Quels sont les di ?érents types d'automates et comment fonctionnent-ils Quels sont leurs liens avec les di ?érents types de grammaire Voilà autant de questions auxquelles nous essaieront de répondre lors de cet exposé I Dé ?nition d'un automate De façon très informelle un automate est un ensemble ??d ? états du système ? reliés entre eux par des ??transitions ? qui sont marquées par des symboles Étant donné un ??mot ? fourni en entrée l ? automate lit les symboles du mot un par un et va d ? état en état selon les transitions Le mot lu est soit accepté par l ? automate soit rejeté II Automates à états ?nis Un automate à états ?nis en anglais ?nite state automaton ou ?nite state machine FSA FSM est une machine abstraite utilisée en théorie de la calculabilité et dans l'étude des langages formels L'automate est dit à états ?nis ? car il possède un nombre ?ni d'états distincts il ne dispose donc que d'une mémoire limitée Pour représenter de façon très intuitive un automate ?ni Q ? ? q F on peut utiliser un graphe de transition constitué des éléments suivants ? Un ensemble de sommets chaque sommet représente un élément de Q ? Un ensemble d ? arcs entre les sommets valués par un symbole de ? un arc entre les états q et q ?? valué par le symbole s signi ?e que ? q s q ?? ? L ? état initial q est marqué par une èche entrante ? Les états ?naux F sont entourés d ? une double ligne Illustration Automates à états ?nis Il existe plusieurs types de machines à états ?nies Les accepteurs ? produisent en sortie une réponse oui ? ou non ? c'est-à-dire qu'ils acceptent oui ou rejettent non l'entrée Les systèmes de reconnaissance classent l'entrée par catégorie En ?n les capteurs sont Cemployés pour produire un certain résultat en fonction de l'entrée Les automates ?nis peuvent caractériser des langages c'est-à-dire des ensembles de mots ?nis le cas standard des langages de mots in ?nis automates de Rabin automates de Büchi ou encore divers types d'arbres automates d'arbres Un langage reconnu par un automate est un langage engendré par une expression régulière La correspondance se fait entre L ? axiome S de la grammaire L' état initial de l ? automate Les variables de la grammaire Les états de l'automate Les règles de la grammaire Les transitions ou les sorties de l'automate Tableau Relation Grammaire régulière-Automate à états ?nis Il existe trois types d'automates à états ?nis les automates déterministes les automates indéterministes non- déterministes et les automates complets II Automates