Grammaires transformationnelles
Dans cet exemple, on ne va pour une fois pas regarder les mots comme concaténation de lettres, mais les phrases comme concaténation de mots (la concaténation étant représentée par le caractère "espace"). On part d’un axiome (ou gabarit de phrase) que voici :
SUJET VERBE COMPLÉMENT.
Pour transformer ce gabarit en phrase, on effectue des transformations comme
- SUJET -> ARTICLE NOM ADJECTIF
- SUJET -> ARTICLE NOM ADJECTIF PROPOSITION
- VERBE -> poursuit
- COMPLÉMENT -> ARTICLE NOM ADJECTIF
- COMPLÉMENT -> ARTICLE NOM ADJECTIF PROPOSITION
La règle du milieu est différente des autres en ce qu’elle remplace le mot "VERBE" par un verbe, qui ne pourra plus être transformé par la suite. On dit que le mot "poursuit" appartient au vocabulaire terminal, des mots comme "VERBE" et "PROPOSITION" étant considérés comme non terminaux. Pour l’instant la phrase devient
ARTICLE NOM ADJECTIF PROPOSITION poursuit ARTICLE ADJECTIF PROPOSITION.
Après ça d’autres transformations peuvent être appliquées aux nouveaux mots non terminaux qui sont apparus ci-dessus, comme celles-ci :
- ARTICLE -> Une
- ARTICLE -> le
- NOM -> chat
- NOM -> souris
- ADJECTIF -> rose
- ADJECTIF -> verte
- PROPOSITION -> PRONOM VERBE COMPLÉMENT
- PROPOSITION -> PRONOM SUJET VERBE COMPLÉMENT
À ce stade, la phrase en construction devient
Une souris verte qui VERBE COMPLÉMENT poursuit le chat rose que SUJET VERBE COMPLÉMENT.
On voit que les propositions subordonnées font intervenir la récursivité, et d’autres transformations analogues permettent d’arriver successivement à ceci :
Une souris verte qui courait dans ARTICLE NOM poursuit le chat rose que des fous en blouse blanche ont, lui aussi, conçu dans un laboratoire sur lequel VERBE COMPLÉMENT.
puis
Une souris verte qui courait dans l’herbe poursuit le chat rose que des fous en blouse blanche ont, lui aussi, conçu dans un laboratoire sur lequel on a cloué une pancarte portant l’écriture "Ici on fabrique des mammifères transgéniques".
(Sémantiquement parlant, l’exemple ci-dessus n’est pas de la science-fiction, comme le montre l’exemple que voici)
Retour aux lettres concaténées pour former des mots : Au vocabulaire $V=\left\{a,b,c,...\right\}$ on joint un vocabulaire non terminal $U=\left\{X,Y,Z,...\right\}$ (l’usage est de représenter par des minuscules les lettres terminales et par des majuscules les lettres non terminales). On considère des règles de dérivation du style $X\rightarrow abacYaXZ$ (on transforme une lettre non terminale en mot comprenant éventuellement aussi des lettres non terminales) et un axiome, en général noté X (une lettre non terminale).
Alors l’ensemble des mots terminaux obtenus par ces dérivations est un langage, dit engendré par la grammaire transformationnelle.
L’utilisation de mots tels que dérivation et axiome suggère que l’activité consistant à démontrer des théorèmes, revient à engendrer un langage (l’ensemble des théorèmes). C’est effectivement le cas : Démontrer c’est réécrire (sauf que là il y a plusieurs axiomes).
Équivalence
On appelle linéaire un langage pour lequel les règles de transformation sont toutes de la forme
- X -> aY
- X -> a
où a est une lettre terminale, et X et Y des lettres non terminales. Un langage linéaire est donc un langage qui se construit de gauche à droite (sans tenir compte du contexte). L’adjectif linéaire est aussi lié au fait que les langages linéaires sont de la forme $\varphi^{-1}(M)$ où $M$ est un monoïde, et $\varphi$ un morphisme de monoïdes (donc quelque chose de linéaire).
Un automate fini est un graphe dont les nœuds sont les états du graphe, et les arêtes représentent les changements d’état de l’automate. Chaque changement d’état a lieu lors de la lecture d’une lettre. Un automate fini n’a qu’un seul état initial, et un ou plusieurs états finaux.
On dit que l’automate lit un mot si, mis dans son état initial, l’automate lit, une à une, de gauche à droite, les lettres du mot, en suivant les arêtes du graphe pour changer d’état.
On dit qu’un mot est reconnu ou accepté par l’automate si, après avoir lu le mot, l’automate est dans un de ses états finaux (ou accepteurs).
| Un langage est dit régulier s’il existe un automate fini reconnaissant les mots de ce langage et uniquement ceux-là. |
Des exemples sont visibles (avec leurs automates) dans les onglets suivants. Les automates y sont simulés avec le logiciel DFA Simulator.
Un langage rationnel est un langage engendré à partir de langages finis par un nombre fini de répétitions des constructions suivantes :
- $A.B$ qui est l’ensemble des concaténés des éléments de $A$ et de ceux de $B$ ;
- $A|B$ qui est la réunion $A \cup B$ de $A$ et de $B$ (Kleene note la réunion par le trait vertical de la disjonction logique, ce qui est logique) ;
- $A^*$ qui est l’ensemble des mots obtenus par concaténation d’un choix quelconque d’éléments de $A$.
Les langages rationnels (pour savoir pourquoi on les appelle comme ça, voir l’onglet "fractions") peuvent aussi être décrits par les propriétés qu’un mot doit vérifier pour appartenir à un tel langage ; ces propriétés sont décrites par des expressions rationnelles ou expressions régulières, en abrégé RegExp. De bons logiciels pour manipuler les RegExp sont Kodos et Kiki, écrits en Python (langage).
En effet les définitions des langages linéaire, régulier, rationnel ou reconnu par un monoïde (de la forme $\varphi^{-1}(M)$) sont équivalentes, et désignent donc le même genre de langages.
Dans les autres onglets, on va voir des exemples, définis de différentes manières (grammaire transformationnelle, automate fini, RegExp), à fin de comparaison entre les différentes manières de décrire ces langages.
Commentaires