Théorie des langages

I/ Automates

1) Exemple

Voici une machine dotée de deux boutons a et b et de trois LEDs numérotées 0, 1 et 2. Une seule LED est allumée à la fois, elle indique l'état interne de la machine. La machine a donc 3 états. L'état 0 est l'état initial de la machine.


0	1	2

Le mot écrit jusqu'ici est :

Chaque appui sur un bouton induit (ou pas) un changement d'état de l'automate. Donc chaque mot (écrit dans l'alphabet {a,b}) détermine un état de l'automate, obtenu en entrant une après l'autre les lettres du mot. Par exemple le mot baabab donne l'état final 1.

2) États finaux

Le mot baba aussi donne 1 comme état final de l'automate (en partant de l'état initial 0). L'ensemble des mots aboutissant à l'état final 1 est un exemple de langage régulier. Comme il a trois états, l'automate ci-dessus définit 7 langages réguliers :

L'ensemble des mots qui aboutissent à l'état final 0
l'ensemble des mots qui aboutissent à l'état final 1
l'ensemble des mots qui aboutissent à l'état final 2
l'ensemble des mots qui aboutissent à l'un des états finaux 0 ou 1
l'ensemble des mots qui aboutissent à l'un des états finaux 0 ou 2
l'ensemble des mots qui aboutissent à l'un des états finaux 1 ou 2
l'ensemble des mots qui aboutissent à l'un des états finaux 0, 1 ou 2

Ce dernier langage est l'ensemble de tous les mots sur l'alphabet {a,b}. On le note {a,b}*.

3) Graphe

On peut représenter un automate par un graphe orienté dont les arcs sont étiquetés par des lettres de l'alphabet et les sommets représentent les états de l'automate. Voici un exemple (alphabet {a,b}, états 0, 1, 2 et 3) :

L'état initial (0) est codé par un arc venant d'un sommet vide et chaque état final (ici il n'y en a qu'un qui est 3) est représenté par un double cercle.

Pour utiliser l'automate pour la lecture du mot babab, on place un pion sur l'état initial puis on déplace le pion en lisant les lettres du mot babab une après l'autre. Avant de lire la première lettre, le pion est sur l'état initial :

Comme la première lettre est un b, le pion suit l'arc étiqueté b :

La seconde lettre est un a donc le pion suit la boucle étiquetée a et revient sur le même sommet :

Mais la lettre suivante étant un b; le pion reprend son mouvement :

L'avant dernière lettre étant un a, le pion suit la boucle en bas à droite et il n'y a pas de changement d'état :

La dernière lettre étant un b, le pion effectue un dernier mouvement :

Le pion étant arrivé, à la fin de la lecture du mot, sur l'état final, le mot babab est reconnu par l'automate.

II/ Expressions régulières

1) Définition

On note ∅ le langage ne contenant aucun mot, et ε le langage ne contenant que le mot vide (qui ne comprend aucune lettre ce mot est élément neutre pour la concaténation).

Un langage régulier est obtenu en appliquant à des langages finis les opérations suivantes :

La réunion, notée par un trait vertical L|M
La concaténation, notée LM
L'étoile de Kleene, notée L* et définie par L*=ε|L|L²|L³|...

Par exemple l'ensemble des mots binaires (sur l'alphabet {a,b}) comprenant une seule fois la lettre b est un langage régulier. Il est décrit par l'expression a*ba*. On le vérifie avec grep :

♟️ echo aabaaa | grep -x a*ba*
aabaaa

L'ensemble des mots binaires comprenant exactement 2 fois la lettre b est aussi régulier, il est décrit par l'expression régulière a*ba*ba* :

♟️ echo aabaaba | grep -x a*ba*ba*
aabaaba

L'ensemble des mots binaires comprenant exactement trois fois la lettre b est aussi un langage régulier, il est décrit par l'expression régulière a*ba*ba*ba* :

♟️ echo babab | grep -x a*ba*ba*ba*
babab
♟️ echo abba | grep -x a*ba*ba*ba*
♟️

Le langage formé par les mots binaires dont le nombre d'occurences de la lettre b est divisible par 3 est aussi un langage régulier : il est décrit par l'expression régulière (a*ba*ba*ba*)*.

Théorème (Kleene 1951) : un langage est régulier si et si seulement il existe un automate à nombre fini d'états le reconnaissant.

Dans la suite, on va voir comment on peut passer de l'expression régulière à l'automate et vice versa.

2) Algorithme de Brzozowski-McCluskey

L'idée est de réduire l'automate en remplaçant les lettres par des expressions régulières pour supprimer tous les sommets jusqu'à ce qu'il ne reste plus que l'état initial. Par exemple, on voudrait trouver l'expression régulière correspondant à cet automate :

Dans un premier temps, comme chaque boucle peut être parcourue aussi souvent que l'on veut (voire pas du tout), l'automate suivant reconnaît exactement le même langage :

Ensuite, on constate que pour aller de droite à gauche, il faut

le chiffre 1 pour aller en bas),
un certain nombre de fois (voire pas du tout) le chiffre 0 (pour rester en bas donc avec 0*),
et un dernier chiffre 1 pour aller depuis en bas vers l'état final.

Par conséquent le passage par l'état d'en bas peut être décrit par l'expression régulière 10*1 :

Mais maintenant on a deux moyens pour aller à l'état final :

la boucle 0* en haut à gauche,
le détour par la droite
- en allant à droite avec 1,
- en restant un peu à droite avec 0*,
- en revenant à gauche avec 10*1,
donc en résumé en faisant l'aller-retour par la droite avec 10*10*1 :

Mais la boucle du bas peut être parcourue aussi souvent que l'on veut (voire pas du tout) donc l'automate suivant reconnaît le même langage que chacun des automates précédents :

Comme chacune des boucles est une étoile, on peut la parcourir autant de fois que l'on veut et l'automate suivant reconnaît aussi le même langage :

L'automate ci-dessus n'ayant qu'une seule boucle, celle-ci porte une expression régulière qui est celle du langage étudié : (0*(10*10*1)*)*.

Remarque : il existe un algorithme plus rapide, dû à John Conway, et basé sur la méthode « diviser pour régner ».

3) Algorithme de Berry-Sethi

On a vu plus haut que le langage formé par les mots binaires dont le nombre d'occurences du chiffre 1 est divisible par 3 est un langage régulier, décrit par l'expression régulière (0*10*10*10*)*. L'algorithme ci-dessous, décrit par Gérard Berry et Ravi Sethi en 1986, permet de construire un automate à partir de l'expression régulière, appelé automate de Glushkov en hommage à un chercheur soviétique l'ayant décrit dans les années 1960.

On commence par linéariser l'expression régulière, ce qui veut dire renommer les lettres pour que chacune n'apparaisse qu'une fois. De (0*10*10*10*)* on passe alors à (a*bc*de*fg*)* (en mémorisant le lien entre chaque nouvelle lettre et le chiffre d'où elle vient : a représente 0, b représente 1 etc),
On représente cette nouvelle expression régulière par un automate où chaque étoile est une boucle allant d'un état à lui-même et les autres lettres joignent les états successifs :
L'automate ci-dessus représente l'expression régulière a*bc*de*fg*. Pour représenter l'expression (a*bc*de*fg*)* on recolle l'état final sur l'état initial :
Enfin on remplace à nouveau la lettre a par 0, la lettre b par 1 etc pour obtenir l'automate de Glushkov :

On reconnaît l'automate vu avant et pour lequel on avait trouvé l'expression régulière (0*(10*10*1)*)*. On en déduit que les expressions régulières (0*10*10*10*)* et (0*(10*10*1)*)* décrivent le même langage.

Le logiciel grep fonctionne ainsi : à partir de l'expression régulière qu'on lui fournit, il fabrique l'automate de Glushkov, puis soumet à cet automate le texte à étudier et regarde quelles sont les parties du texte pour lesquelles le pion est dans un état final.

4) Lemme de l'étoile

La longueur d'un mot est le nombre de lettres (ou de caractères) qu'il contient. Seul le mot vide a pour longueur 0.

Lemme (Bar-Hillel, Perles, Shamir 1961) : Si un mot `m` appartient à un langage régulier `L` dont l'automate de Glushkov comprend moins d'états que la longueur de `m`, alors il existe trois mots `u`, `v` et `w` tels que `m=uvw`, la longueur de `uv` est inférieure ou égale au nombre d'états de l'automate de Glushkov et tous les mots de la forme `uvⁿw` sont dans `L`.

On note uv*w ⊂ L la dernière propriété.

Preuve du lemme : comme m a plus de lettres que l'automate a d'états, il y a forcément un état qui est visité deux fois. Il en résulte que l'automate de Glushkov comporte une boucle. Cette boucle reconnaît le mot v cqfd.

Le lemme de l'étoile sert surtout à prouver qu'un langage n'est pas régulier. Par exemple html permet d'écrire des exposants imbriqués comme dans 2^{2^2²} = 65536. Pour cela on utilise la balise sup de html et on ouvre 4 fois puis on referme 4 fois la balise. En notant o une ouverture de balise et f une fermeture de balise, l'expression ci-dessus se résume ooooffff. Or le langage des mots de la forme oⁿfⁿ n'est pas régulier. On montre cela par l'absurde : si le langage était régulier, il serait reconnu par un automate ayant n états. On pourrait alors appliquer le lemme de l'étoile avec le mot oⁿfⁿ où n est le nombre d'états de l'automate en question. Il existerait alors trois mots u, v et w tels que

oⁿfⁿ = uvw
la longueur de uv est inférieure à n,
tous les mots de uv*w sont de la forme o^kf^k

Or comme uv est un préfixe de oⁿfⁿ, il n'y a que la lettre o dans uv (dont la longueur est inférieure à n). Il y aurait alors une infinité de mots de o* dans le langage considéré. Cette contradiction prouve que le langage n'est pas régulier. On en déduit que

html n'est pas un langage régulier.

III/ Recherche de motifs

Dans cette partie, le motif que l'on cherche dans un texte n'est pas une expression régulière mais un facteur (sous-mot).

1) Algorithme de Knuth-Morris-Pratt

Un amateur de rock suédois aimerait savoir si son groupe préféré est cité quelque part sur un site web. Pour cela il compare les lettres du texte (supposé, pour simplifier, écrit dans l'alphabet {a,b}) avec celles du motif et en cas d'échec il recommence toutes les comparaisons à la lettre suivante du texte :

Mais dans le pire cas, le nombre de comparaisons de lettres est le produit des longueurs du motif et du texte. L'algorithme de Knuth-Morris-Pratt est plus rapide car il mémorise les comparaisons déjà effectuées :

Cet automate a été construit en regardant les suffixes des mots engendrés qui sont des préfixes (et même les plus grands possibles) du motif. Le motif étant abba, ses préfixes sont {ε,a,ab,abb,abba}. Par exemple si on arrive à ab, il y a deux possibilités comme nouveau mot :

aba qui n'est pas un préfixe de abba, et son suffixe ba non plus. Mais le suffixe a est un préfixe de abba donc on le relie (par la lettre a) à ab,
abb qui est un préfixe de abba.

ce qui définit deux arcs de l'automate : de ab vers a avec l'étiquette a, et de ab vers abb avec l'étiquette b.

2) Algorithme de Rabin-Karp

L'algorithme de Rabin-Karp ne compare pas les lettres du motif et celles du texte, mais leurs images par une fonction de hashage (« empreintes »). Il y a risque de collision et cet algorithme n'est efficace que si la fonction de hashage est plus rapide à calculer que les comparaisons lettre à lettre. Typiquement on l'utilise plutôt lorsque le motif est de grande taille.

IV/ Langages algébriques

1) Grammaires transformationnelles

On considère un nouvel alphabet, dit non terminal (l'ancien étant formé de lettres terminales) et dont les lettres sont conventionnellement écrites en majuscules. Les lettres non terminales sont destinées à être réécrites. L'idée remonte au logicien Emil Post qui utilise donc le vocabulaire et les notations de la logique. Ainsi les règles de réécriture s'appellent parfois règles de dérivation et le premier mot à partir duquel on réécrit (ou déduit, ou dérive) s'appelle axiome. Par exemple le langage {ε,of,ooff,ooofff,ooooffff,...} dont on a vu plus haut qu'il n'est pas régulier, peut s'obtenir en ajoutant un alphabet non terminal {A} à l'alphabet terminal {o,f}, et ces règles de dérivation :

règle 1 : A→ε
règle 2 : A→oAf

Par exemple, pour dériver le mot ooooffff, on part de l'axiome A, et on obtient successivement

⊢ A (axiome)
⊢ oAf (règle 2)
⊢ ooAff (règle 2)
⊢ oooAfff (règle 2)
⊢ ooooAffff (règle 2)
⊢ ooooffff (règle 1)

2) Analyse syntaxique

Comme on ne dispose pas d'automate pour vérifier si un mot écrit avec des lettres terminales (comme oofoffooff) peut être dérivé d'un axiome, on peut essayer de reconstituer une dérivation. Par exemple, la seule manière d'obtenir un of est d'utiliser la règle 1, donc oofoffooff peut venir de ooAfoAffooAff qui lui-même peut s'obtenir par la règle 2 à partir de oAAfoAf. Or oAAfoAf a pu s'obtenir avec la règle 2 à partir de oAAfA qui n'est pas un axiome : oofoffooff n'est pas dérivable dans ce système.

L'analyse syntaxique est une phase importante de la compilation que l'on effectue avant la compilation elle-même.

3) Langages réguliers

Un langage est régulier si et seulement si on peut l'obtenir avec des règles de dérivation dont les lettres non terminales sont toutes des suffixes.

Par exemple le langage (a*ba*ba*ba*)* des mots dont le nombre d'occurences de b est divisible par 3, peut se construire à partir de l'axiome Z avec ce système de réécriture :

Z→ε
Z→aZ
Z→bU
U→aU
U→bD
D→aD
D→bZ

On constate que l'alphabet non terminal {D,Z,U} est plus grand que l'alphabet terminal, et que chacune des lettres D, U et Z est à la fin des règles de dérivation. On a vu avec les automates (et grep) que le mot babab fait partie du langage. En voici une dérivation :

⊢ Z (axiome)
⊢ bU (règle 3)
⊢ baU (règle 4)
⊢ babD (règle 5)
⊢ babaD (règle 6)
⊢ bababZ (règle 7)
⊢ babab (règle 1)