Théorie des Langages

Chapitre II
Automates à états finis

Yousra Hlaoui

2ème niveau du Cycle d’Ingénieur en Informatique

Préparatoire Intégrée
FST-DSI

Yousra Hlaoui (FST-DSI) Automates à états finis 1/1

Chapitre II
Automates à états finis

Yousra Hlaoui (FST-DSI) Automates à états finis 2/1

 Introduction

Introduction 1/3

Description d’un automate à états finis

Un automate à états finis a pour but de reconnaı̂tre ou
d’accepter un langage régulier de manière automatique.
Donner une signification à un automate revient à définir le
langage qu’il accepte.
Un automate se compose de :
Un ensemble fini d’états dont
un état initial est l’un des états de l’automate qui initialise son
exécution,
des états finaux qui terminent l’exétion de l’automate sur un mot
donné à son entrée.
Une fonction de transition qui indique pour chaque état et symbole
lu de l’entrée quel est l’état suivant de l’automate.

Yousra Hlaoui (FST-DSI) Automates à états finis 3/1

 Introduction

Introduction 2/3
Exécution d’un automate à états finis
Un automate à états finis s’exécute sur une machine qui se compose de :
1 Un ruban d’entrée divisé en cases dont chacune contient un seul symbole du
mot à reconnaı̂tre. Les autres cases contiennent des ϵ
2 Une tête de lecture qui se déplace de gauche vers la droite en pointant la case
du symbole à lire du mot d’entrée.
3 Un contrôleur d’états qui donne l’état qui suit létat courant en fonction du symble
lu.
Cette machine fonctionne comme suit :
Au départ l’état courant du controleur de la machine est l’état initial de
l’automate et le mot d’entrée est placé sur le ruban. La tête de lecture pointe la
première case contenant le premier symbole du mot d’entrée.
À chaque étape de l’exécution de l’automate, la machine lit un symbole du
ruban, détermine l’état suivant au moyen de la transition courante puis avance la
tête de lecture vers la case suivante du ruban.
La machine s’arrête lorsque tous les symboles ont été lus. Le mot est accepté si
la machine se trouve alors dans un état final de l’automate.
Yousra Hlaoui (FST-DSI) Automates à états finis 4/1
 Introduction

Introduction 3/3

Exemple d’exécution d’un autoamte

Machine

État courant= p ... ... ... a b ... ...

a
p q Contrôleur p

Automate

État courant= q ... ... ... a b ... ...

Contrôleur q

Yousra Hlaoui (FST-DSI) Automates à états finis 5/1

 Automates à états finis

Automates à états finis

Définition Formelle
Un automate à états finis est donné par (S, Σ, δ, s0 , SF ) où :
S est un ensemble fini d’états ;
Σ est un alphabet fini ;
δ : S × Σ → S est la fonction de transitions ;
s0 est l’état initial ;
SF est l’ensemble des états finaux.

Exemple
Représentation graphique d’un automate fini Définition formelle
b b
a S = {s0 , s1 , s2 } ;
a Σ = {a, b} ;
s0 s1 s2 δ(s0 , a) = s1 , δ(s0 , b) = s0 ,
a
δ(s1 , a) = s2 , δ(s1 , b) = s1 ,
δ(s2 , a) = s1 , δ(s2 , b) = s0 ;
b s0 est l’état initial ;
SF = {s0 , s2 }.

Yousra Hlaoui (FST-DSI) Automates à états finis 6/1

 Automates à états finis

Automates finis : Exemples

Exemple 1
Un automate fini qui accepte le langage {a}∗ .
a

s0

Exemple 2
Un automate fini qui accepte le langage {a}+ .
a

a
s0 s1

Yousra Hlaoui (FST-DSI) Automates à états finis 7/1

 Automates à états finis

Automates finis : Exemples

Exemple 3
Un automate fini qui accepte le langage {aa}∗ ou
{ω ∈ {a}∗ /|ω| = 2k, k ≥ 0}.
a

s0 s1
a

Exemple 4
Un automate fini qui accepte le langage {aaa}∗ aa ou
{ω ∈ {a}∗ /|ω| = 3k + 2, k ≥ 0}
a a
s0 s1 s2

Yousra Hlaoui (FST-DSI) Automates à états finis 8/1

 Automates à états finis

Automates finis : Exemples

Exemple 5
Un automate acceptant {ω ∈ {a, b}∗ /|ω|a = 3k + 2, k ≥ 0}

b b b

a a
s0 s1 s2

Exemple 6
Un automate fini acceptant {ω ∈ {a, b, c}∗ ayant aba comme facteur}

b, c a a, b, c

a b a
s0 s1 s2 s2
c
b, c

Yousra Hlaoui (FST-DSI) Automates à états finis 9/1

 Automates à états finis

Configuration d’un automate fini

Définition (Configuration)
Une configuration d’un automate fini représente l’information nécessaire pour
déterminer son évolution future.
Elle se compose d’une paire reprenant l’état dans lequel l’automate se trouve et
la partie du mot d’entrée restant à lire.
Formellement, une configuration est donc un élément (q, ω) ∈ S × Σ∗ .

Exemple : Configuration d’un automate

b b

a a
q0 q1 q2 (1) Les configurations pour le mot aa
(q0 , aa), (q1 , a), (q2 , ε)
b (2) Les configurations pour le mot bba
(q0 , bba), (q0 , ba), (q0 , a), (q1 , ε)

Yousra Hlaoui (FST-DSI) Automates à états finis 10 / 1

 Automates à états finis

Configuration d’un automate fini

Définition (Configuration successeur)

La configuration (q ′ , ω ′ ) qui est dérivable en une étape (dite aussi successeur) de la
configuration (q, ω) par l’automate M est notée par (q, ω) ⊢M (q ′ , ω ′ ) si :
ω = aω ′ .
q ′ = δ(q, a) .

Exemple : Configuration successeur d’un automate

b b

a a
q0 q1 q2
(1) (q0 , aa) ⊢ (q1 , a) ⊢ (q 2 , ε)
b (2) (q0 , bba) ⊢ (q0 , ba) ⊢ (q0 , a) ⊢ (q1 , ε)

Yousra Hlaoui (FST-DSI) Automates à états finis 11 / 1

 Automates à états finis

Configuration d’un automate fini

Définition (Configuration k i ème successeur d’un automate)
La configuration (q ′ , ω ′ ) qui est k i ème successeur de la configuration (q, ω) par
l’automate M est notée par (q, ω) ⊢∗M (q ′ , ω ′ ) si :
il existe k ≥ 0 et des configurations (qi , ωi ), 0 ≤ i ≤ k telles que :
(q, ω) = (q0 , ω0 ),
(q ′ , ω ′ ) = (qk , ωk ),
pour tout i, 0 ≤ i ≤ k, (qi , ωi ) ⊢M (qi+1 , ωi+1 )

Exemple : Configuration k i ème successeur d’un automate

A b b

a a (1) (q0 , aa) ⊢∗A (q2 , ε) puisque ∃k ≥ 0,

q0 q1 q2
(q0 , aa) ⊢kA (q2 , ε), avec k = 2
d’où on a (q0 , aa) ⊢A (q1 , a) ⊢A (q2 , ε).
b (2) (q0 , bba) ⊢3A (q1 , ε). En effet :
(q0 , bba) ⊢A (q0 , ba) ⊢A (q0 , a) ⊢A (q1 , ε)

Yousra Hlaoui (FST-DSI) Automates à états finis 12 / 1

 Automates à états finis

Configuration d’un automate fini

Définition (Exécution d’un automate)

L’exécution d’un automate A = (S, Σ, δ, s, SF ) sur un mot ω est la suite de
configurations (s, w) ⊢M (q1 , ω1 ) ⊢M (q2 , ω2 ) ⊢M . . . ⊢M (qn , ε).

Définition (Acceptation d’un mot)

Un mot accepté par un automate M si (s, ω) ⊢∗M (q, ε) où q ∈ SF

Définition (Acceptation d’un langage)

Le langage accepté par un automate M est l’ensemble des mots L(M) tel que :
L(M) = {ω ∈ Σ∗ /(s, ω) ⊢∗M (q, ε) avec q ∈ F }

Yousra Hlaoui (FST-DSI) Automates à états finis 13 / 1

 Automates à états finis

Configuration d’un automate fini

Exemple : Mot d’un langage accepté par un automate fini

b b b

a a
q0 q1 q2

1 aa ∈ L(A) par ce que : (q0 , aa) ⊢2A (q2 , ε) puisque (q0 , aa) ⊢A (q1 , a) ⊢kA (q2 , ε),
avec q2 ∈ F .
2 bba ∈ / L(A) par ce que : ∄k /(q0 , bba) ⊢kA (q2 , ε). En effet :
(q0 , bba) ⊢A (q0 , ba) ⊢A (q0 , a) ⊢A (q1 , ε) avec q1 ∈
/ SF

Yousra Hlaoui (FST-DSI) Automates à états finis 14 / 1

 Automates à états finis

Langage accepté par un automate fini

Exercice
Soit l’automate A suivant :

b b b

a a
q0 q1 q2

Questions :
1 Quel est le langage reconnu par l’automate A ?
2 Est-ce que le mot ε est accepté par A ?

Yousra Hlaoui (FST-DSI) Automates à états finis 15 / 1

 Automates à états finis

Langage accepté par un automate fini

Exercice
Soit l’automate A suivant :

b b b

a a
q0 q1 q2

Réponse :
1 L(A) = {ω ∈ {a, b}∗ /|ω|a = 3k + 2, k ≥ 0} ∪ {ω ∈ {a, b}∗ /|ω|a = 3k , k ≥ 0}
2 ε ∈ L(A) car (q0 ∈ SF et (q0 , ε) est une configuration finale et initiale.

Yousra Hlaoui (FST-DSI) Automates à états finis 16 / 1

 Automates à états finis

Automates Déterministes

Définition (Automate Déterministe)

Un automate fini (S, Σ, δ, s0 , SF ) est déterministe si :
il a un unique état initial s0 ;
il existe deux transitions (p, a, q) et (p, a, q ′ ) de δ alors q = q ′

Exemple : Automate Déterministe et Automate non Déterministe

b b
a a, b a, b
q0 q1
a
q0 q1 q2
a b
Automate Déterministe Automate Non Déterministe

Yousra Hlaoui (FST-DSI) Automates à états finis 17 / 1

 Automates à états finis

Automate Complet
Définition
Un automate fini sur l’alphabet Σ est dit complet ssi pour chaque symbole a de Σ et
chaque état q, il existe au moins une transition étiquetée par a qui quitte q.

Exemple : Automate non complet sur {a, b} car δ(q0 , b) = ∅

a, b

a
q0 q1

Remarque
On peut toujours compléter un automate en ajoutant un état puit dans lequel vont
aller toutes les transitions non prévues.

Exemple : Rendre complet l’automate précédent en lui ajoutant l’état puit ∅

a, b a, b

b a
∅ q0 q1

Yousra Hlaoui (FST-DSI) Automates à états finis 18 / 1

 Automates à états finis

Automate non ambiguë

Définition
Un automate fini sur l’alphabet Σ est dit non ambiguë si pour chaque état q et
chaque symbole a ∈ Σ, il existe au plus une transition qui quitte q étiquetée par a.

Exemple d’un automate ambiguë

a a, b
a
q0 q1

Automate ambiguë sur {a, b} car δ(q0 , a) = {q0 , q1 } et δ(q1 , b) = {q0 , q1 } :

- deux transitions quittant q0 étiquetées par a, et
- deux transitions quittant q1 étiquetées par b.

Remarque
Un automate complet et non ambiguë, il est déterministe

Yousra Hlaoui (FST-DSI) Automates à états finis 19 / 1

 Automates finis non déterministes

Automates finis non déterministes

Ils sont plus faciles à construire. La construction d’un automate non déterministe
peut être automatisée à partir d’une expression régulière
Pour certains langages, on ne peut avoir que des machines non déterministes
pour les reconnaı̂tre.

Description
Les automates finis non déterministes sont des automates finis où l’on permet :
Plusieurs transitions étiquetées par la même lettre quittent certains états,
Des transitions sur le mot vide (c’est-à-dire sans avancer dans le mot d’entrée)
des transitions sur des mots de longueur supérieure à 1 (regroupement de
transitions)

Remarque
Dans un automate fini non déterministe, la relation de transition n’est pas
nécessairement totale : il n’est pas complet.

Yousra Hlaoui (FST-DSI) Automates à états finis 20 / 1

 Automates finis non déterministes

Automate fini non déterministe

Définition
Un Automate Fini Non Déterministe (AFND) est défini par M = (S, Σ, ∆, s, SF ), avec :
S est un ensemble fini d’états,
Σ est un alphabet,
∆ ⊂ (S × Σ∗ × S) (sous-ensemble fini) est la relation de transitions,
s0 ∈ S est l’état initial,
SF ⊆ S est l’ensemble des états accepteurs.

Exemple d’un AFDN reconnaissant L(M) = (a + b)∗ a+ b(ab)∗

M a,b a ab
M = (S, Σ, ∆, s, SF ), avec :
q0
a
q1
b
q2
S = {q0 , q1 , q2 }, Σ = {a, b},
∆ = {(q0 , a, q0 ), (q0 , b, q0 ), (q0 , a, q1 ),
(q1 , a, q1 ), (q1 , b, q2 ), (q2 , ab, q2 )},
s0 = q0 , SF = {q2 }

Yousra Hlaoui (FST-DSI) Automates à états finis 21 / 1

 Automates finis non déterministes

Automates finis non déterministes

Définition (Configuration AFN)
La configuration (q ′ , ω ′ ) est dérivable en une étape de la configuration (q, ω) par
l’automate M ((q, ω) ⊢M (q ′ , ω ′ )) si :
ω = u ω ′ ( le mot ω commence par un préfixe u ∈ Σ∗ ),
(q, u, q ′ ) in ∆ ( le triplet (q, u, q ′ ) est dans la relation de transitions ∆)

Définition (Mot accepté)

Un mot ω est accepté par un AFND M = (S, Σ, ∆, s, SF ) s’il existe une configuration
ki éme successeur : (s, ω) ⊢∗M (q, ε), avec q état accepteur.

Propriétés
Si M est non déterministe alors :
1 ∃ ω ∈ Σ∗ possédant au moins deux exécutions différentes ou,
2 ∃ ω ∈ Σ∗ pour lequel nous avons un blocage c.a.d : (s, ω) ⊢∗M (q, ω ′ ), avec
ω ′ ̸= ε et la configuration (q, ω) n’a pas de configuration successeur.

Yousra Hlaoui (FST-DSI) Automates à états finis 22 / 1

 Automates finis non déterministes élimination du non déterminisme

élimination du non déterminisme

Le non-déterminisme n’ajoute rien à la capacité des automates finis. Nous allons
prouver, alors, que nous pouvons toujours remplacer un AFND par un AFD
équivalent.

Définition
Deux automates M1 et M2 sont équivalents s’ils acceptent le même langage,
c’est à dire L(M1 ) = L(M2 ).

Théorème
Pour tout automate fini non déterministe, il est possible de construire un
automate fini déterministe équivalent

Principe de la construction
On peut toujours remplacer un automate non déterministe par un autre
déterministe équivalent en :
1 éliminant les transitions sur des mots de longueurs supérieure à 1,
2 éliminant les transitions sur le mot vide ainsi que les transitions non
exclusives qui causent le non-déterminisme.

Yousra Hlaoui (FST-DSI) Automates à états finis 23 / 1

 Automates finis non déterministes élimination du non déterminisme

élimination du non déterminisme

1. élimination des transitions de longueur > 1

éclater la transition sur le mot de longueur n > 1 en n transitions.

aba a b a
q1 q2 ⇒ q0 q1 q2 q3

2. élimination du non-déterminisme
Correspondre chaque état de l’automate déterministe à un ensemble d’états
de l’automate non-déterministe.

q1 {q0 , q1 }
a a a

q0 ⇒ {q0 }
b b

q2 {q2 }

Yousra Hlaoui (FST-DSI) Automates à états finis 24 / 1

 Automates finis non déterministes élimination du non déterminisme

Formalisation de la construction
Soit un automate non déterministe M = (S, Σ, ∆, s, SF ), construisons un automate
déterministe M ′ = (S ′ , Σ, δ ′ , s′ , SF′ ) équivalent à M. Définissons les éléments de
l’automate M ′ .
1. élimination des transitions sur les mots de longueur > 1
M ′ = (S ′ , Σ, ∆′ , s′ , SF′ ) ne contient pas des transitions sur des mots de longueur > 1 :

∀ (q, u, q ′ ) ∈ ∆′ , |u| ≤ 1

Les ensembles S ′ et ∆′ sont obtenus de ceux de l’automate M comme suit :

Initialement S ′ = S et ∆′ = ∆.
Pour chaque transition (q, u, q ′ ) ∈ ∆ avec u = u1 , u2 , . . . , uk , (k > 1),
uk ∈ Σ :
on enlève cette transition de ∆′ ,
on ajoute de nouveaux états p1 , . . . , pk−1 à S ′ ,
on ajoute les nouvelles transitions (q, u1 , p1 ), (p1 , u2 , p2 ),. . . ,
(pk−1 , uk , q ′ ),à ∆′ ,

Yousra Hlaoui (FST-DSI) Automates à états finis 25 / 1

 Automates finis non déterministes élimination du non déterminisme

Formalisation de la construction
2. élimination du non-déterminisme
L’idée est de regrouper toute suite de transitions sur le mot ε avec une transitions sur
un élément de Σ afin d’éliminer les transitions sur ε. Soit E(q) l’ensemble des états p
qui peuvent être atteints à partir d’un état q d’un automate M à travers des transitions
étiquetées par ε.
E(q) = {p ∈ S | (q, ω) ⊢∗M (p, ω)}.
Les éléments de l’automate M ′ déterministe sont :
1 L’ensemble des états S ′ = 2S de M ′ est l’ensemble des sous-ensembles des
états de M. Chaque état de l’automate déterministe correspond à un ensemble
d’états de l’automate non déterministe.
2 L’état initial s′ de M ′ est s′ = E(s), où s est l’état initial de M.
3 La fonction de transition δ ′ doit regrouper les transitions possibles de M. δ ′ (q, a)
sera l’ensemble des états qui, dans M, peuvent être atteints à partir d’un des
états qi ∈ q par une suite de transitions dont la première est étiquetée par
a ∈ Σ et les suivantes par le mot ε.
Ainsi δ ′ (q, a) = {E(p)/∃qi ∈ q : (qi , a, p) ∈ ∆}
S

4 Un état de l’automate déterministe M ′ sera accepteur s’il contient un état

accepteur de M. SF′ sera alors :SF′ = {q ∈ S ′ | q ∩ SF ̸= ∅}
Yousra Hlaoui (FST-DSI) Automates à états finis 26 / 1
 Automates finis non déterministes élimination du non déterminisme

Algorithme d’élimination du non-déterministe

Donnée : Un AFN AN
Résultat : Un AFD AD
Méthode :
On construit une table de transition TransD pour AD, où chaque état de AD est
un ensemble d’états, D état de DN. TransD est la table de transitions de AD où
les lignes sont les super-états de D état et les colonnes ssont les symboles de Σ.
Pour ce faire :
on regroupe les états reliés par des ε − transitions en utilisant les
opérations :
1 ε − fermeture(e) qui fournit l’ensemble T des états de AN

accessibles depuis l’état e de AN par des ε − transitions uniquement.

T et un super-état.
2 ε − fermeture(T ) qui fournit l’ensemble des états de AN accessibles

depuis l’état e de l’ensemble T par des ε − transitions uniquement.

on regroupe toutes les transitions étiquetées par un même symbole
quittant un même état de AN afin d’éliminer le non déterminisme en
utilisant l’opération suivante :
Transiter (T , a) qui produit des états de AN vers lesquels il existe une
transition sur le symbole a de l’alphabet à partir d’un état e de T .
Yousra Hlaoui (FST-DSI) Automates à états finis 27 / 1
 Automates finis non déterministes élimination du non déterminisme

Algorithme d’élimination du non-déterministe

Construction des super-états

1 Début
2 D états := ∅
3 Appliquer ε − fermeture(e) sur l’état initial, e = s0
4 T := ε − fermeture(s0 )
5 D états := D états ∪ T
6 PourChaque symbole a De Σ Faire
7 U := ε − fermeture(Transiter (T , a));
8 Si U n’appartient pas à D états Alors
9 ajouter U comme super-état à D états
10 TransD[T , a] := U
11 FinSi
12 FinPour
13 Fin

Yousra Hlaoui (FST-DSI) Automates à états finis 28 / 1

 Automates finis non déterministes élimination du non déterminisme

Algorithme d’élimination du non-déterministe

Calcul de ε − fermeture(T )

1 Début
2 PourChaque état e De T Faire
3 PourChaque état s avec ε-transition De e Faire
4 Si si s n’est pas dans ε − fermeture(e) Alors
5 ajouter s à ε − fermeture(e)
6 appliquer ε − fermeture(s)
7 FinSi
8 FinPour
9 FinPour
10 Fin

Yousra Hlaoui (FST-DSI) Automates à états finis 29 / 1

 Automates finis non déterministes élimination du non déterminisme

Application de la méthode
Rendre déterministe l’automate M 1. élimination des transitions de longueur > 1
a a

ab a b
1 2 1 2′ 2
M ε ε

0 0

ε ε
3 4 3 4
c c

a c a c

2. élimination du non-déterminisme Automate M ′ déterministe résultant

M′ a
Etat a b c
a b
A = {0, 1, 3} {1, 3, 2′ } ∅ {4} A B C

B = {1, 3, 2′ } {1, 3, 2′ } {2} {4}

c c
C = {2} ∅ ∅ ∅
D = {4} ∅ ∅ {4} D c
E =∅ ∅ ∅ ∅ b a, b, c
a, b

a, b, c

Yousra Hlaoui (FST-DSI) Automates à états finis 30 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Minimalisation du nombre d’états d’un AFD

Un automate optimale est un automate déterministe ayant un nombre minimal d’états.

Soit A un automate fini déterministe A = (S, Σ, δ, s, SF ) à rendre optimal. Il suffit,

alors, de minimaliser son nombre d’états ; rendre minimal |S|. Pour obtenir un
automate A minimal en nombre d’états, il faut suivre les étapes suivantes :
1 Construire une partition initiale Π0 composée de deux groupes : Groupe des
états finaux G1 et Groupe des états non finaux G2
2 Répéter Jusqu’à Πi+1 = Πi /i ≥ 0 Pour obtenir Πi+1 , partitionner chaque groupe
de Πi en mettant ensemble des états p et q si pour chaque symbole s du
vocabulaire, p et q transitent par s vers des états du même groupe d’états de Πi .
Construire les nouveaux groupes
3 Associer à chaque groupe un nom et construire les transitions des groupes en
utilisant les transitions des états des groupes.
4 Un groupe qui contient un état final est un état final dans l’automate minimal

Théorème
L’automate optimal est unique à un renommage d’état près.

Yousra Hlaoui (FST-DSI) Automates à états finis 31 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Application de la minimalisation

Minimaliser le nombre d’états de l’automate M suivant :

b
M
C b
b
a

a b b
A B D E
a
a
a

Processus de Minimalisation de A :
G1 G2
Π0
(ABCD) (E)

Yousra Hlaoui (FST-DSI) Automates à états finis 32 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Application de la minimalisation

Minimaliser le nombre d’états de l’automate M suivant :

b
M
C b
b
a

a b b
A B D E
a
a
a

Processus de Minimalisation de A :
G1 G2
Π0
(ABCD) (E)
G1 G2
Π1 (E)
(ABC) (D)

Yousra Hlaoui (FST-DSI) Automates à états finis 32 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Application de la minimalisation
Minimaliser le nombre d’états de l’automate M suivant :
b
M
C b
b
a

a b b
A B D E
a
a
a

Processus de Minimalisation de A :
G1 G2
Π0
(ABCD) (E)
G1 G2
Π1 (E)
(ABC) (D)
G1 G2
Π2 (D)(E)
(A, C) (B)

Yousra Hlaoui (FST-DSI) Automates à états finis 32 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Application de la minimalisation
Minimaliser le nombre d’états de l’automate M suivant :
b
M
C b
b
a

a b b
A B D E
a
a
a

Processus de Minimalisation de A :
G1 G2
Π0
(ABCD) (E)
G1 G2
Π1 (E)
(ABC) (D)
G1 G2
Π2 (D)(E)
(A, C) (B)
G1 G2
Π3 (D)(E)
(AC) (B)

Yousra Hlaoui (FST-DSI) Automates à états finis 32 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Application de la minimalisation
Minimaliser le nombre d’états de l’automate M suivant :
b
M
C b
b
a

a b b
A B D E
a
a
a

Processus de Minimalisation de A :
G1 G2
Π0
(ABCD) (E)
G1 G2
Π1 (E)
(ABC) (D)
G1 G2
Π2 (D)(E)
(A, C) (B)
A B D E

Yousra Hlaoui (FST-DSI) Automates à états finis 32 / 1

 Automates finis non déterministes Minimalisation du nombre d’états d’un AFD

Application de la minimalisation
Minimaliser le nombre d’états de l’automate M suivant :
b
M
C b
b
a

a b b
A B D E
a
a
a

Processus de Minimalisation de A :
b a
G1 G2 ′
Π0 M
a
(ABCD) (E) A B
G1 G2 a
Π1 (E) a
(ABC) (D) b b

G1 G2
Π2 (D)(E) E D
(A, C) (B) b

A B D E
′
On obtient l’automate M minimal, avec :

Yousra Hlaoui (FST-DSI) Automates à états finis 32 / 1

 Automates finis et Langages Réguliers

Automates finis et Langages Réguliers

Pour décrire un langage, nous avons présenté deux formalismes de natures
différentes :
1 Les expressions régulières qui sont basées sur la description d’ensembles de

mots à partir d’ensembles élémentaires et des opérations sur ces ensembles.

2 Les automates qui définissent les langages de manière opérationnelle en

fournissant un mécanisme de reconnaissance de ces langages.

Bien qu’ils soient différents, les deux formalismes définissent la même classe de
langages :
Théorème
Un langage L est dit régulier si et seulement si il existe un automate fini A qui
l’accepte (L(A) = L)

Lemme 1
Si un langage est dénoté par une expression régulière, il est accepté par un automate
fini non déterministe.

Lemme 2
Si un langage est accepté par un automate fini non déterministe, il est régulier.
Yousra Hlaoui (FST-DSI) Automates à états finis 33 / 1
 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 1
Si L1 et L2 sont des langages réguliers alors L1 + L2 est un langage régulier.

Preuve
Pour montrer que L1 + L2 est un langage régulier, il suffit de construire un automate fini
qui accepte L1 + L2 à partir des automates finis qui acceptent respectivement L1 et L2
Soient A1 = (S1 , Σ1 , ∆1 , s01 , SF1 )/L(A1 ) = L1 et A2 = (S2 , Σ2 , ∆2 , s02 , SF2 )/L(A2 ) = L2
On construit A = (S, Σ, ∆, s0 , SF )/L(A) = L1 + L2 comme suit :
S = S1 ∪ S2 ∪ {s0 }
Σ = Σ1 ∪ Σ2
∆ = ∆1 ∪ ∆2 ∪ {(s0 , x, q)/(s01 , x, q) ∈ ∆1 ou (s02 , x, q) ∈ ∆2 }
SF = SF1 ∪ SF2 ∪ {s0 } si s01 ∈ SF1 ou s02 ∈ SF2
SF1 ∪ SF2 sinon
.

Yousra Hlaoui (FST-DSI) Automates à états finis 34 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L(A1) + L(A2)

L(A) = L1 + L2 = L(A1 ) + L(A2 )
L1 = L(A1 ) a a, b
a a, b
a
A1 q01 q1
a a
q01 q1
A a
q0 a, b
L2 = L(A2 )
b b
A2 a, b
a, b q02 q2
q02 q2

Yousra Hlaoui (FST-DSI) Automates à états finis 35 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 2
Si L1 et L2 sont des langages réguliers alors L1 .L2 est un langage régulier.

Preuve
Pour montrer que L1 .L2 est un langage régulier, il suffit de construire un automate fini
qui accepte L1 .L2 à partir des automates finis qui acceptent respectivement L1 et L2 .
Soient A1 = (S1 , Σ1 , ∆1 , s01 , SF1 )/L(A1 ) = L1 et A2 = (S2 , Σ2 , ∆2 , s02 , SF2 )/L(A2 ) = L2
On construit A = (S, Σ, ∆, s0 , SF )/L(A) = L1 .L2
S = S1 ∪ S2
Σ = Σ1 ∪ Σ2
s0 = s01
∆ = ∆1 ∪ ∆2 ∪ {(p, x, q)/p ∈ SF1 et (s02 , x, q) ∈ ∆2 }
SF = SF1 ∪ SF2 si q02 ∈ SF2
SF = SF2 sinon

Yousra Hlaoui (FST-DSI) Automates à états finis 36 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L(A1) . L(A2)
SF = SF1 ∪ SF2 puisque q02 ∈ SF2
L1 = L(A1 ) L2 = L(A2 )
a a, b b
A1 A2
a a, b
q01 q1 q02 q2

L(A) = L1 . L2 = L(A1 ) . L(A2 )

a a, b b
A
a b a, b
q01 q1 q02 q2

a, b
b
a, b

Yousra Hlaoui (FST-DSI) Automates à états finis 37 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L(A1) . L(A2)
SF = SF2 puisque q02 ∈
/ SF2
L1 = L(A1 ) L2 = L(A2 )
a a, b b
A1 A2
a a, b
q01 q1 q02 q2

L(A) = L1 . L2 = L(A1 ) . L(A2 )

a a, b b
A
a b a, b
q01 q1 q02 q2

a, b
b
a, b

Yousra Hlaoui (FST-DSI) Automates à états finis 37 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 3
Si L est un langage régulier alors L∗ est un langage régulier.

Preuve
Pour prouver que L∗ est un langage régulier, il suffit de construction un automate
reconnaissant L∗ à partir de l’automate fini qui accepte L.
Soit A1 = (S1 , Σ1 , ∆1 , s01 , SF1 )/L(A1 ) = L1
On construit A = (S, Σ, ∆, s0 , SF )/L(A) = L∗1
S = S1 ∪ {s0 }
Σ = Σ1
∆ = ∆1 ∪ {(s0 , x, q)/(s01 , x, q) ∈ ∆1 } ∪ {(sf , x, q)/(s01 , x, q) ∈ ∆1 et sf ∈ SF1 }
SF = SF1 ∪ {s0 }

Yousra Hlaoui (FST-DSI) Automates à états finis 38 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L∗

L1 = L(A1 ) L(A) = (L1 )∗
a b
A
a b
a q0 q01 q1
a a a
A1
b b
q01 q1

On ajoute (q0 , a, q01 ) et (q0 , b, q1 ) à ∆ puisque (q01 , a, q01 ) et (q01 , b, q1 ) sont

dans ∆1 .
On ajoute (q1 , a, q01 ) et (q1 , b, q1 ) à ∆ puisque (q01 , a, q01 ) et (q01 , b, q1 ) sont
dans ∆1
L(A1 ) = a∗ ba∗ et L(A) = (L(A1 ))∗ = (a∗ ba∗ )∗ .

Yousra Hlaoui (FST-DSI) Automates à états finis 39 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 4
Si L est un langage régulier alors L+ est un langage régulier.

Preuve
Pour prouver que L+ est un langage régulier, il suffit de construire un automate
reconnaissant L+ à partir de l’automate fini qui accepte L.
Soit A1 = (S1 , Σ1 , ∆1 , s01 , SF1 )/L(A1 ) = L1
On construit A = (S, Σ, ∆, s0 , SF )/L(A) = L+ 1

S = S1 ∪ {s0 }
Σ = Σ1
∆ = ∆1 ∪ {(s0 , x, q)/(s01 , x, q) ∈ ∆1 } ∪ {(sf , x, q)/(s01 , x, q) ∈ ∆1 et sf ∈ SF1 }
SF = SF1

Yousra Hlaoui (FST-DSI) Automates à états finis 40 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L+

L1 = L(A1 ) L(A) = (L1 )+
a b
A
a b
a q0 q01 q1
a a a
A1
b b
q01 q1

On ajoute (q0 , a, q01 ) et (q0 , b, q1 ) à ∆ puisque (q01 , a, q01 ) et (q01 , b, q1 ) sont

dans ∆1 .
On ajoute (q1 , a, q01 ) et (q1 , b, q1 ) à ∆ puisque (q01 , a, q01 ) et (q01 , b, q1 ) sont
dans ∆1
L(A1 ) = a∗ ba∗ et L(A) = (L(A1 ))+ = (a∗ ba∗ )+ .

Yousra Hlaoui (FST-DSI) Automates à états finis 41 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 5
Si L est un langage régulier alors LR est un langage régulier.

LR = {ω | ω R ∈ L}, ω R est le mot inverse de ω

Preuve
Pour prouver que LR est un langage régulier, il suffit de construire un automate
reconnaissant LR à partir de l’automate fini qui accepte L.
Soit A1 = (S1 , Σ1 , ∆1 , s01 , SF1 )/L(A1 ) = L1
On construit A = (S, Σ, ∆, s0 , SF )/L(A) = LR1
S = S1 ∪ {s0 }
Σ = Σ1
∆ = {(q, x, p)/(p, x, q) ∈ ∆1 } ∪ {(s0 , ε, q) | q ∈ SF1 } (les transitions sont celles
de A1 inversées plus une transition du nouvel état initial vers chaque état final de
A1 ).
SF = {s01 }

Yousra Hlaoui (FST-DSI) Automates à états finis 42 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant LR

a a
A1
b a
q01 q1 q2

Automate reconnaissant L

a a
A
ε a b
q0 q2 q1 q01

Automate reconnaissant LR

Yousra Hlaoui (FST-DSI) Automates à états finis 43 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 6
Si L est un langage régulier alors L (complément de L) est un langage régulier.

Preuve
Pour prouver que L est un langage régulier, il suffit de construire un automate
reconnaissant L à partir d’un automate fini déterministe qui accepte L.
Soit A1 = (S1 , Σ1 , ∆1 , s01 , SF1 )/L(A1 ) = L1
On construit A = (S, Σ, ∆, s0 , SF )/L(A) = L1
S = S1
Σ = Σ1
∆ = ∆1
SF = S − SF1 (on permute les états accepteurs et non accepteurs de A1 )

Yousra Hlaoui (FST-DSI) Automates à états finis 44 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L

a a
A1
b a
q01 q1 q2

Automate reconnaissant L

a a
A
b a
q01 q1 q2

Automate reconnaissant L

Yousra Hlaoui (FST-DSI) Automates à états finis 45 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Propriété 7
Si L1 et L2 sont deux langages réguliers alors L1 ∩ L2 est un langage régulier.

Preuve
Pour prouver que L1 ∩ L2 est un langage régulier, il suffit simplement de construire un
automate déterministe A = (S, Σ, ∆, s0 , SF ) reconnaissant L1 ∩ L2 à partir des
automates déterministes A1 = (S1 , Σ, δ1 , s01 , SF1 ) et A2 = (S2 , Σ, δ2 , s02 , SF2 )
acceptant respectivement L1 et L2 .
L’automate A simule, simultanément, l’exécution des automates A1 et A2 et accepte
quand ces deux automates acceptent.
On construit A = (S, Σ, δ, s0 , SF )/L(A) = L(A1 ) ∩ L(A2 ).
S = S1 × S2
δ((q1 , q2 ), x) = (p1 , p2 ), x ∈ Σ ssi δ1 (q1 , x) = p1 et δ2 (q2 , x) = p2
s0 = (s01 , s02 )
SF = SF1 × SF2 .

Yousra Hlaoui (FST-DSI) Automates à états finis 46 / 1

 Automates finis et Langages Réguliers Propriétés des langages réguliers (LR)

Propriétés des langages réguliers (LR)

Exercice : Construire A reconnaissant L1 ∩ L2

a b a, b

A1 A2
b a a
q01 q11 q21 q02 q12

Automate acceptant L1 Automate acceptant L2

L1 = { mots se terminant par ba}. L2 = { mots commençant par a}.

a b
A
a b a
(q01 , q02 ) (q01 , q12 ) (q11 , q12 ) (q21 , q12 )

S = {(q01 , q02 ), (q01 , q12 ), (q11 , q12 ), (q21 , q12 )}

s0 = (q01 , q02 )
SF = {(q21 , q12 )}
L(A) = { mots commençant par a et se terminant par ba}

Yousra Hlaoui (FST-DSI) Automates à états finis 47 / 1

 Automates finis et Langages Réguliers Des expression régulières aux automates

Des expression régulières aux automates

On construit un automate fini non-déterministe à partir d’une expression régulière en
appliquant l’algorithme de Thompson.

Algorithme de Thompson
Entrée : Expression régulière E,
Sortie : Automate non-déterministe A,
L’algorithme de Thompson est dirigé par la syntaxe de l’expression en entrée. Il
est récursif sur la structure syntaxique de l’expression régulière E en entrée.
L’automate A est construit avec des ε−transitions par induction sur la structure
de l’expression E.
Pour chaque motif de l’expression régulière, définir un AFN, en allant des
motifs de base vers les motifs inductifs plus complexes.
Motifs de base : ∅, ε, a ∈ Σ
Motifs inductifs : (α), α1 . α2 , α1 + α2 , α∗ , où α1 , α2 et α sont des
expressions régulières.
Pour chaque état ajouté, donner un nom différent des noms des états déjà
créés.

Yousra Hlaoui (FST-DSI) Automates à états finis 48 / 1

 Automates finis et Langages Réguliers Des expression régulières aux automates

Correspondance Expressions régulières et AFN

Cas de Base
Expression Régulière AFN correspondant
p
∅
ε
p q
ε
a
p q
a

Cas Inductifs
Expression Régulière AFN correspondant
aaaαaaaaaaa
(α)
α1 aaaaaaa aaaaα2 aaaaa
α1 .α2 .

Yousra Hlaoui (FST-DSI) Automates à états finis 49 / 1

 Automates finis et Langages Réguliers Des expression régulières aux automates

Correspondance Expressions régulières et AFN

Cas Inductifs - Suite
Expression Régulière AFN correspondant
Aaaaaa
ε ε

p q
ε ε
Baaaaa
α1 + α2
ε

p
ε ε
q
aaaaaaa
ε
α∗

Théoreme
Étant donnée une expression régulière E, il existe un unique automate d’états fini
optimal M (à un renommage d’état près) tel que L(M) = E.

Yousra Hlaoui (FST-DSI) Automates à états finis 50 / 1

 Automates finis et Langages Réguliers Des expression régulières aux automates

Algorithme de Thompson - Illustration

Construire l’AFN de l’expression (1 + 0)∗ . 1

Arbre syntaxique décomposant (1 + 0)∗ . 1
r6

r5 . 1

∗ r4

( r3 )

r1 + r2

1 0

l’AFN correspondant :
ε
M
1
ε C E ε
ε 1
A B G ε H I
ε 0 ε
D F
ε

Yousra Hlaoui (FST-DSI) Automates à états finis 51 / 1

 Automates finis et Langages Réguliers Des expression régulières aux automates

Rendre déterministe le AFD résultant

Rendre déterministe le AFN M fourni par l’algorithme de Thompson
ε − fermeture(A) = {A, B, C, D, H}
ε − fermeture(Transiter ({A, B, C, D, H}, 0)) = {F , G, B, C, D, H}
ε − fermeture(Transiter ({A, B, C, D, H}, 1)) = {E, G, B, C, D, H, I}
ε − fermeture(Transiter ({F , G, B, C, D, H}, 0)) = {F , G, B, C, D, H}
ε − fermeture(Transiter ({F , G, B, C, D, H}, 1)) = {E, G, B, C, D, H, I}
ε − fermeture(Transiter ({E, G, B, C, D, H, I}, 0)) = {F , G, B, C, D, H}
ε − fermeture(Transiter ({E, G, B, C, D, H, I}, 1)) = {E, G, B, C, D, H, I}
′
Le AFD correspondant M :
′
M 0

0
{A, B, C, D, H} {F , G, H, B, C, D}

0 1
1

{E, G, B, C, D, H, I}

Yousra Hlaoui (FST-DSI) Automates à états finis 52 / 1

 Automates finis et Langages Réguliers Des automates aux expressions régulières

Des automates aux expressions régulières

Lemme
Si un langage est accepté par un automate fini non déterministe, alors il est
régulier (dénoté par une expression régulière).

Définition d’un langage à partir d’un automate fini en utilisant le Lemme d’ARDEN
x qj
qi

Associer à chaque état de A un langage. Li et Lj sont les langages

reconnus respectivement par les états qi et qi .
Dresser les équations au niveau de chaque état, en ajoutant ε à
l’équation de chaque état d’acceptation : Li = xLj + {ε}.
Résoudre les équations dressées en utilisant le théorème d’Arden.

Yousra Hlaoui (FST-DSI) Automates à états finis 53 / 1

 Automates finis et Langages Réguliers Des automates aux expressions régulières

Des automates aux expressions régulières

Théorème d’Arden
Soient A et B deux langages, on définit l’équation E, d’inconnu L :

L = A L + B(E)

Alors les items suivants sont valides :

1 L0 = A∗ . B est solution de (E)
2 Toute solution de (E) contient L0 , et
3 Si ε ∈
/ A alors L0 est l’unique solution de (E).

Exemple
Si L = {a} L + {b}, alors L = {a}∗ {b}.
Si L = {a} L + ε, alors L = {a}∗ .

Yousra Hlaoui (FST-DSI) Automates à états finis 54 / 1

 Automates finis et Langages Réguliers Des automates aux expressions régulières

Langage accepté par un automate fini

Exercice illustratif 1
Soit A un automate fini sur un vocabulaire X = {a, b}. Chercher le langage L0
reconnu par l’automate A.

q0
a q1
a q2
A

Yousra Hlaoui (FST-DSI) Automates à états finis 55 / 1

 Automates finis et Langages Réguliers Des automates aux expressions régulières

Langage accepté par un automate fini

Exercice illustratif 1
Soit A un automate fini sur un vocabulaire X = {a, b}. Chercher le langage L0
reconnu par l’automate A.

q0
a q1
a q2
A

Exercice illustratif 1 - Corrigé

L0 = {a}L1 (1) L1 = {a}L2 (2) L2 = {a}L0 + {ε}(3)
(1)+ (2) ⇒ L0 = {a}{a}L2 = {aa}L2 (4)
(4) + (3)⇒ L0 = {aa}L2 = {aa}({a}L0 + {ε}) ⇒ L0 = {aaa}L0 + {aa}
D’après le lemme d’Arden ⇒ L0 = {aaa}∗ {aa} = (aaa)∗ aa.

Yousra Hlaoui (FST-DSI) Automates à états finis 55 / 1

 Automates finis et Langages Réguliers Des automates aux expressions régulières

Langage accepté par un automate fini

Exercice illustratif 2
Chercher le langage reconnu par l’automate A.

b a

q1
a q2
A

Yousra Hlaoui (FST-DSI) Automates à états finis 56 / 1

 Automates finis et Langages Réguliers Des automates aux expressions régulières

Langage accepté par un automate fini

Exercice illustratif 2
Chercher le langage reconnu par l’automate A.

b a

q1
a q2
A

Exercice illustratif 2 - Corrigé

L1 = {b}L1 + {a}L2 (1) L2 = {a}L2 + {b}L1 + {ε}(2) d’où :
d’après le lemme d’Arden : L2 = a∗ (bL1 + ε)
L1 = bL1 + aa∗ (bL1 + ε)
L1 = bL1 + aa∗ bL1 + aa∗
L1 = (b + a+ b)L1 + a+ d’après le théoreme d’Arden on aura :
L1 = (b + a+ b)∗ a+

Yousra Hlaoui (FST-DSI) Automates à états finis 56 / 1

 Limites des automates finis

Limites des automates finis

Les langages réguliers représentent une classe très intéressante de langages
mais cette classe ne représente pas tous les langages.
Tous les langages finis sont des langages réguliers :
L = {ω1 , ω2 , . . . , ωk } est le langage dénoté par l’expression régulière
ER = ω1 + ω2 + . . . + ωk
Si un langage est non régulier alors il doit être infini (la réciproque n’est pas
vraie) :
Σ∗ est régulier mais pas non régulier.
Tout langage régulier est accepté par un automate fini comportant un nombre
fixe d’états, soit m.
Soient L, un langage régulier infini, et M, un automate à m états, acceptant ce
langage. Pour tout mot ω, |ω| > m, l’exécution de l’automate sur ce mot doit
passer par un même état sk au moins deux fois avec une partie non vide du mot
séparant ces deux passages.
Tous les mots sont de la forme xu ∗ y ∈ L(M).
x u y
s sf
sk sk

Yousra Hlaoui (FST-DSI) Automates à états finis 57 / 1

 Limites des automates finis

Limites des automates finis

Remarque
Certains langages ne sont pas réguliers en établissant qu’ils ne peuvent pas satisfaire
cette propriété.

Pour établir la démonstration, nous donnons les théorèmes qui formalisent ces
observations.

Yousra Hlaoui (FST-DSI) Automates à états finis 58 / 1

 Limites des automates finis

Limites des automates finis

Théorème 1
Soit L ∈ LR un langage infini, alors il existe x, y , z ∈ Σ∗ , avec y ̸= ε tels que
∀n ≥ 0, xy n z ∈ L

Théorème 2 (Théorème de pompage ou de gonflement)

Soit M = (Q, X , d, i, F ) un automate fini déterministe et soit ω une chaı̂ne de
symboles de Σ tels que :
1 ω ∈ L(M) (L(M) est infini)
2 |ω| ≥ |Q|
alors il existe x, u et y tels que :
ω = xuy
u ̸= ε et |xu| ≤ |Q|
xu n y ∈ L(M), n ≥ 0

Yousra Hlaoui (FST-DSI) Automates à états finis 59 / 1

 Limites des automates finis

Limites des automates finis

Application des Théorèmes du gonflement

Le langage an bn est non régulier
Pour le démontrer il suffit de montrer qu’il n’existe pas de mots x, u, y tels
que xu k y ∈ an bn . Supposons l’existence de x, u, y que sera-t-il alors u :
u ∈ a∗ : impossible, car si on répète u, le nombre de a sera différent
de celui de b.
u ∈ b∗ : impossible, car si on répète u, le nombre de b sera différent
de celui de a.
u ∈ (a + b)∗ : impossible, car une occurrence de b peut précéder
celle de a.
Le théorème du gonflement ne peut pas s’appliquer au langage an bn donc
ce langage n’est pas régulier

Le langage an bn est dit algébrique ou Hors-Contexte

Yousra Hlaoui (FST-DSI) Automates à états finis 60 / 1

 Limites des automates finis

Limites des automates finis

Limites
Intuitivement, les limites des langages réguliers sont liées au fait que ces
langages sont acceptés par des machines à mémoire finie fixée.
Il existe, alors, une quantité de mémoire maximale qui ne peut être utilisée
indépendamment du mot à traiter
Par conséquent, si pour reconnaitre un langage, il faut, alors, une quantité de
mémoire qui n’est pas bornée a priori : ce langage n’est pas régulier !

Yousra Hlaoui (FST-DSI) Automates à états finis 61 / 1