Outils Mathématiques

Cours pour Ingénieur

Georges Edouard KOUAMOU
Motivation
• Besoin
• écrire des programmes sous une forme plus naturelle, dans laquelle les
éléments (fonctions, instructions, déclarations, expressions, etc) sont
combinés selon des règles précises
• Préoccupations
• comment écrire, à moindre frais, des compilateurs qui analysent le code
source, et génèrent sa traduction ?
• Inversement, peut-on identifier des familles de langages faciles à analyser ?
• Développements mathématiques
• Au delà de ces motivations pratiques, la théorie des langages s'intéresse aux
propriétés mathématiques des langages formels.

Cours de 3ème Année Ingénieur 2

Domaines d’application
• Reconnaissances des expressions régulières
• Automatiser la fabrication des compilateurs, en fournissant une
description du langage à reconnaitre à un méta-compilateur, qui
produira un compilateur.

Cours de 3ème Année Ingénieur 3

Positionnement
• L’informatique ne peut se réduire à la programmation. Elle ne peut pas non
plus se limiter au génie logiciel
• L’informatique est la résolution des problèmes (P).
• Les mathématiques sont au cœur de la résolution de problème (Q).
• PQR
• Donner la forme littérale de R
• Définir un problème nécessite bien souvent la rigueur des mathématiques
• Le bon usage et l’analyse des modèles, des structures de données et des
algorithmes nécessitent une base solide en mathématiques
• Edsger Dijkstra: « L’informatique n’est pas plus la science des ordinateurs
que l’astronomie n’est celle des télescopes »
Cours de 3ème Année Ingénieur 4
Sujets connexes
• Théorie des ensembles, Relations et fonctions:
− Vu en MSP
• Logique prépositionnelle
− Introduit en IA
− L’application à la conception des circuits: algèbre de Boole/architecture des
ordinateurs
• Science de l’information: fondements mathématiques de la sécurité
informatique
− Codage
− Cryptographie et chiffrements

Cours de 3ème Année Ingénieur 5

Contenu
• Mots et Langages
• Automates à états finis
• Automate fini non déterministe
• Automate fini déterministe
• Langages rationnels
• Expression rationnelle
• Langages rationnels
• Langage réguliers
• Notion de résiduel d’un langage
• Automate canonique (minimal)
• Grammaire algébrique et langages algébriques

Cours de 3ème Année Ingénieur 6

Chapitre 1
Mots et langages

Cours de 3ème Année Ingénieur 7

Définitions
• Définition (alphabet): Un alphabet est un ensemble fini non vide dont
les éléments sont appelés des lettres.
• Exemple
• B = {0, 1} l’alphabet binaire
• A = {a, b, c}
• L = {a · · · , z} l’alphabet français.
• Le biologiste interessé par l'étude de l'ADN utilisera un alphabet à quatre
lettres {A; C; G; T} pour les quatre constituants des gènes: Adénine, Cytosine,
Guanine et Thymine

Cours de 3ème Année Ingénieur 8

Mots
• Pour tout alphabet , on pose ∗ l’ensemble défini par:
Σ∗ = ራ Σ𝑛
𝑛≥0
∗
• Un élément de  est appelé un mot sur l’alphabet .
• Définition (mot vide): Le symbole ε dénote ce qu’on0 appelle le mot vide. Pour
tout ensemble A, on considère par convention que A = {ε}, l’ensemble contenant
uniquement le mot vide.
• Remarque: 𝜀 ≠ 𝜙
• Un mot est donc soit le mot vide, soit un n-uplet d’éléments de .
• Exemple
• u = (a, a, b, c, a) est un mot de {a, b, c}∗
• Par simplification, on va l’écrire u = aabca. C’est juste un changement d’écriture, les
propriétés des mots sont les mêmes que celles des n-uplets

Cours de 3ème Année Ingénieur 9

Définition des mots par recursion
• Terminologie
•  est le mot vide: “”
•  est l’ensemble des lettres : { a, b, c, …, z }
• Cet ensemble peut varier en function du problème
• Nous pouvons définir un ensemble de mots * comme il suit
• Etape de base:   *
• Si w  * et x  , alors wx  *
• Ainsi, * est l’ensemble des mots possibles qui peuvent être générés avec
l’alphabet
• Est-ce dénombrablement infini ou indénombrablement infini?

Cours de 3ème Année Ingénieur 10

Longueur d’un mot
• Définition (longueur): Soit u ∈ *. La longueur de u est l’unique l tel que u
∈ l. On note 𝑢 la longueur de u.
• Pour tout n ∈ N , on note  l’ensemble des mots de longueur n.
n

• Tout symbole (ou lettre) de l’alphabet  est un mot de longueur 1

• Le mot vide est le mot de longueur 0
• Théorème (égalité des mots):
• Deux mots 𝑢 = 𝑢1 … 𝑢𝑛 𝑒𝑡 𝑣 = 𝑣1 … 𝑣𝑚 sont égaux si et seulement si n = m et pour
tout i ∈ {1, . . . , n}, 𝑢𝑖 = 𝑣𝑖 .
• Définition (longueur en a): Pour toute lettre a ∈  et pour tout mot u∈
*, on note 𝑢 𝑎 la longueur en a de u, qui est le nombre d’occurrences de
la lettre a dans le mot u.
• Exercice: Donner la définition récursive de la longueur d’un mot.

Cours de 3ème Année Ingénieur 11

Longueur d’un mot par récurrence
• Définir récursivement la longueur d’un mot
• Cas de base: l() = 0
• Recurrence: l(wx) = l(w) + 1 si w  * and x  
• Exemple: l(“aaa”)
• l(“aaa”) = l(“aa”) + 1
• l(“aa”) = l(“a”) + 1
• l(“a”) = l(“”) + 1
• l(“”) = 0
• Resultat: 3

Cours de 3ème Année Ingénieur 12

Opérations sur les mots
• Concaténation
• Définition (concaténation): Soient 𝑢 = 𝑢1 𝑢2 … 𝑢𝑛 et v = 𝑣1 𝑣2 … 𝑣𝑚 deux mots sur l’alphabet
. On note 𝑢 ∙ 𝑣 (ou bien 𝑢𝑣) la concaténation de u et de v, qui est le mot de taille n + m
défini par : 𝑢𝑣 = 𝑢1 𝑢2 … 𝑢𝑛 𝑣1 … 𝑣𝑚
• Théorème: La concaténation sur * est associative et admet pour élément neutre le mot
vide ε. Elle n’est pas commutative.
• Théorème: Pour tout u, v∈ * on a :
• |uv| = |u| + |v| ; et ∀𝑎 ∈ 𝐴, 𝑢𝑣 𝑎 = 𝑢 𝑎+ 𝑣 𝑎.
• Simplification
• Théorème (simplification): Si u, v, w sont trois mots tels que uw = vw alors u = v. de
même, si wu = wv alors u = v. On dit qu’on peut simplifier à gauche et à droite
• Miroir
• Définition (miroir): Le miroir d’un mot 𝑢 = 𝑢1 … 𝑢𝑛 , noté 𝑢෤ est le mot 𝑢෤ = 𝑢෤ 1 … 𝑢෤ 𝑛 vérifiant:
∀𝑖 ∈ 1, … , 𝑛 𝑢෤ 𝑖 = 𝑢𝑛+1−𝑖 .
• Exemple: 𝑢 = 𝑏𝑜𝑛𝑗𝑜𝑢𝑟 on a 𝑢෤ = 𝑟𝑢𝑜𝑗𝑛𝑜𝑏.
• Théorème: Pour tout u ∈ *, 𝑢෤ = 𝑢 et 𝑢෨෤ = 𝑢. Pour tout u, v ∈ *, 𝑢෦𝑣 = 𝑣෤ 𝑢.
෤

Cours de 3ème Année Ingénieur 13

Découpage des mots
• Définition (préfixe): On dit qu’un mot v est un préfixe d’un mot u
s’il existe un mot w ∈ * tel que u = vw.
• Définition (suffixe): On dit qu’un mot v est un suffixe d’un mot u sur 
s’il existe un mot w ∈ * tel que u = wv.
• Définition (facteur): On dit qu’un mot v est un facteur d’un mot u sur
 s’il existe deux mots w, w’ ∈ * tel que u = wvw’.
• Attention
• Dans les définitions ci-dessus, on peut très bien prendre w =ε et/ou w’= ε.

Cours de 3ème Année Ingénieur 14

Découpage des mots
• Définition (sous-mot): Soit 𝑢 = 𝑢1 … 𝑢𝑛 un mot de *. Un sous-mot
v de u est un mot de longueur m tel qu’il existe une injection
strictement croissante 𝜙: 1, … , 𝑚 → 1, … , 𝑛 tel que: 𝑣 =
𝑢𝜙(1) 𝑢𝜙(2) … 𝑢𝜙(𝑚)
• Informellement on obtient un sous-mot de u en supprimant des
lettres de u et en ne changeant pas l’ordre de celles qui restent. Si
u =informatique, v = faq est un sous-mot de u, mais pas w = fini.
• Théorème. Pour tout 𝑢 ∈ Σ ∗ , u et ε sont toujours des préfixes, des
suffixes, des facteurs et des sous-mots de u.

Cours de 3ème Année Ingénieur 15

Ordre sur les mots
• Hypothèse: L’alphabet  est totalement ordonné (on donne un ordre
sur les lettres).
• Définition (ordre lexicographique): Soient u et v deux mots de , on
dit que u est plus petit que v pour l’ordre lexicographique, noté u ≤ v
ou encore u ≤ lex v quand :
• ou bien u est préfixe de v ;
• ou bien il existe a < b dans  (pour l’ordre sur l’alphabet), il existe des mots w,
u’, v’ dans *, tels que u = wau’ et v=wbv’.
• C’est l’ordre utilisé pour les dictionnaires.

Cours de 3ème Année Ingénieur 16

Langages (1)
• Définition (langage): Un langage est un ensemble de mots. C’est donc
un élément de 𝒫(Σ ∗ ).
• Définition (concaténation de langages): Soient X et Y deux langages,
la concaténation de X et de Y, notée XY est l’ensemble des
concaténations des mots de X par les mots de Y:
𝑋𝑌 = 𝑥. 𝑦|𝑥 ∈ 𝑋, 𝑦 ∈ 𝑌
• Théorème. La concaténation des langages est associative mais pas
commutative. L’élément neutre est le langage réduit au mot vide {ε}.
• Définition (miroir d’un langage): Soit X un langage, le miroir noté 𝑋෨
est l’ensemble des miroirs des mots de X : 𝑋෨ = 𝑥෤ 𝑥 ∈ 𝑋 .
Cours de 3ème Année Ingénieur 17
Langages (2)
• Définition (puissances): Par convention, pour tout langage X on pose
X0= {ε}. On définit les puissances d’un langage X, pour tout n ≥ 1 par
Xn= Xn−1X.
• Pour n ≥ 1, u ∈ Xn si et seulement si il peut s’écrire comme
concaténation de n mots de X.
• Définition (étoile) Soit X un langage, l’étoile de X (on dit aussi l’étoile
de Kleene de X) est le langage 𝑋 ∗ = ‫≥𝑛ڂ‬0 𝑋 𝑛 .
• Le langage X∗ contient toujours le mot vide.

Cours de 3ème Année Ingénieur 18

Exercices
• Exercice 1 : Combien y a-t-il de mots de longueur p sur un alphabet à n
lettres ?
• 1. contenant au moins une occurrence d’une lettre donnée a ?
• 2. contenant exactement une occurrence d’une lettre donnée a ?
• 3. contenant exactement q occurrences d’une lettre donnée a ?
• Exercice 2. Soit l’alphabet V = {a, b} et les langages : L1={a, ab, ba} et L2={ε,
b, ba}
• 1. Donner les résultats
2
des opérations suivantes : L1.L2, L2.L1 , L1.∅, ∅.L2, L1.{ε},
{ε}.L2, L2∩{ε}, 𝐿1
• 2. Si L3 et L4 sont deux langages tels que L3 . L4 = {ε}, que peut on dire de L3 et L4 ?
• 3. Si L5 et L6 sont deux langages tels que L5 . L6 = ∅, que peut on dire de L5 et L6 ?
• Exercice 3. Soit Σ un alphabet. Montrer que Σ* est un ensemble infini
dénombrable.

Cours de 3ème Année Ingénieur 19

Chapitre 2: automates et
langages reconnaissables
Un langage est dit reconnaissable s'il est reconnu par un automate fini. On introduit la notion d'automate fini et celle
d'automate généralisé. On montre que tout langage reconnaissable peut être reconnu par un automate fini
déterministe mais que cette transformation peut, dans le pire cas, accroitre de façon exponentielle la taille de
l'automate. On étudie les propriétés de clôture des langages reconnaissables : cette famille de langage est close par
les opérations booléennes (union, intersection, complémentaire et donc aussi différence ensembliste) ainsi que par
l'opération de concaténation et d'itération, elle est close également par image miroir et par images directes et
inverses par substitutions (d'un mot à une lettre).

Cours de 3ème Année Ingénieur 20

Automate fini
• Un automate fini A = (Q,q0,, d,F) consiste en
• un ensemble fini Q d'états, q0 Q est l'état initial,
•  est un ensemble fini appelé alphabet de l'automate,
• d: Q×→(Q) est la fonction de transition. ((Q) = {X  Q} désigne
l'ensemble des parties de Q.)
• F  Q est l'ensemble des états finals de l'automate.
• Représentation de la fonction de transition
• Table de transition
• Sagittale

Cours de 3ème Année Ingénieur 21

Automate fini
• Table de transition de l'automate, dont les lignes sont associées aux états de l'automate, les
colonnes sont associées aux lettres de l'alphabet, et la case correspondant à l'état q et à la lettre
a contient les états qd(q,a), c'est à dire les états atteints à partir de q par lecture de la lettre a
.
• Diagramme sagittale qui est un graphe dont les sommets sont les états et dans lequel on
dispose d'un arc étiqueté a de q vers q’ lorsque q’d(q,a). Si u * est un mot construit sur
l'alphabet, on note q -- u → q s'il existe un chemin dans le graphe allant de q à q étiqueté u, ce
qui est défini inductivement par:
• q --  → q pour tout état q
• q -- a → q lorsque q d(q,a)
• q -- au → q s'il existe un état q tel que q -- a → q et q -- u → q
• Un mot u  * est reconnu par l'automate s'il existe un chemin étiqueté u partant de l'état
initial et conduisant à un état final, le langage reconnu par l'automate est donc défini par
L(A)={u*|$qF q0--u→q}

Cours de 3ème Année Ingénieur 22

Exemple
• Construire un automate reconnaissant chacun des langages suivants
sur l'alphabet ={a;b}
1. L1 = {u* |$ v* u = vaa}, c'est à dire les mots ayant pour suffixe (ou bien
se terminant par) a2.
2. L2 = { u * | #a(u) est paire} où #a(u) désigne le nombre d'occurrences de
la lettre a dans le mot u.
3. L3 = *aba*, ie les mots ayant pour facteur aba

Cours de 3ème Année Ingénieur 23

Automates déterministes
• Un automate est dit déterministe si les entrées de sa table de transition
contiennent au plus un élément,
• c'est à dire si pour tout état q et toute lettre a il existe au plus un état q tel que
(q,a,q) d
• Un automate est dit complet si les entrées de sa table de transition
contiennent au moins un élément, c'est à dire si pour tout état q et toute
lettre a il existe au moins un état q tel que (q,a,q) d
• Remarque:
• Il est toujours possible de rendre un automate complet par adjonction d'un état
supplémentaire ^, appelé état puits
• pour tout état q et toute lettre a tels qu'il n' existe pas d'état q tel que (q,a,q)d on
ajoute alors la transition (q,a,^) à d ainsi que les transitions (^,a,^) pour chaque lettre
a

Cours de 3ème Année Ingénieur 24

Rendre un automate fini déterministe
• Proposition: Soit A = (Q,q0,,d, F) un automate fini;
l'automate det(A) = ((Q),{q0}, d,F) dans lequel:
• (Q) = {X  Q} est l'ensemble des parties de Q
• Y  d(X,a)  Y = {q  Q | $ p X q d(p,a)}
• F = {X  Q | XF }
• est déterministe, complet et reconnait le même langage que A.
• Cas défavorable
• Det(A) peut avoir jusqu’à 2card(Q) états

Cours de 3ème Année Ingénieur 25

Exemple
L3 = *aba*, ie les mots ayant pour facteur aba

Automate fini non déterministe Automate fini déterministe correspondant

Cours de 3ème Année Ingénieur 26

Propriétés de clôture
• Un langage L  * est dit reconnaissable s'il s'agit de l'ensemble des
mots reconnus par un automate fini sur l’alphabet .
• Proposition. L'ensemble des langages reconnaissables est clos par
union, intersection, complémentaire, concaténation et étoile
• Preuve (Complémentaire)
• Soit A=(Q,q0,,d,F) un automate déterministe complet reconnaissant L le
langage complémentaire Lc=*\L est reconnu par l'automate Ac=(Q,q0,,d,
Q\F)

Cours de 3ème Année Ingénieur 27

Propriété de clôture
• Preuve (Intersection)
• Soient L1 et L2 les langages reconnus par deux automates A1=(Q1,q0,1,,d1,F1) et
A2=(Q2,q0,2,,d2,F2) alors l'automate A=(Q,q0,,d,F) défini comme il suit reconnait
L1L2
• Q = Q1×Q2 = {(q1,q2) | q1Q1 et q2 Q2}
• q0 = ( q0,1,q0,2)
• (q1,q2)  d((q1,q2),a)  q1d1(q1,a) et q2 d2(q2,a)
• F = F1×F2
• Preuve (Union)
• Approche 1: L1L2 = (Lc1Lc2)c.
• Approche 2: Une construction directe d'un automate (généralisé) reconnaissant
L1L2 à partir d'automates reconnaissant L1 et L2 consiste à juxtaposer une copie de
chacun de ces automates, puis à ajouter un nouvel état i qui devient l'état initial avec
deux transitions à vide (i,,q0,1) et (i,,q0,2) de cet état vers chacun des états initiaux
des deux automates

Cours de 3ème Année Ingénieur 28

Propriétés de clôture
• Preuve (concaténation)
• Si L1 et L2 sont des langages reconnus par des automates A1 et A2 leur
concaténation L1· L2 est reconnu par l'automate (généralisé) obtenu par
juxtaposition des automates A1 et A2 auxquels on ajoute les transitions à vide
(q,,q0,2) de chacun des états finals de A1 vers l'état initial de A2, avec comme
état initial l'état initial q0,1 de A1 et comme états finals ceux de A2.
• Preuve (Etoile)
• Si L est un langage reconnu par un automate A, son étoile L* est reconnu par
l'automate obtenu à partir de A par ajout d'un nouvel état i et de transitions à
vide (q,,i) de chacun des état finals q de A vers i et d'une transition à vide de i
vers l'état initial de A, i est l'état initial de cet automate et ses états finals sont
ceux de A auxquels on ajoute l'état i.

Cours de 3ème Année Ingénieur 29

Exercices
1. Donner un automate a états finis qui reconnait les mots sur
l’alphabet {a,b} qui se terminent par « aab ».
• Rendre l’automate obtenu déterministe
2. Donner un automate à états finis qui accepte les mots sur l’alphabet
{a,b} qui commence par b, se termine par b et ayant a* en facteur
i.e les mots de la forme b(a)*b
• Rendre l’automate obtenu déterministe s’il ne l’est pas
3. Donner un automate à états finis déterministe acceptant les
nombres binaires qui contiennent la sous-chaîne « 011 »
4. Donner un automate à états finis déterministe acceptant les
nombres binaires qui ne contiennent pas la sous-chaîne « 011 »
Cours de 3ème Année Ingénieur 30
Exercices
• Construire un automate reconnaissant chacun des langages suivants
sur l'alphabet ={a;b}
1. L1 = {u* |$ v* u = vaaa ou u = vbb}, c'est à dire les mots se terminant
par a3 ou b2.
2. L2 = { u * | #a(u) est paire et #b(u) est impaire} où #a(u) désigne le
nombre d'occurrences de la lettre a dans le mot u.
3. L3 = *aba*
• Construire un automate fini qui accepte les suites binaires qui
représentent des nombres divisibles par 3

Cours de 3ème Année Ingénieur 31

 Exercices
• Construire un automate déterministe complet équivalent à chacun
des automates suivants sur l'alphabet {a; b}
Q = {p,q,r}, l'état initial est p, r est final et la table de transition est
a b
a b
p q, r p
p p,q p
q s
q r
r r, s
r
s s r
Q = {p,q,r,s}, l'état initial est p, s est final et la table de transition est
Cours de 3ème Année Ingénieur 32
Langages rationnels
On introduit la notion d'expression rationnelle et donne la preuve du théorème de Kleene qui indique
qu'un langage est rationnel, c'est à dire représentable par une expression rationnelle, si, et seulement si, il
est reconnaissable. Ce théorème est constructif ce qui signifie que l'on dispose d'algorithmes permettant de
construire un automate à partir d'une expression rationnelle, et inversement d'extraire une expression
rationnelle représentant le langage d'un automate fini. On introduit ensuite les expressions rationnelles
étendues qui sont des notations abrégées pour des expressions rationnelles.

Cours de 3ème Année Ingénieur 33

Les expressions rationnelles
• Soient
•  un alphabet
• 0 et 1 deux constantes n’appartenant pas à l’alphabet
• un opérateur unaire * et un opérateur binaire + qui seront respectivement associés aux
opérations d'itération et d'union sur les langages
• Définition inductive (ER() ensemble des expressions rationnelles associées
à un alphabet)
• "a  a  ER()
• 0,1  ER()
• "e1, e2  ER() e1 +e2  ER()
• "e1, e2  ER() e1 ·e2  ER()
• "e  ER() e*  ER()

Cours de 3ème Année Ingénieur 34

Langages rationnels
• Définition inductive (Le langage L(e)  * associé à une expression
rationnelle e  ER() )
• "a  L(a) = {a}
• L(0) =  et L(1) = { }
• "e1, e2  ER() L(e1 +e2) = L(e1)L(e2)
• "e1, e2  ER() L(e1 ·e2) = L(e1)·L(e2)
• "e  ER() L(e*) = L(e)*
• Un langage est dit rationnel s'il peut être représenté par une expression
rationnelle
• L  Rat(*)  $ eER() L = L(e)

Cours de 3ème Année Ingénieur 35

 Exemples
• Sur l’alphabet Σ = 𝑎, 𝑏 , voici • Les langages associés à chacune
quelques exemples des ER
d'expressions régulières • 𝐿(𝑒1 ) = 𝜖, 𝑎𝑏
• 𝑒1 = 1 + 𝑎. 𝑏 • 𝐿(𝑒2 ) = 𝑎𝑏𝑎 ∪ 𝑏 ∗ ∗
∗ ∗
• 𝑒2 = 𝑎. 𝑏 . 𝑎 + 𝑏 • 𝐿(𝑒3 ) = {𝑎, 𝑏}∗ 𝑎𝑏
• 𝑒3 = (𝑎 + 𝑏)∗ . 𝑎. 𝑏 • Question: Donner l’expression
littérale de chaque langage
Remarque:
✓ Dans la suite, on s'autorisera a confondre une expression régulière et le langage qu'elle représente.
✓ Si aucune confusion n'est possible, on s'autorisera également a enlever les parenthèses ou autres symboles
superflus.
Cours de 3ème Année Ingénieur 36
Langages rationnels et langages reconnaissables
• Théorème (dit de Kleene)
• Un langage 𝐿 ⊆ Σ ∗ est rationnel si, et seulement si, il est reconnaissable.
• Preuve
• Comme , {} et {a} pour toute lettre a  sont des langages reconnaissables
et que par ailleurs la classe des langages reconnaissables est close par union,
concaténation et étoile on déduit que tout langage rationnel est reconnaissable.
Inversement supposons que L  * soit un langage reconnaissable
• L'algorithme de Thompson permet d'aller de l'expression rationnelle à l’automate
• Inversement, construire un automate fini à partir d’une ER. La preuve est
constructive, mais nous verrons plutôt la méthode directe

Cours de 3ème Année Ingénieur 37

 Construction inductive de l’automate
Cas de base
Expression ε Expression a où a est une lettre

Cas inductifs Etoile de Kleene s*

Union (s+t)

Concaténation s.t

Cours de 3ème Année Ingénieur 38

 Exemple 𝑒 = (𝑎𝑏 + ∗
𝑐 )

Etape 1. on construit l’automate qui reconnait {a}

Etape 2. on construit l’automate qui reconnait {b}
Etape 3. on construit l’automate qui reconnait {c}
Etape 4. Par concaténation de 1 et 2, on construit
l’automate qui reconnait {ab}
Etape 5. A partir de l’automate 3, on construit un
automate reconnaissant c*
Etape 6. e est reconnu par l’union de 4 et 5
Exercice. 𝑒′ = (𝑎 + 𝑏)∗ 𝑏 Cours de 3ème Année Ingénieur 39
Système d'équations caractéristiques
• Si A = (Q,q0,,d,F) est un automate fini, on lui associe un système
d'équations
• une variable Xi pour chaque état qi de l'automate.
• Cette variable Xi est associée à une équation ayant l'une des deux formes suivantes :
1. Xi = a1·Xj1 + + ak·Xjk ou
2. Xi = 1 + a1·Xj1 + + ak·Xjk si qi est final
• Une solution du système est un ensemble de langages L1, Ln * tels que
• Li = a1·Lj1 ak·Ljk si Xi = a1·Xj1 + + ak·Xjk
• Li = {}a1·Lj1ak·Ljk si Xi = 1 + a1·Xj1 + + ak·Xjk
• Li est le langage reconnu à partir de l'état qi, en particulier L0 est le
langage de l'automate
Cours de 3ème Année Ingénieur 40
Equation en langages
• Lemme 1 (Arden). Soient A et B deux langages. L’équation X = AX + B a une
plus petite solution, qui est X = A*B. Cette solution est unique si ℰ
n’appartient pas au langage A.
• Démonstration
• validité : A*B est bien solution : 𝐴 𝐴∗ 𝐵 + 𝐵 = 𝐴𝐴∗ + 1 𝐵 = 𝐴∗ 𝐵
• minimalité : Soit L une solution de l’équation. Alors L = AL + B. En remplaçant L par
AL + B à droite, on a aussi 𝐿 = 𝐴 𝐴𝐿 + 𝐵 + 𝐵 = 𝐴2 𝐿 + 𝐴𝐵 + 𝐵. En continuant
ainsi, on montre (par récurrence) que 𝐿 = 𝐴𝑛+1 𝐿 + σ𝑛𝑖=0 𝐴𝑖 𝐵. Ainsi, pour tout 𝑛 ≥
0, 𝐴𝑛 𝐵 ⊆ 𝐿, 𝑒𝑡 𝑑𝑜𝑛𝑐 𝐴∗ 𝐵 ⊆ 𝐿.
• unicité : si ℰ n’est pas élément de A, alors soit u un mot d’un langage solution L de
l’équation. Si 𝑢 = 0, alors le mot vide appartient à B. Sinon, si 𝑢 = 𝑛, comme on a
𝐿 = 𝐴𝑛+1 𝐿 + σ𝑛𝑖=0 𝐴𝑖 𝐵, u est nécessairement dans σ𝑛𝑖=0 𝐴𝑖 𝐵. donc 𝐿 = 𝐴∗ 𝐵.

Cours de 3ème Année Ingénieur 41

 Exemple
Soit l’automate ci-après
𝑅é𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑑𝑒 𝑙 ′ é𝑞𝑢𝑎𝑡𝑖𝑜𝑛 2:
𝑋1 = 𝑎∗ 𝑏𝑋2
Substitution dans l′équation 3:
𝑋2 = 1 + 𝑎𝑎∗ 𝑏 + 𝑏 𝑋2
𝑞𝑢𝑖 𝑎 𝑝𝑜𝑢𝑟 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑋2 = (𝑎𝑎∗ 𝑏 + 𝑏)∗
Substitution dans les 2 autres:
𝑋0 = 𝑐𝑋1 + 𝑏𝑋2 𝑋1 = 𝑎∗ 𝑏(𝑎𝑎∗ 𝑏 + 𝑏)∗ 𝑒𝑡
ቐ 𝑋1 = 𝑎𝑋1 + 𝑏𝑋2 𝑋0 = (𝑐𝑎∗ 𝑏 + 𝑏) (𝑎𝑎∗ 𝑏 + 𝑏)∗
𝑋2 = 𝑎𝑋1 + 𝑏𝑋2 + 1

Cours de 3ème Année Ingénieur 42

Exercices
Donner une expression rationnelle pour les automates ci-après

Cours de 3ème Année Ingénieur 43

TD: Elimination des transitions spontanées
• Définition: Les transitions étiquetées par le mot vide dans un automate fini sont appelées
les transitions spontanées.
• Un Automate fini à transitions spontanées est un automate fini (non-déterministe) noté
𝜀 − 𝑁𝐹𝐴
• Définition (𝜀 − 𝑓𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒)
• 𝜀 − 𝑓𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒(𝑝) = {𝑞 ∈ 𝑄|𝛿 ∗ (𝑝, 𝜀) = 𝑞}, i.e l’ensemble des états qu’on peut atteindre en
suivant des transitions vides
• Par construction, p ∈ 𝜀 − 𝑓𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒(𝑝)
• Théorème. Pour
′
tout 𝜀 − 𝑁𝐹𝐴 A, il existe un DFA A’ qui reconnait le même langage
𝐿 𝐴 = 𝐿(𝐴 )
• Démonstration
• En posant A = Σ, 𝑄, 𝑑, 𝐹, 𝛿 𝑢𝑛 𝜀 − 𝑁𝐹𝐴, on définit A’ comme suit: A′ = Σ, 𝑄, 𝑑′, 𝐹′, 𝛿′ avec
• F ′ = {q ∈ 𝑄|𝜀 − 𝑓𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒(𝑞) ∩ 𝐹 ≠ ∅}
• 𝛿 ′ 𝑝, 𝑎 = ‫𝜀∈𝑞ڂ‬−𝑓𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒(𝑝) 𝛿(𝑞, 𝑎)

Cours de 3ème Année Ingénieur 44

Exemple
• Construire l’automate fini pour l’expression rationnelle a*b*c*
• Eliminer les transitions spontanées

Cours de 3ème Année Ingénieur 45

Exercice.
• Convertissez les expressions rationnelles suivantes en 𝜀−𝑁𝐹𝐴 :
1. 01*
2. (0 + 1)01
3. 00(0 + 1)*
• Puis éliminer les transitions spontanées

Cours de 3ème Année Ingénieur 46

Exercices
• Construire un automate fini qui accepte les suites binaires qui
représentent :
1. Des nombres pairs
2. Des nombres multiples de 4
• Construire le NFA, le rendre déterministe, puis minimiser
3. Ensemble de toutes les chaînes ne contenant pas 101
• Construire un automate sur l'alphabet ={a;b} reconnaissant le
langage des mots admettant aba pour facteur
• Construire l’automate du langage miroir
• Donner une expression rationnelle

Cours de 3ème Année Ingénieur 47

Travaux dirigés
Rendre déterministe les automates suivants

Cours de 3ème Année Ingénieur 48

Langages réguliers, Automate
minimal
On introduit la notion de résidu d'un langage par un mot et l'équivalence de Nerode. Un langage est dit régulier s'il n'admet qu'un nombre fini de résidus ce
qui revient à dire que son équivalence de Nerode est de type fini. On montre qu'un langage est reconnaissable si, et seulement si, il est régulier. L'automate
associé à l'équivalence de Nerode d'un langage reconnaissable possède une propriété remarquable intéressante : il s'agit de l'automate déterministe
complet reconnaissant le langage ayant un nombre minimal d'états. Cette propriété caractérise, à isomorphisme près, cet automate qui est alors appelé
automate canonique associé au langage. On définit une équivalence, dite aussi de Nerode, sur les états d'un automate fini de telle sorte que son automate
canonique est obtenu en quotientant par cette équivalence. Cela nous procure un moyen pour décider si deux automates finis sont équivalents, c'est à dire
s'ils reconnaissent le même langage. Par ailleurs on introduit un calcul (calcul de Brzozowski) pour les résidus d'une expression rationnelle qui permet de
calculer directement l'automate canonique associé à une expression rationnelle

Cours de 3ème Année Ingénieur 49

Notion de residuel
• Définition: Le résidu d'un langage 𝐿 ⊆ Σ ∗ par un mot 𝑢 ∈ Σ ∗ est le
langage 𝑢 −1 𝐿 = {𝑣 ∈ Σ ∗ |𝑢𝑣 ∈ 𝐿}
• c'est à dire qu'il s'agit de l'ensemble des mots qui peuvent être concaténés à
u pour former un mot du langage.
• Définition. Un langage est dit régulier s'il possède un nombre fini de
résidus.
• Proposition. Tout langage reconnaissable est régulier

Cours de 3ème Année Ingénieur 50

Langage régulier
• Preuve:
• Soit A = (Q,q0,,d,F) un automate fini déterministe complet reconnaissant le langage
L considéré. Pour tout mot u  * posons qu l'état atteint à partir de l'état initial par
lecture du mot u, i.e. q0 -- u → qu. Un tel état existe car l'automate est complet, et il
est caractérisé par cette propriété car l'automate est déterministe. Il est alors clair que
u-1L = L(qu) où Lq = {v   | $q  F q -- v → q} désigne le langage reconnu à
partir de l'état q. Comme il n'y a qu'un nombre fini détats on en déduit que L n'admet
qu'un nombre fini de résidus et donc est régulier.
• Corollaire. Tout résidu d'un langage reconnaissable est reconnaissable.
• Preuve : Avec les mêmes notations que dans la preuve précédente; le résidu u-1L =
L(qu) est reconnu par l'automate Au = (Q,qu,,d,F) obtenu à partir de l'automate de
départ en remplaçant l'état initial par qu.

Cours de 3ème Année Ingénieur 51

Langage régulier
• Proposition. Tout langage régulier est reconnaissable
• Preuve: Soient L un langage régulier. Par hypothèse, il a un ensemble un
ensemble fini de résidu. Notons le Q={L0, …, Ln}
• Supposons que L0=ℰ-1L i.e L lui-même; alors l’automate can(L) = (Q,L0,D, F) où
• F ensemble des états finaux sont les résidus de L contenant le mot vide
• Le relation de transition est donnée par Li  D(Lj, a) si et seulement si Li = a-1Lj
• Cet automate reconnait L
• On montre en effet aisément par récurrence sur la longueur du mot u que Li --
u → Lj si, et seulement si, Lj = u-1Li une fois qu'on a observé les identités -1L = L
et (u·a)-1L = a-1(u-1L). Le langage de can(L) est alors l'ensemble des mots u tels
que   u-1L or cette dernière condition équivaut au fait que u  L.
• can(L), appelé automate canonique de L
• Il est par définition déterministe et complet.
• Il s'agit du plus petit automate déterministe complet reconnaissant L

Cours de 3ème Année Ingénieur 52

Equivalence de Nerode
• Donnée: A = (Q,q0,,d,F) est un automate déterministe complet
• Définition (langage reconnu depuis un état q)
• 𝐿𝑞 = {𝑢 ∈ Σ ∗ |𝛿 ∗ (𝑞, 𝑢) ∈ 𝐹}
• en particulier 𝐿 𝐴 = 𝐿𝑞0
• Définition (congruence de Nerode)
• Deux états q et q’ de A sont discernés par un mot u si 𝛿 ∗ (𝑞, 𝑢) ∈ 𝐹 et 𝛿 ∗ (𝑞′, 𝑢) ∉ 𝐹
ou le contraire; i.e le mot u est « reconnu » à partir de l'un d'entre eux mais par les
deux.
• Deux états sont dits indiscernables s'il n'y a aucun mot permettant de les discerner.
• Cette relation d'indiscernabilité est une relation d'équivalence appelée
équivalence de Nerode.
• Ainsi deux états q et q’ sont équivalents pour l'équivalence de Nerode s'ils
reconnaissent le même langage: 𝐿𝑞 = 𝐿𝑞′
Cours de 3ème Année Ingénieur 53
Etats équivalents
• On pose 𝑞 ≡𝑛 𝑞′ lorsque q et q’ ne sont discernés par aucun mot de
longueur inférieure ou égale à n
• q  n q  Lq  n = Lq’  n
• On les identités suivantes qui nous permettent de calculer ces
relations de proche en proche
1. q  0 q  les deux états sont finaux ou non
2. q  n+1 q  "a   q·a  n q·a
• si  n =  n+1 alors "m  n  n =  m et l'équivalence de Nerode est
obtenue à cette n-ième étape

Cours de 3ème Année Ingénieur 54

Automate quotient
• Le quotient de A par son équivalence de Nerode est obtenu en identifiant les états
indiscernables.
• Il s'agit de l'automate Nerode(A) = (Q  , [q0], N(d), N(F)) dans lequel:
• Q  = {[q] | q  Q} est l'ensemble des classes d'équivalence des états pour l'équivalence de
Nerode,
• [q0] est la classe de l'état initial,
• Y  N(d)(X,a)  $q  X, $q  Y tel que q  d(q,a),
• N(F) = {[q] | q  F} est l'ensemble des classes d'équivalence des états finals.
• Théorème: Le quotient d'un automate déterministe complet A par son
équivalence de Nerode est un automate déterministe complet qui reconnait le
même langage que A
• Proposition: 𝑵𝒆𝒓𝒐𝒅𝒆(𝑨) ≈ 𝒄𝒂𝒏(𝑳(𝑨))
• Le quotient d'un automate déterministe complet accessible (tous les états sont accessibles à
partir de l' état initial) par son équivalence de Nerode est isomorphe à l'automate canonique
du langage reconnu par cet automate.

Cours de 3ème Année Ingénieur 55

Problème de minimisation
• Donnée : A un A.F.D. complet dont chaque état est accessible depuis
l’état initial
• Problème : construire l’automate minimal (déterministe et complet)
qui reconnaît le même langage que A
• Idée : faire en sorte que les états équivalents soient fusionnés
• En pratique, l’algo. est fondé sur le principe de «séparation des états»
• on commence par séparer les états finals des états non finals
• dans chaque classe, on sépare les états non équivalents
• on renouvelle cette opération jusqu’à la stabilisation ...

Cours de 3ème Année Ingénieur 56

Minimisation (algorithme de Moore)
• Idée: identifier les classes d’équivalence à partir d’un automate fini
déterministe A = (Q,q0,, d,F)
• la partition correspondant aux classes d’équivalence est construite par
raffinement de la partition initiale Π0 qui distingue simplement états finaux et
non-finaux
• Algorithme (itératif)
1. Initialiser avec deux classes d’équivalence : F et Q\ F
2. Itérer jusqu’à stabilisation :
▪ pour toute paire d’états q et p dans la même classe de la partition Π𝑘 , s’il
existe 𝑎 ∈ Σ tel que δ 𝑞, 𝑎 𝑒𝑡 𝛿(𝑝, 𝑎) ne sont pas dans la même classe pour
Π𝑘 , alors ils sont dans deux classes différentes pour Π𝑘+1 .

Cours de 3ème Année Ingénieur 57

Exemple
Un DFA à minimiser
L’automate minimal

Cours de 3ème Année Ingénieur 58

Corolaire
• L'automate canonique associé à un langage reconnaissable est l'automate
déterministe complet ayant le minimum d’états qui reconnaisse ce langage.
• On peut décider si deux automates finis reconnaissent le même langage :
• On les rend déterministes, complets et accessibles en passant aux parties,
• on quotiente les automates obtenus par leurs équivalence de Nerode,
• on vérifie que les automates réduits ainsi obtenus sont isomorphes.
• On peut décider si deux expressions rationnelles représentent le même
langage
• construire un automate associé à chacun d'entre eux et leur appliquer la procédure
précédente.

Cours de 3ème Année Ingénieur 59

Résidus d'une expression rationnelle
• On peut directement calculer l'automate canonique du langage associé
à une expression rationnelle en définissant une opération de résidu sur
les expressions rationnelles telle que : L(u-1e) = u-1L(e).
• Pour cela on part des identités suivantes :
• a-1(L1L2) = a-1L1a-1L2,
• a-1(L1·L2) = (a-1L1)·L2  (L1)·a-1L2,
• a-1L* = (a-1L)·L*
• où (L) = {} si   L et (L) =  sinon.

Cours de 3ème Année Ingénieur 60

Résidus d’une ER
• la fonction 𝞺 ci-dessus sur les expressions rationnelles est définie
inductivement par
• (0) = (a) = 0,
• (1) = (e*) = 1,
• (e1+ e2) = (e1)+(e2) et
• (e1·e2) = (e1)·(e2)
• de sorte que L((e)) = 1 si   L(e) et L((e)) = 0 sinon.
• Le résidu d'une expression rationnelle par une lettre est alors donné par :
• a-11 = 0, a-1a = 1, a-1b = 0 si a  b
• a-1(e1+ e2) = a-1e1+ a-1e2
• a-1(e1·e2) = (a-1e1)·e2 + (e1)·a-1e2
• a-1(e*) = (a-1e)·e*

Cours de 3ème Année Ingénieur 61

Calcul de Brzozowski
• 1. initialiser l'ensemble des expressions à traiter par l'expression rationnelle
dont on cherche à construire l'automate canonique.
• 2. tant qu'il reste des expressions à traiter faire le traitement suivant
a. Choisir une expression parmi l'ensemble des expressions non traitées et la retirer de
cet ensemble.
b. En utilisant le fait que la somme est associative, commutative, idempotente, et admet
0 comme neutre, que le produit est associatif, admet 1 comme neutre et distribue par
rapport à la somme, et la règle d’expansion e* = 1+e·e* écrire e sous l'une des
équations suivantes :
i. e = a1·e1 + + ak·ek
ii. e = 1+a1·e1 + + ak·ek
c. Parmi les expressions ei identifier celles qui ont déjà été rencontrées et ajouter les
autres à l'ensemble des expressions à traiter.

Cours de 3ème Année Ingénieur 62

Construction de l’automate minimal
• 3. L'ensemble des équations obtenues nous donne une description de
l'automate canonique, plus précisément
a. Les états de l'automate sont les expressions obtenues, l'état initial est
l'expression de départ et une expression correspond à un état final si 1
apparait en partie droite de l'équation qui la définit.
b. On a une transition de ei vers ej étiquetée a si, et seulement si, le terme
a·ej apparait en partie droite de l'équation définissant ei.

Cours de 3ème Année Ingénieur 63

Exemple
• e = (ca*b+b)·(aa*b+b)*
• e = ca*b(aa*b+b)* + b(aa*b+b)* distributivité de la concaténation sur +
• e = c·e1+b·e2 avec e1 = a*b(aa*b+b)* et e2 = (aa*b+b)*
• e1 = a*b(aa*b+b)* =(1+aa*)b(aa*b+b)* on sait que e*=1+ee*
• e1 = b·e2+a·e1
• e2 = (aa*b+b)*=1+(aa*b+b)(aa*b+b)*
• e2 = 1+a·e1+b·e2

Cours de 3ème Année Ingénieur 64

Synthèse (sous forme d’un automate)

Cours de 3ème Année Ingénieur 65

Exercices
• Montrer que: ∀𝑢 ∈ Σ ∗ , 𝑎 ∈ Σ (ua)-1L=a-1u-1L
• Généralisation: Montrer que ∀𝑢, 𝑣 ∈ Σ ∗ , (uv)-1L=v-1u-1L
• Caractériser les résidus du langage {anbn| n IN} et en déduire que ce
langage n'est pas reconnaissable
• Utiliser la méthode des résidus pour construire l'automate canonique
associé à chacune des expressions suivantes :
1.(a+b)*aba(a+b)*
2.(a+b)*(ab+ba)(a+b)*
3.(a+b)*a(a+b)(a+b)
• Montrer que (a+bd*c)* = a*+a*b(ca*b+d)*ca*.

Cours de 3ème Année Ingénieur 66

Minimiser les automates

Cours de 3ème Année Ingénieur 67

Exercice
On considère l’automate ci-après Determiniser chacun des automates
1. Est-ce que cet automate accepte le mot ccabab ? Et suivants, puis minimiser l’automate
le mot acbccccc ? obtenu
2. Quel est l’ensemble des états finaux de cet
automate ?
3. Cet automate est-il complet ? Est-il déterministe ?

Calculer l′ automate minimal correspondant à l′ expression

𝑎 𝑎𝑏 ∗ ∗ + 𝑎𝑏 ∗
Cours de 3ème Année Ingénieur 68
Exercices pratiques
• Exercice 1. Monsieur Berger B emmène un Loup L, une chèvre C, et un choux X
près d’une rivière et souhaite traverser avec un petit bateau. Le bateau est
tellement petit que B peut entrer dans le bateau avec au plus un passager. Sans
surveillance de B, L mange C et C mange X. Comment B peut faire traverser la
rivière à la compagnie ?
• 1. Construire un automate qui modélise la situation.
• 2. Utiliser cet automate pour trouver comment le problème peut être résolu.
• Exercice 2. Si U est un alphabet fini, on appelle liste de U une séquence débutant
par le symbole ’(’, finissant par le symbole ’)’, et contenant des éléments de U
séparés par des ‘:’. Ainsi par exemple: (1 : 2 : 3 : 2 : 1) est une liste d’éléments de
U = {1, 2, 3}. Dans tout l’exercice, on considérera qu’une liste contient toujours au
moins un élément: il n’y a pas de liste vide.
• Est-il possible de reconnaître l’ensemble des listes d’éléments de U = {1, 2, 3} avec un
automate fini ? Si votre réponse est positive, donnez une représentation graphique d’un
automate reconnaissant ce langage, en indiquant précisément l’alphabet, l’état initial et le ou
les états finaux. Les automates les plus simples seront préférés.

Cours de 3ème Année Ingénieur 69

Exercices pratiques
• Exercice 2 – Distributeur de boissons
• On modélise un distributeur de boissons par un automate fini.
L’alphabet d’entrée 𝞢 = {d, v, c} correspond aux pièces de 25, 50 et
100 francs acceptées par le distributeur. Une boisson coûte 100
francs.
• Construisez un automate A déterministe reconnaissant toutes les séquences
de pièces dont le total est 100 francs. Vous pourrez éventuellement
commencer par proposer un automate non-déterministe reconnaissant
toutes ces séquences.

Cours de 3ème Année Ingénieur 70

Travaux Pratiques
• Problème:
• Ecrire un programme qui teste si une chaîne donnée (sous forme d’une
chaîne de caractères) appartient au langage d’un automate fini déterministe
donné.
• Solution 1: Automate code dans les instructions du programme
• Les transitions sont transcrites par des branchements conditionnels
• Solution 2: Implémentation d’un automate comme une donnée
• La représentation de l’automate est dans des variables. Un programme pour
interprète ces données et produit une exécution.
• Une représentation classique se fait au moyen de tableaux.
• Un tableau à deux dimensions pour les transitions
• et un tableau de booléens pour désigner si un état est final ou non

Cours de 3ème Année Ingénieur 71

Exemple
• Donner deux versions de l’implémentation de l’automate ci-dessous
• On utilisera le langage Java

Cours de 3ème Année Ingénieur 72

Grammaires et langages
algébriques
Un langage est dit algébrique s'il peut être engendrée par une grammaire
algébrique. On introduit les notions de grammaire algébrique, d'arbre de
dérivation, de trace de dérivations et d'ambiguïté.

Cours de 3ème Année Ingénieur 73

Grammaires algébriques
• Définition: Une grammaire algébrique G = (,V,R,S) consiste en
• un alphabet  dont les symboles sont appelés terminaux
• un ensemble V de variables ou non-terminaux
• un ensemble R  V×(V)* de règles de productions
• un axiome S  V
• Note
• réserver les lettres minuscules du début de l'alphabet latin a,b,c  pour
désigner les symboles terminaux (éléments de )
• les lettres de la fin de l'alphabet u,v,w,u,v,wu1, u1 pour désigner des
mots constitués de symboles terminaux u *
• les lettres de l'alphabet grec a,b,g,a,b1,g2 pour désigner des suites de
symboles grammatiaux i.e des éléments de (V)*.

Cours de 3ème Année Ingénieur 74

Notations des productions
• Une production (A,a)  V×(V)* sera écrite sous la forme A → a
• On pourra regrouper ensemble les productions
A → a1, A → a2  A →an concernant un même non-terminal en utilisant la
notation factorisée
• A →a1 | a2 |  | an ou encore
• A → a1 + a2 + + an.
• Lorsque cette dernière notation est utilisée on conviendra de noter le mot vide par 1 plutôt que
sous la forme 
• Exemple: La grammaire G = (,V,R,S) donnée par
•  = {a;b}, V = {S,A,B}, et
• R = {S → aAbS; S → bBaS; S → ; A → aAbA; A → ; B → bBaB; B → } sera représentée
par
• S → aAbS | bBaS |  A → aAbA |  B -- → bBaB |  ou encore
• S → 1 + aAbS + bBaS A → 1 + aAbA B → 1 + bBaB

Cours de 3ème Année Ingénieur 75