Grammaires, automates et langages formels

Ce chapitre aborde quelques concepts de base sur les grammaires, les automates et les langages formelsqui sont en lien avec les concepts et représentations des grammaires locales et des grammaires locales étendues étudiées à partir des chapitres 3 et 4 de la thèse. En plus des notions préliminaires disponibles dans l’annexe A, nous introduisons succinctement les concepts des grammaires formelles, des langages réguliers et des automates finis, des langages non contextuels et des automates à pile, des langages contextuels ainsi que des langages sans restriction et des Machines de Turing.

Grammaires formelles

Une grammaire formelle est un formalisme pour décrire un langage (cf. défini- tion A.34). Cette description permet à la fois de définir, générer et reconnaître ce langage. Nous donnons une définition plus formelle ci-après.Une grammaire formelle G, dorénavant grammaire ou G, est alors un système fini composé d’un ensemble disjoint de symboles de V et de T , ou V ∪ T constitue le vocabulaire de la grammaire, noté Σ, d’un ensemble fini P de règles de réécriture, ou simplement règles, et d’un seul symbole initial S ∈ V . Les règles de P constituent l’élément central de la définition de toute grammaire et sont de la forme :

} permet ainsi, par leur application successive, de réécrire des suites de mots à partir d’autres suites. Selon la façon dont r peut se dériver de l, soit sous forme directe, ou bien sous forme indirecte, on parle d’une dérivation directe ou simplement d’une dérivation.Définition 2.5 (Phrase). Un mot w est appelé une phrase de G s’il est une forme sen- tencielle de G constituée uniquement de symboles terminaux (zéro ou plus), autrement dit, elle se définit comme tout mot w ∈ T=⇒ w). En revanche, dans une grammaire de reconnaissance les règles sont inversées et de la forme r → l, de sorte qu’une phrase est analysée en effectuant la substitution par les symboles qui se trouvaient initialement à gauche et en répétant ce processus jusqu’à atteindre l’axiome de la grammaire (w=⇒ S). Bien que l’ensemble des règles d’une grammaire puisse avoir la forme r → l, dite de composition, ou l → r, dite de décomposition, il est utile de remarquer que la grammaire définit toujours le même langage.

Notation 2.12 (Arbre de dérivation). Étant donnée une grammaire quelconque, le processus de dérivation d’une phrase peut être visualisé plus facilement à l’aide d’une notation arborescente. Il s’agit de construire un arbre où la racine coïncide avec l’axiome de la grammaire (S), les nœuds avec les variables (V ) et les feuilles avec les symboles de la phrase (T ). Ce type de représentation est connu sous le nom d’arbre de dérivation ou arbre syntaxique du fait qu’il représente la structure syntaxique d’une phrase engendrée par une grammaire.

Automates finis

Les automates finis sont des machines abstraites qui vérifient sous forme séquentielle si un mot, passé en entrée, appartient ou non à un langage donné. Ces automates sont dits finis car restreints à un ensemble fini d’états qui mémorisent des informations. Les automates finis ont trouvé des applications directes dans plusieurs domaines qui vont de l’analyse lexicale de langues artificielles et naturelles, en passant par la compression de l’information, la recherche de motifs dans un texte, ou la vérification de systèmes, tel que des circuits électroniques, dotés d’un nombre fini d’états.

Chaque transition est définie comme un triplet (p, σ, q) de Q × Σ × Q (l’ensemble de transitions) où : p est l’état de départ, σ est un symbole de l’alphabet, et q est l’état d’arrivée. Si A a une transition étiquetée par un symbole σ qui relie p à q, ceci indique que lorsque l’automate est dans l’état p et lit σ, il passe à l’état q. Cette règle de transition est notée : δ(p, σ) = q. Considérons l’exemple 2.17 :

Un automate fini peut être représenté graphiquement par un diagramme d’états- transitions comme celui de la figure 2.2. L’état initial, conventionnellement le premier à gauche, est distingué par un arc orienté vers un nœud aux contours en gras. Les états finaux sont indiqués par des nœuds avec double cercle. Les transitions sont des arcs orientés allant d’un nœud de départ vers un nœud d’arrivée. Les étiquettes des transitions se placent sur les arcs. Lorsque un automate a plusieurs transitions). En outre, remarquons qu’un automate fini peut accepter plusieurs mots, mais il reconnaît toujours un seul langage. L’inverse n’est pas vrai, pour un langage donné, il peut exister plusieurs automates qui le reconnaissent.