Comparaison entre un automate et un arbre

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

Documents similaires
Fr explication des trois questions de la tombe 1 0 0
Apprendre autrement avec la pe dagogie positive 0 0
RICTUS ROMANTIQUES, Maxime Prévost Remerciements Pénombres du rire romantique I 0 0
LA GNOSE ORIGINELLE EGYPTIENNE II J. VAN RlJCKENBORGH Avant-propos Homme qui es 0 0
Victor Hugo, Les Misérables, partie II, livre III, chapitre 8, « Désagrément de 0 0
Travail vacances ec1 1 CULTURE GÉNÉRALE - FRANÇAIS TRAVAIL POUR LA RENTRÉE EN EC Une solide culture historique est indispensable pour comprendre les textes de sociologie d ? anthropologie d ? histoire de l ? art d ? histoire de philosophie politique etc q 0 0
Chapitre 2 25 Chapitre Histoire de cryptage arabe Introduction Depuis des temps très reculés l ? homme avait utilisé diverses méthodes et techniques pour envoyer un message secrètement Ce sont des méthodes qui transforment le message en clair en message i 0 0
lois robert greene CDe Robert Greene aux éditions Alisio La e loi Les lois de la nature humaine L ? art de la séduction Stratégie les loi de la guerre Atteindre l ? excellence Power les lois du pouvoir Grand amoureux d ? histoire de littérature et de la F 0 0
Hassan w these Année de soutenance Thèse pour le doctorat en Lexicologie Terminologie Multilingues et Traductologie LA FORMATION DES TRADUCTEURS EN ARABE FRANÇAIS ETUDE DE TERRAIN A DAMAS ET A L'UNIVERSITE LUMIERE LYON Ward HASSAN Sous la direction de M J 0 0
Duras Marguerite Duras est aujourd ? hui reconnue comme un des auteurs majeurs du e siècle Elle est née en Indochine française et la vie di ?cile qu ? elle y connait nourrira plusieurs de ses livres Son écriture demeure très particulière voire inclassable 0 0
  • 32
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Aucune attribution requise
Partager