Ce document (ici l'original) a été remis en page et modifié à partir de celui écrit par Jean Marc FEDOU.

Vocabulaire

Soit A un alphabet. On note A* l'ensemble des mots sur l'alphabet A, c'est à dire l'ensemble des suites finies (éventuellement avec répétition) formées à partir des lettres de A.
Ex. Le mot 010010 est un mot de {0,1}*.
L'ensemble A* est muni de l'opération de concaténation ".", qui lui confère une structure de monoïde (c'est à dire un " groupe sans inverse"), dont l'élément neutre est noté . Attention la concaténation n'est pas une opération commutative.
• Si a est une lettre de A et w un mot de A*, on note |w|a le nombre de lettres "a" apparaissant dans le mot w. Le nombre total de lettres de w est noté |w|.
• On appelle préfixe (resp. suffixe ) d'un mot w tout mot u tel qu'il existe un mot v tel que w u.v (resp v.u). On appelle facteur d'un mot w tout mot u tel qu'il existe des mots v et v' tels que w=vuv'. On appelle sous mot d'un mot w= w1.w2....wn tout mot u=wi1.wi2...wik avec i1<i2<...<ik.
• Un langage sur l'alphabet A est une partie de A*, c'est à dire une partie (finie ou infinie) de mots.

Opérations définies sur les langages
• Union +
• Intersection
• Concaténation .
• Etoile *
• Exemples de langage :
• Expressions arithmétiques
• Langage de Dyck ou parenthésages bien formés.
• Langage de Motzkin

Langages rationnels

• Définition. La classe des langages rationnels sur un alphabet A est la plus petite classe qui a les propriétés suivantes
• Le langage réduit au mot vide est rationnel
• pour chaque lettre a de l'alphabet A, le langage {a} est rationnel
• Si L et L' sont deux langages rationnels, alors il en est de même pour
• L+L',
• LL' et
• L*
• Expressions rationnelles. On définit les expressions rationnelles sur un alphabet A par
• ø est une expression rationnelle
• une lettre a de l'alphabet A est une exprssion rationnelle
• Si E est une expression rationnelle, E* l'est aussi
• Si E et E' sont deux expressions rationnelles, alors il en est de même pour
• E+E' et
• E.E'

• Exemples.
• a(a+b)*b est le langage rationnel des mots commençant par a et finissant par b.
• (a*)(a(a*)b)* est le langage rationnel des mots commençant par a et finissant par b qui ne contiennent pas plusieurs b consécutifs.
• (1+a)(ba)*(1+b) est le langage des mots ne contenat ni 2 a consécutifs ni 2 b consécutifs.

 
• Langages non rationnels : Lemme de l'étoile

On démontrera en utilisant les automates le théorème suivant

Théorème. Soit L un langage rationnel Il existe un entier n tel que tout mot de L de longueur >=n peut s'écrire sous la forme uxv de façon que l'on ait les propriétés suivantes

• |ux| <=n
• x différent du mot vide
• u(x)* v est inclus dans L.
• Application : le langage {a^n b^n, n>=0} n'est pas rationnel.

Automates

• Exemple

• Définition

Un automate est défini par
• Un alphabet fini A
• Un ensemble fini non vide d'états E
• Un fonction de transition, qui est une application t de ExA dans E.
• Un état initial e0
• Un ou plusieurs états finaux.
• Exemple. Décrire l'automate ci dessous. On remarque que pour s'accorder avec la définition, on doit créer un nouvel état, nommé puit pour compléter l'automate présenté sur la figure précédente. L'automate complet est donc,

 
• Mots reconnus par un automate

Etant donné un automate, on dit qu'un mot w=x1...xn est reconnu par l'automate lorsqu'il existe une suite q0,q1,... qn,q(n+1) d'états telle que

• q0 soit l'état initial
• pour tout i de 0.n on ait t(qi,xi)=q(i+1)
• q(n+1) soit un état final
• Automates non déterministes. Ce sont les automates où plusieurs flèches étiquetées par une même lettre peuvent être issues d'un même état. Il ne s'agit plus d'une fonction de transition.

On montre que pour tout automate non déterministe, il existe un automate déterministe équivalent (c'est à dire qui reconnait le même langage). Par exemple, l'automate ci dessous est équivalent à l'automate du premier exemple.

---

Automates et langages rationnels

Pour montrer qu'un langage rationnl est reconnu par un automate, on réalise une preuve par induction. On utilise l'équivalence des automates non dterministes et déterministes et on décrit successivement l'union, le produit et l'étoile d'automates.

• Somme de deux automates

• Produit de deux automates

• Etoile d'un automate

La réciproque se fait par la description d'un algorithme premant en entrée un automate et retournant une expression rationnelle.

---

Compléments

• Définitions inductives de langages rationnels

On peut définir un langage rationnel de manière inductive. On utilise souvent une notation équationnelle.

• Par exemple L=1+aL+bbL est l'ensemble des mots (dits de Fibonacci, pourquoi ?) dont les suites de b consécutifs sont de longueurs paires. La définition inductive de ce langage est
• B={1}
• E={w->aw,w->bbw}
• Dans ces définitions, on peut avoir des définitions mutuellement récursives comme dans
• L=1+aL+bL (l'ensemble A*)
• M=aLb (l'ensemble des mots commençant par a et finissant par b.
• Langages algébriques

De cette manière, on définir d'autres types de langage par induction

• L=1+aLb (l'ensemble des mots du type a^n b^n)
• D=1+aDbD (les mots de parenhèses bien formés ou langage de Dyck)

D'une manière plus formelle, un langage algébrique est la donnée de :

• Un alphabet A (ce sont les lettres à partir desquelles les mots du langage sont formées). Cet alphabet est appelé terminal.
• Un alphabet S de variables (appelé non terminal)
• Un ensemble de rêgles de productions ou de rêgles de réécriture de la forme s->w ou w est un mot de (A+S)*
• Une variable particuliere s0 appelée axiome ou variable initiale.
• Pour L=1+aLb, on a
• A={a,b}
• S={L}
• {L->1,L->aLb}
• s0=L
• Pour D=1+aDbD, on a
• A={a,b}
• S={D}
• {D->1,D->aDbD}
• s0=D

On dit qu'un mot v de (A+S)* dérive d'un mot u de (A+S)* lorsque le mot v est obtenu par réécriture de u en remplaçant l'une de ses lettres de S à l'aide d'une rêgle de dérivation. On note alors u -> v.

• On a par exemple, pour le langage de Dyck cité plus haut, les dérivations suivantes,
• aDabbDa -> aDabbaDba
• a DabbDa -> aDabba
• aDabbDa -> aaDbabbDa
• aDabbDa -> aabbaDba

L'ensemble des mots que l'on peut obtenir par dérivation à partir de l'axiome et appelé langage engendré par la grammaire. On remarque alors que tout mot engendré est représentable par son arbre de dérivarion, c'est à dire par l'abre des appels successifs aux réécritures qui ont servies à le construire.

• Le mot de Dyck aabbab est engendré par la suite de dérivations

D->aDbD->aaDbDbD->aabDbD->aabbD->aabbaDbD->aabbabD->aabbab
• L'arbre de dérivation associé au mot aabbab est l'arbre

 
• Les expressions arithmétiques sont engendrées par la grammaire

S = a + b + c + "+SS" + "*SS "+ "+S "+ "-S"
-(++b-(-ac)) est l'expression associée à -((+b)+(-(a-c))).
• Langages rationneles et langages algébriques

Théorème. Tout langage rationnel est algébrique.

 
 
• Automates à piles

On montre que les langages algébriques sont les langages reconnus par les automates à pile.

Une pile est ne structure de donnée caractérisée par ses fonctionnalités

• PileVide
• Empiler(x)
• Dépiler

Un automate à pile est un automate où chaque transition est associée à une opération sur la pile et ou la condition d'arrêt est le test de pile vide.

 
• Applications de la théorie des langages : analyse syntaxique.

Tout langage de programmation contient un langage algébrique sous jacent.

• Une variable est une lettre (parmi a..Z) suivie d'un mot sur (a..Z0..9)
• Toute parenthèse, accolade ou crochet ouvrant correpond à une unique parenthèse, accolade ou crochet fermant (mot de Dyck sous-jacent).
• Structure des boucles : if ... then ... else
• ...