Remerciez-le!

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

Comparaison entre un automate et un arbre 1

Comparaison entre un automate et un arbre Introduction On va dans cet exposé comparer les automates et les arbres dire les points communs et les points divergents Table des matières I- Qu'est-ce qu'un automate II- Qu'est- ce qu'un arbre III- Quel est le point commun entre un automate et un arbre IV- Qu'est-ce qui distingue les arbres des automates V- Quel est le point commun entre une une expression régulière et une règle de réécriture VI- Qu'est-ce qui distingue une expression régulière d'une règle de réécriture VII- Qu'est-ce qu'une expression régulière VIII- Qu'est-ce qu'une règle de réécriture Conclusion Bibliographie I- Qu'est-ce qu'un automate Un automate à états ?nis est un quintuplet M V Q q F ? o? V est le vocabulaire par exemple V je nous précis er ai s ion Q est l'ensemble des états par exemple Q q q q q q est l'état initial F est l'ensemble des états accepteurs par exemple F q q q ? est l'ensemble des transitions par exemple ? q je q q nous q q précis q q er q q ai q q s q q ion q Un automate est un algorithme de reconnaissance de mots qui lit toutes les lettres d'un mot une par une et qui accepte ce mot si sa lecture se termine dans un état accepteur également dit état ?nal CExemple illustrant la dé ?nition de automate Chacune des transitions lit les symboles qu'il y a entre un état de départ et un état d'arrivée Par exemple ? q er q Les transitions peuvent être entre autres de nature - Ré exive lorsqu'une boucle relie un état à lui-même Par exemple ? q je q q nous q -Transitive lorsqu'il est possible de sauter des états liés entre eux Par exemple ? q er q q ai q q ion q - Symétrique lorsque on peut faire un va et vient entre deux états consécutifs ? q s q q ion q -Cyclique lorsqu'après avoir parcouru un certain nombre d'états on revient au point de départ ? q je q q s q q ion q Et les automates peuvent être de nature -Déterministe lorsque une seule lecture est possible pour chaque symbole Par exemple pour lire er on ne peut que passer par q et q -Non déterministe lorsque plusieurs lectures sont possibles pour chaque symbole Par exemple si pour lire er on avait le choix entre passer par q et q ou passer par q et q Un mot appartient au langage d'un automate si on peut former ses parties avec le vocabulaire qui est donné et si il est reconnu dans un état accepteur Par exemple l'automate M peut produire les mots précis jeprécis nousprécis jejeprécis nousnousprécis préciser préciserai préciserais préciseraisais jenouspréciseraisais précision etc On peut compter le nombre de lectures possible pour un mot Par exemple pour l'automate non déterministe on n'a qu'une possibilité de lecture possible pour lire précision mais deux pour lire préciser Et on peut compter la