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 Introduction On va dans cet exposé co

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 finis est un quintuplet M = (V, Q, q0, 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 = {q0, q1, q2, q3} q0 est l'état initial F est l'ensemble des états accepteurs par exemple F = {q1, q2, q3} Λ est l'ensemble des transitions par exemple Λ = {(q0, je, q0), (q0, nous, q0), (q0, précis, q1), (q1, er, q2), (q2, ai, q3), (q3, s, q2), (q1, ion, q3)} 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 final. 1 Exemple illustrant la définition 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 λ = {(q1, er, q2)} Les transitions peuvent être entre autres de nature: -Réflexive, lorsqu'une boucle relie un état à lui-même. Par exemple λ = {(q0, je, q0), (q0, nous, q0)} -Transitive, lorsqu'il est possible de sauter des états liés entre eux. Par exemple λ = {(q1, er, q2), (q2, ai, q3), (q1, ion, q3)} -Symétrique, lorsque on peut faire un va et vient entre deux états consécutifs. λ = {(q3, s, q1), (q1, ion, q3)} -Cyclique, lorsqu'après avoir parcouru un certain nombre d'états on revient au point de départ. λ = {(q0, je, q0); (q3, s, q1), (q1, ion, q3)} 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 q1 et q2. -Non déterministe, lorsque plusieurs lectures sont possibles pour chaque symbole. Par exemple si pour lire "er" on avait le choix entre passer par q1 et q2, ou passer par q1 et q4. 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 longueur des mots. 0 mots de longueur 1, 2, 3, 4, 5, 7 1 mot de longueur 6 1 mot de longueur 8 1 mot de longueur 9 etc... 2 II- Qu'est-ce qu'un arbre ? Un arbre peut servir tout comme le lexique de donnée d'entrée d'un programme informatique comme Prolog (Par exemple: SWI-Prolog a SQL et est également disponible dans les packages de cygwin). Il représente l'analyse syntaxique que nous locuteurs avons décidé d'entrer après une longue réflexion. Un arbre doit pouvoir couvrir un grand nombre d'énoncés possibles, les catégories grammaticales d'un arbre doivent donc être les plus générales possible. Remarque: Pour un linguiste, il vaut mieux que l'arbre soit une donnée d'entrée sinon il ne pourra pas avoir de prise sur la grammaire qu'il utilise. Dans un arbre il y a toujours une racine, une catégorie initiale, c'est presque toujours la phrase noté S pour sentence (angl = phrase). Des catégories grammaticales en relation de hiérarchie, la catégorie du haut inclue celle du bas et celle du bas dépend de celle du haut, et on applique les règles de gauche à droite. Des constituants immédiats qui dans les grammaires hors contexte peuvent être soit le point de départ de l'analyse syntaxique soit le point d'arrivée. Le lexique de ces constituants immédiats est appelé vocabulaire terminal, et correspond aux feuilles de l'arbre. On n'est pas obligé de le représenter dans les arbres syntagmatiques, car ces arbres doivent pouvoir générer un plus grand nombre de phrases que celles de nos exemples. Des inconvénients: les mots en deux morceaux comme ne...pas ne peuvent pas être réunis en une seule catégorie car deux arcs d'un arbre ne se recoupent jamais. Des méthodes: pour décider comment on va regrouper les constituants immédiats en catégories grammaticales, on utilise la méthode de commutation qui consiste à remplacer un groupe d'éléments par un autre, et pour décider quelles sont les catégories grammaticales que l'on va définir, on utilise le critère de grammaticalité qui consiste à comparer deux phrases dont la structure grammaticale est identique. Ex 1: Le chat mange. Le chien mange. La souris court. Ex 2: Le chat va dans la cuisine. *Le chat va. Une unité des conventions et de l'analyse: S = Phrase. SN = Syntagme nominal. SV = Syntagme verbal. A = Adjectif. V = Verbe. B = Adverbe (Cette convention peut être changée). 3 SA = Syntagme adjectival SB = Syntagme adverbial. SP = Syntagme prépositionnel. P = Préposition. S → SN SV SN → D N SV → V GN SP → P GN SA → B A SB → B B III- Quel est le point commun entre un automate et un arbre ? On peut définir les automates et les arbres par la théorie des graphes où les noeuds correspondent aux états des automates ou aux catégories grammaticales des arbres syntagmatiques, et où les arcs correspondent aux transitions des automates ou aux relations de dépendance des arbres. Un automate est un graphe orienté qui a une racine et qui est connexe et un arbre syntagmatique est un graphe orienté qui a une racine et qui est acyclique et projectif et ordonné et connexe. Graphe = il y a des noeuds et des arcs Orienté = il y a un sens de lecture Une racine = un état initial Acyclique = il n'y a pas de cycle Projectif = deux arcs ne se recoupent jamais Ordonné = il y a une hiérarchie Connexe = chaque noeud est relié à un autre IV- Qu'est-ce qui distingue les arbres des automates ? On ne peut pas concevoir un automate qui génère le langage d'un arbre syntaxique mais on peut concevoir un arbre syntaxique qui génère le langage d'un automate. Donc un arbre représente mieux le langage humain écrit qu'un automate car on a plus de liberté d'expression. Avec un automate on ne peut pas: -Inclure des catégories grammaticales à l'intérieur d'autres catégories grammaticales car on ne fait pas la distinction entre symbole terminal et symbole non terminal, i.e. entre le vocabulaire et la catégorie grammaticale. 4 Par exemple on ne peut pas représenter une simple règle de récursivité: SN → D + N -Illustrer le phénomène de récursivité qui consiste à donner à un syntagme la possibilité de pouvoir se dominer un nombre infini de fois à l'intérieur d'une phrase. Par exemple on ne peut pas représenter des syntagmes prépositionnels emboîtés: SN → D + N + SP SP → P + SN La fille du fils du frère de mon arrière-grand-père de la ville des lumières. -Illustrer le phénomène d'enchâssement qui consiste à donner à une phrase la possibilité de pouvoir se dominer un nombre infini de fois à l'intérieur d'une autre phrase. Par exemple on ne peut pas représenter les complétives: S → GN GV GV → V S' S' → Conj S Je pense que tu penses que il pense que tout le monde pense qu'il ne neigera plus en antarctique. Ni les relatives: S → GN GV | GN S' GN → GN S' | Σ S' → Pron S Le livre qui est gris qui est sur la table que tu m'avais apporté que tu voulais que je lise, je l'ai feuilleté. Par contre on peut représenter un automate avec une règle de réécriture en donnant un nom à chaque état et en écrivant chaque symbole lu devant le nom de l'état. Exemple: V ={a, b} Cat ={U, V, W} q0 = U Règles de réécriture Expression régulière U → aV V → bU | bW W → Σ L = {ab}*.b 5 V- Quel est le point commun entre une une expression régulière et une règle de réécriture? Ce sont tous des langages formels car à partir d'un vocaulaire fini, on produit un nombre fini ou infini de mots. Et de même à partir d'un nombre de mots fini, on produit un nombre fini ou infini de phrases. Mais pour simplifier ce qu'on dit, on peut uploads/Litterature/ comparaison-entre-un-automate-et-un-arbre 1 .pdf