Théorie des langages (Introduction/Rappels)

Alexis Nasr
Carlos Ramisch
Manon Scholivet

Compilation – L3 Informatique
Département Informatique et Interactions
Aix Marseille Université

1 / 76
Langages

Grammaires
Arbres de dérivation
Types de grammaires

Reconnaisseurs
Généralités
Automates finis
Automates à pile
Machines de Turing

2 / 76
Langages

Grammaires
Arbres de dérivation
Types de grammaires

Reconnaisseurs
Généralités
Automates finis
Automates à pile
Machines de Turing

3 / 76
Le paysage syntaxique

Les symboles sont des éléments indivisibles qui vont servir de

briques de base pour construire des mots.
Un alphabet est un ensemble fini de symboles. On désigne
conventionnellement un alphabet par la lettre grecque Σ.
Une suite de symboles, appartenant à un alphabet Σ, mis bout à
bout est appelé un mot (ou une chaîne) sur Σ. Le mot de longueur
zéro est noté ε.
On note |m| la longueur du mot m (le nombre de symboles qui le
composent) et |m|s le nombre de symboles s que possède le mot
m.
L’ensemble de tous les mots que l’on peut construire sur un
alphabet Σ est noté Σ∗ .
Un langage sur un alphabet Σ est un ensemble de mots construits
sur Σ. Tout langage défini sur Σ est donc une partie de Σ∗ .

4 / 76
Exemples de langages

Σ = { a} L1 = {ε, a, aa, aaa, . . .}

Σ = { a, b} L2 = {ε, ab, aabb, aaabbb, aaaabbbb, . . .}

Σ = { a, b} L3 = {ε, aa, bb, aaaa, abba, baab, bbbb, . . .}

Σ = { a, b, c} L4 = {ε, abc, aabbcc, aaabbbccc, . . .}

5 / 76
Opérations sur les langages

Union L1 ∪ L2 { x | x ∈ L1 ou x ∈ L2 }
Intersection L1 ∩ L2 { x | x ∈ L1 et x ∈ L2 }
Différence L1 − L2 { x | x ∈ L1 et x ∈
/ L2 }
Complément L̄ { x ∈ Σ∗ | x ∈
/ L}
Concaténation L1 L2 { xy | x ∈ L1 ety ∈ L2 }
n
z }| {
Auto concaténation L...L Ln
L∗ Lk
S
Fermeture de Kleene k ≥0

6 / 76
Comment décrire un langage ?

Énumération
L2 = {ε, ab, aabb, aaabbb, aaaabbbb, . . .}
Description littéraire
Ensemble des mots construits sur l’alphabet { a, b}, commençant par
des a et se terminant par des b et tel que le nombre de a et le nombre de
b soit égal
Grammaire de réécriture
G = h{S}, { a, b}, {S → aSb | ε}, Si

7 / 76
Langages

Grammaires
Arbres de dérivation
Types de grammaires

Reconnaisseurs
Généralités
Automates finis
Automates à pile
Machines de Turing

8 / 76
Grammaires de réécriture

Une grammaire de réécriture est un 4-uplet h N, Σ, P, Si où :

N est un ensemble de symboles non terminaux, appelé

l’alphabet non-terminal.
Σ est un ensemble de symboles terminaux, appelé l’alphabet
terminal, tel que N et Σ soient disjoints.
P est un sous ensemble fini de :

( N ∪ Σ)∗ N ( N ∪ Σ)∗ × ( N ∪ Σ)∗

un élément (α, β) de P, que l’on note α → β est appelé une règle
de production ou règle de réécriture.
α est appelé partie gauche de la règle
β est appelé partie droite de la règle
S est un élément de N appelé l’axiome de la grammaire.

9 / 76
Notation

Pour alléger les notations, on note :

α → β1 | β2 | . . . | βn
les n règles :

α → β1 , α → β2 , . . . , α → βn

10 / 76
Proto-mots d’une grammaire

Les proto-mots d’une grammaire G = h N, Σ, P, Si sont des mots

construits sur l’alphabet Σ ∪ N, on les définit récursivement de la
façon suivante :

S est un proto-mot de G
si αβγ est un proto-mot de G et β → δ ∈ P alors αδγ est un
proto-mot de G.
Un proto-mot de G ne contenant aucun symbole non-terminal est
appelé un mot engendré par G. Le langage engendré par G, noté
L( G ) est l’ensemble des mots engendrés par G.

11 / 76
Dérivation

L’opération qui consiste à générer un proto-mot αδγ à partir d’un

proto-mot αβγ et d’une règle de production r de la forme β → δ
est appelée l’opération de dérivation. Elle se note à l’aide d’une
double flèche :

αβγ ⇒ αδγ
k
On note α ⇒ β pour indiquer que β se dérive de α en k étapes.
+ ∗
On définit aussi les deux notations ⇒ et ⇒ de la façon suivante :
+ k
α ⇒ β ≡ α ⇒ β avec k > 0
∗ k
α ⇒ β ≡ α ⇒ β avec k ≥ 0

Attention
Les symboles ⇒ et → ne représentent pas la même chose.

12 / 76
Conventions

Les symboles non terminaux appartenant à N sont représentés

par des lettres latines majuscules : A, B, C, S, E, T . . .
Les symboles terminaux appartenant à Σ sont représentés par
des lettres latines minuscules : a, b, c, d . . .
Les proto-mots appartenant à ( N ∪ Σ)∗ sont représentés par des
lettres grecques minuscules : α, β, γ, ε . . .
L’axiome est représenté par le non-terminal S et constitue la
partie gauche de la première règle de production

13 / 76
Langage engendré par une grammaire

L( G ) est défini de la façon suivante :

+
L( G ) = {m ∈ Σ∗ | S ⇒ m}
Deux grammaires G et G 0 sont équivalentes si L( G ) = L( G 0 ).

14 / 76
L1 = {ε, a, aa, aaa, . . .}

G = h{S}, { a}, {S → Sa | ε}, Si

sous-ensemble des proto-mots de G

S
 HH

ε Sa
 HH

a Saa
H
 H
aa Saaa
HH
aaa Saaaa

15 / 76
L2 = {ε, ab, aabb, aaabbb, aaaabbbb, . . .}

G = h{S}, { a, b}, {S → aSb | ε}, Si

sous-ensemble des proto-mots de G

S
H
 H
 H
ε aSb
H HH

ab aaSbb
H
 H
aabb aaaSbbb

16 / 76
L3 = { aa, bb, aaaa, abba, baab, bbbb, . . .}

G = h{S}, { a, b}, {S → aSa | bSb | aa | bb}, Si

sous-ensemble des proto-mots de G

S
P
 PP
 @
@ PPP
 PP
  @ PP
  @ P
aSa aa bb bSb

 PP
 @ PP  P
 PP
 @ P   @@ PP
aaSaa aaaa abba abSba baSab baab bbbb bbSbb

17 / 76
L4 = {ε, abc, aabbcc, aaabbbccc, . . .}
 
S → aS1 c, S1 → b | SS2 ,
G = h{S, S1 , S2 }, { a, b, c}, , Si
cS2 → S2 c, bS2 → bb

sous-ensemble des proto-mots de G

S

aS1 c
 H
 HH
abc aSS2 c

aaS1 cS2 c
HH
 H
aabcS2 c aaSS2 cS2 c

aabS2 cc

aabbcc

18 / 76
Sens de dérivation

G = h{ E, T, F }, {+, ∗, a}, { E → T + E | T, T → F ∗ T | F, F → a}, Ei

Les proto-mots engendrés lors d’une dérivation peuvent comporter

plus d’un symbole non-terminal :

E ⇒ T+E
⇒ T+T
⇒ F+T
⇒ F+F∗T
⇒ F+a∗T
⇒ F+a∗F
⇒ a+a∗F
⇒ a+a∗a

19 / 76
Sens de dérivation

Dérivation gauche : on réécrit le Dérivation droite :

non-terminal le plus à gauche : ...

E ⇒ T+E E ⇒ T+E
⇒ F+E ⇒ T+T
⇒ a+E ⇒ T+F∗T
⇒ a+T ⇒ T+F∗F
⇒ a+F∗T ⇒ T+F∗a
⇒ a+a∗T ⇒ T+a∗a
⇒ a+a∗F ⇒ F+a∗a
⇒ a+a∗a ⇒ a+a∗a

20 / 76
Arbre de dérivation

E
H
HH
 H
T + E

F T
HH
a F * T

a F

Un arbre de dérivation pour G (G = h N, Σ, P, Si) est un arbre

ordonné et étiqueté dont les étiquettes appartiennent à l’ensemble
N ∪ Σ ∪ {ε}. Si un nœud de l’arbre est étiqueté par le non terminal A
et ses fils sont étiquetés X1 , X2 , ..., Xn alors la règle A → X1 , X2 , ..., Xn
appartient à P.

21 / 76
Arbre de dérivation

Un arbre de dérivation indique les règles qui ont été utilisées

dans une dérivation, mais pas l’ordre dans lequel elles ont été
utilisées.
À un arbre de dérivation correspondent une seule dérivation
droite et une seule dérivation gauche.

22 / 76
Ambiguïté

Une grammaire G est ambiguë s’il existe au moins un mot m dans

L( G ) auquel correspond plus d’un arbre de dérivation.
Exemple :
E → E+E | E∗E | a
E E
H
 HH H
 H
 H  HH
E + E E * E
HH HH
a E * E E + E a

a a a a

23 / 76
Symboles et règles de production utiles

Pour manipuler une grammaire, il est souhaitable que tous les

symboles et règles de production soient utiles :
Un symbole terminal ou non-terminal est utile s’il apparaît dans
une règle de production utile
Une règle de production est utile si :
1 elle peut générer des mots
2 le symbole non-terminal de la partie gauche peut être généré (sauf
l’axiome, qui peut par définition ne pas être généré)
3 elle n’est pas de la forme α → α

24 / 76
Types de règles
Les grammaires peuvent être classées en fonction de la forme de leurs
règles de production. On définit cinq types de règles de production :

Une règle est régulière à gauche si et seulement si elle est de la

forme A → xB ou A → x avec A, B ∈ N et x ∈ Σ∗ .
Une règle est régulière à droite si et seulement si elle est de la
forme A → Bx ou A → x avec A, B ∈ N et x ∈ Σ∗ .
Une règle A → α est un règle hors-contexte si et seulement si :
A ∈ N et α ∈ ( N ∪ Σ)∗
Une règle α → β est une règle contextuelle si et seulement si :
α = gAd et β = gBd avec g, d, B ∈ ( N ∪ Σ)∗ et A ∈ N.
Le nom “contextuelle” provient du fait que A se réecrit B uniquement
dans le contexte g_d.
Une règle α → β est une règle sans restriction si elle n’est pas
contextuelle.

25 / 76
Type d’une grammaire

Une grammaire est :

régulière ou de type 3 si elle est régulière à droite ou régulière à
gauche. Une grammaire est régulière à gauche si toutes ses règles
sont régulières à gauche et une grammaire est régulière à droite
si toutes ses règles sont régulières à droite.
hors contexte ou de type 2 si toutes ses règles de production sont
hors contexte.
dépendante du contexte ou de type 1 si toutes ses règles de
production sont dépendantes du contexte.
sans restrictions ou de type 0 si toutes ses règles de production
sont sans restrictions.

26 / 76
Hiérarchie de Chomsky

0 : sans restriction

1 : contextuelle

2 : hors-contexte

3 : régulière

27 / 76
Type d’un langage

Un langage pouvant être engendré par une grammaire de type x et

pas par une grammaire d’un type supérieur dans la hiérarchie, est
appelé un langage de type x.

Type Nom
3 régulier
2 hors contexte
1 dépendant du contexte
0 récursivement énumérable

28 / 76
Exemples de langages réguliers

L1 = {m ∈ { a, b}∗ }

L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0}

L3 = {m ∈ { a, b}∗ | m = xaaa avec x ∈ { a, b}∗ }

L4 = {m ∈ { a, b}∗ | |m| a mod 2 = 0 et|m|b mod 2 = 0}

29 / 76
Exemples de langages réguliers

L1 = {m ∈ { a, b}∗ }
G1 = h{S}, { a, b}, {S → aS | bS | ε}, Si

L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0}

L3 = {m ∈ { a, b}∗ | m = xaaa avec x ∈ { a, b}∗ }

L4 = {m ∈ { a, b}∗ | |m| a mod 2 = 0 et|m|b mod 2 = 0}

29 / 76
Exemples de langages réguliers

L1 = {m ∈ { a, b}∗ }
G1 = h{S}, { a, b}, {S → aS | bS | ε}, Si

L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0} 

S → aT | bS | ε,
G2 = h{S, T }, { a, b}, , Si
T → aS | bT
L3 = {m ∈ { a, b}∗ | m = xaaa avec x ∈ { a, b}∗ }

L4 = {m ∈ { a, b}∗ | |m| a mod 2 = 0 et|m|b mod 2 = 0}

29 / 76
Exemples de langages réguliers

L1 = {m ∈ { a, b}∗ }
G1 = h{S}, { a, b}, {S → aS | bS | ε}, Si

L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0} 

S → aT | bS | ε,
G2 = h{S, T }, { a, b}, , Si
T → aS | bT
L3 = {m ∈ { a, b}∗ | m = ∗
xaaa avec x ∈ { a, b} } 
 S → aS | bS | aT, 
G3 = h{S, T, U }, { a, b}, T → aU, , Si
U → a
 
L4 = {m ∈ { a, b}∗ | |m| a mod 2 = 0 et|m|b mod 2 = 0}

29 / 76
Exemples de langages réguliers

L1 = {m ∈ { a, b}∗ }
G1 = h{S}, { a, b}, {S → aS | bS | ε}, Si

L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0} 

S → aT | bS | ε,
G2 = h{S, T }, { a, b}, , Si
T → aS | bT
L3 = {m ∈ { a, b}∗ | m = ∗
xaaa avec x ∈ { a, b} } 
 S → aS | bS | aT, 
G3 = h{S, T, U }, { a, b}, T → aU, , Si
U → a
 
L4 = {m ∈ { a, b}∗ | |m| a mod 2 = 0 et|m|b mod 2 = 0}
G4 h{S, T, U, V }, { a, b},
=  
S → aT | bU | ε, T → aS | bV,
, Si
V → aU | bT, U → aV | bS

29 / 76
Exemples de langages hors-contexte

L1 = { a n b n | n ≥ 0}

L2 = {mm−1 | m ∈ { a, b}∗ } (langage miroir - palindromes paires)

30 / 76
Exemples de langages hors-contexte

L1 = { a n b n | n ≥ 0}
G1 = h{S}, { a, b}, {S → aSb | ε}, Si

L2 = {mm−1 | m ∈ { a, b}∗ } (langage miroir - palindromes paires)

30 / 76
Exemples de langages hors-contexte

L1 = { a n b n | n ≥ 0}
G1 = h{S}, { a, b}, {S → aSb | ε}, Si

L2 = {mm−1 | m ∈ { a, b}∗ } (langage miroir - palindromes paires)

G2 = h{S}, { a, b}, {S → aSa | bSb | ε}, Si

30 / 76
Exemples de langages contextuels

L1 = { a n b n c n | n ≥ 0}

L2 = {m]m | avec m ∈ { a, b}∗ }

31 / 76
Exemples de langages contextuels

L1 = { a n b n c n | n ≥ 0}
G1 = h{
 S, B, B̄, C }, { a, b, c}, 
 S → aSBC | ε, CB
 → B̄B, 

B̄B → B̄C, B̄C → BC,
 
, Si

 aB → ab, bB → bb, 
bC → bc, cC → cc
 
L2 = {m]m | avec m ∈ { a, b}∗ }
...

31 / 76
Grammaire v/s Reconnaisseur

Une grammaire d’un langage L permet de générer tous les mots

appartenant à L.
Un reconnaisseur pour un langage L est un programme qui
prend en entrée un mot m et répond oui si m appartient à L et
non sinon.
Pour chaque classe de grammaire, il existe une classe de
reconnaisseurs qui définit la même classe de langages.
Type de grammaire Type de reconnaisseur
régulière Automate fini
hors contexte Automate à pile
contextuelle Automate linéairement borné
sans restriction Machine de Turing

32 / 76
Langages

Grammaires
Arbres de dérivation
Types de grammaires

Reconnaisseurs
Généralités
Automates finis
Automates à pile
Machines de Turing

33 / 76
Représentation graphique d’un reconnaisseur

BANDE D’ENTREE

TETE DE LECTURE

UNITE DE CONTROLE

MEMOIRE
AUXILIAIRE

34 / 76
Éléments d’un reconnaisseur
Un reconnaisseur est composé de quatre parties :
1 une bande de lecture
elle est composée d’une succession de cases.
Chaque case pouvant contenir un seul symbole d’un alphabet
d’entrée.
C’est dans les cases de cette bande de lecture qu’est écrit le mot à
reconnaître.
2 une tête de lecture
Elle peut lire une case à un instant donné.
La case sur laquelle se trouve la tête de lecture à un moment donné
s’appelle la case courante.
La tête peut être déplacée par le reconnaisseur pour se positionner
sur la case immédiatement à gauche ou à droite de la case courante.
3 une mémoire
Elle peut prendre des formes différentes.
La mémoire permet de stocker des éléments d’un alphabet de
mémoire.

35 / 76
Éléments d’un reconnaisseur

4 une unité de contrôle

Elle constitue le cœur d’un reconnaisseur.
Elle peut être vue comme un programme qui dicte au
reconnaisseur son comportement.
Elle est définie par un ensemble fini d’états ainsi que par une
fonction de transition qui décrit le passage d’un état à un autre en
fonction du contenu de la case courante de la bande de lecture et
du contenu de la mémoire.
L’unité de contrôle décide aussi de la direction dans laquelle
déplacer la tête de lecture et choisit quels symboles stocker dans la
mémoire.
Parmi les états d’un reconnaisseur, on distingue
des états initiaux, qui sont les états dans lesquels doit se trouver le
reconnaisseur avant de commencer à reconnaître un mot
des états d’acceptation qui sont les états dans lequel doit se trouver le
reconnaisseur après avoir reconnu un mot.

36 / 76
Configuration et mouvement

Configuration d’un reconnaisseur :

Etat de l’unité de contrôle
Contenu de la bande d’entrée et position de la tête
Contenu de la mémoire
Mouvement : passage d’une configuration à une autre (C1 ` C2 )

37 / 76
Configurations

configuration initiale
L’unité de contrôle est dans un état initial
La tête est au début de la bande
La mémoire contient un élément initial.
configuration d’acceptation
L’unité de contrôle est dans un état d’acceptation
La tête de lecture est à la fin de la bande
La mémoire se trouve dans un état d’acceptation.

38 / 76
Déterminisme

L’unité de contrôle est dite déterministe si à toute configuration

correspond au plus un mouvement. S’il peut exister plus d’un
mouvement, elle est dite non déterministe.
Le déterminisme est une propriété importante :
Un reconnaisseur déterministe reconnaît un mot de longueur n en
O(n)

39 / 76
Reconnaissance

Un mot m est acceptée par un reconnaisseur si, partant de l’état

initial, avec m sur la bande d’entrée, le reconnaisseur peut faire
une série de mouvements pour se retrouver dans un état
d’acceptation.
Le langage accepté par un reconnaisseur est l’ensemble de tous
les mots qu’il accepte.

40 / 76
Automates finis

Le modèle le plus simple de reconnaisseur.

Mémoire limitée aux seuls états.

a
1 3

a b c a

0 2
b

Un état initial (0), un ou plusieurs états finaux (1 et 3).

41 / 76
Définition

Un automate fini est un 5-uplet h Q, Σ, δ, q0 , F i

Q est l’ensemble des états,
Σ est l’alphabet de l’entrée
δ est la fonction de transition :

δ : Q × (Σ ∪ {ε}) → ℘( Q)
q0 ∈ Q est l’état initial,
F ⊆ Q est l’ensemble des états d’acceptation.

42 / 76
Exemple

h Q, Σ, δ, q0 , F i
Q = {0, 1, 2, 3}
a
1 3 Σ = { a, b, c}
δ(0, a) = {1}
δ(0, b) = {2}
a b c a
δ(1, a) = {3}
δ(1, b) = {0}
0 2 δ(2, c) = {3}
b δ(3, a) = {2}
q0 = 0
F = {1, 3}

43 / 76
Configurations et mouvement

A = h Q, Σ, δ, q0 , F i
Configuration : (q, m) ∈ Q × Σ∗ où :
q représente l’état courant de l’unité de contrôle
m est la partie du mot à reconnaître non encore lue. Le premier
symbole de m (le plus à gauche) est celui qui se trouve sous la tête
de lecture. Si m = ε alors tout le mot a été lu.
Configuration initiale : (q0 , m) où m est le mot à reconnaître
Configuration d’acceptation : (q, ε) avec q ∈ F
Mouvement : (q, aw) ` (q0 , w) si q0 ∈ δ(q, a).

44 / 76
Reconnaissance

a
1 3 (0, ababbc)

a b c a

0 2
b

45 / 76
Reconnaissance

a
1 3 (0, ababbc)
` (1, babbc)
a b c a

0 2
b

45 / 76
Reconnaissance

a
1 3 (0, ababbc)
` (1, babbc)
` (0, abbc)
a b c a

0 2
b

45 / 76
Reconnaissance

a
1 3 (0, ababbc)
` (1, babbc)
` (0, abbc)
a b c a
` (1, bbc)

0 2
b

45 / 76
Reconnaissance

a
1 3 (0, ababbc)
` (1, babbc)
` (0, abbc)
a b c a
` (1, bbc)
` (0, bc)
0 2
b

45 / 76
Reconnaissance

a
1 3 (0, ababbc)
` (1, babbc)
` (0, abbc)
a b c a
` (1, bbc)
` (0, bc)
0 2 ` (2, c)
b

45 / 76
Reconnaissance

a
1 3 (0, ababbc)
` (1, babbc)
` (0, abbc)
a b c a
` (1, bbc)
` (0, bc)
0 2 ` (2, c)
b ` (3, ε)

45 / 76
L1 = {m ∈ { a, b}∗ }

46 / 76
L1 = {m ∈ { a, b}∗ }

G1 = h{S}, { a, b}, {S → aS | bS | ε}, Si

46 / 76
L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0}

47 / 76
L2 = {m ∈ { a, b}∗ | |m| a mod 2 = 0}

b b
a
0 1
a

G2 = h{S, T }, { a, b}, {S → aT | bS | ε, T → aS | bT }, Si

47 / 76
L3 = { xaaa | x ∈ { a, b}∗ }

48 / 76
L3 = { xaaa | x ∈ { a, b}∗ }

a
a a a
0 1 2 3

G3 = h{S, T, U }, { a, b}, {S → aS | bS | aT, T → aU, U → a}, Si

48 / 76
L3 = { xaaa | x ∈ { a, b}∗ }

a
a a a
0 1 2 3

G3 = h{S, T, U }, { a, b}, {S → aS | bS | aT, T → aU, U → a}, Si

Non-déterminisme !

48 / 76
L3 = { xaaa | x ∈ { a, b}∗ }

b a
a
a a
0 b 1 2 3

b
b

49 / 76
L3 = { xaaa | x ∈ { a, b}∗ }

(0, abaabaaa)
b a ` (1, baabaaa)
a ` (0, aabaaa)
a a
0 b 1 2 3 ` (1, abaaa)
` (2, baaa)
` (0, aaa)
b ` (1, aa)
b ` (2, a)
` (3, ε)

49 / 76
Déterminisme

Tout langage régulier peut être reconnu par un automate fini

déterministe
Pour tout automate fini non déterministe A, on peut construire
un automate déterministe A0 avec L( A) = L( A0 )
Prix à payer : dans le pire des cas, | Q( A0 )| = 2|Q( A)|

50 / 76
Limite des automates finis

Certains langages ne peuvent pas être reconnus par les

automates finis (ne peuvent être engendrés par une grammaire
régulière)
Exemple : L = { an bn | n ≥ 0}
Il faut mémoriser le nombre de a que l’on a lu pour vérifier que
le mot possède autant de b.
Pour mémoriser un nombre potentiellement infini de a, il faut un
ensemble infini d’états !

51 / 76
Automates à pile

Forme simple de mémoire : une pile.

Mode de stockage Last In First Out.
On ne peut accéder qu’à l’élément se trouvant au sommet de la
pile.
Deux opérations possibles :
empiler : ajouter un élément au sommet.
dépiler : enlever l’élément se trouvant au sommet.
Elle commence avec un symbole de fond de pile ⊥, que l’on ne peut
pas dépiler.
La pile permet de stocker de l’information sans forcément multiplier
le nombre d’états.

52 / 76
Représentation graphique

a, B → c

1 2

Si l’automate est en 1, et que la tête de lecture est sur a, l’automate :

décale la tête de lecture d’une case vers la droite
dépile B (B doit être présent au sommet de la pile)
empile c
va en 2

53 / 76
Représentation graphique

a, B → c

1 2

Si l’automate est en 1, et que la tête de lecture est sur a, l’automate :

décale la tête de lecture d’une case vers la droite
dépile B (B doit être présent au sommet de la pile)
empile c
va en 2

cas particuliers

si a = ε, l’automate peut franchir cet arc sans lire de symbole.

si B = ε, l’automate peut franchir cet arc indépendamment du
symbole se trouvant en sommet de pile (et ne le dépile pas).
si c = ε, l’automate peut franchir cet arc sans rien empiler.
53 / 76
Représentation graphique

a, ε → A b, A → ε

b, A → ε ε, ⊥ → ⊥
1 2 3

54 / 76
Définition formelle

Un automate à pile est un 6-uplet h Q, Σ, Γ, δ, q0 , F i

Q est l’ensemble des états
Σ est l’alphabet d’entrée
Γ est l’alphabet de symboles de pile
(en particulier, ⊥ ∈ Γ)
δ est la fonction de transition :

δ : Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → ℘( Q × Γ∗ )
q0 ∈ Q est l’état initial
F ⊆ Q est l’ensemble des états d’acceptation

55 / 76
Configurations et mouvement

A = h Q, Σ, Γ, δ, q0 , F i
Configuration : (q, m, α) ∈ Q × Σ∗ × Γ∗ où :
q représente l’état courant de l’unité de contrôle
m est la partie du mot à reconnaître non encore lue. Le premier
symbole de m (le plus à gauche) est celui qui se trouve sous la tête
de lecture. Si m = ε alors tout le mot a été lu.
α représente le contenu de la pile. Le symbole le plus à gauche est
le sommet de la pile. Si α = ε alors la pile est vide.
Configuration initiale : (q0 , m, ⊥) où m est le mot à reconnaître
Configuration d’acceptation : (q, ε, ⊥) avec q ∈ F
Mouvement : (q, aw, Zα) ` (q0 , w, γα) si (q0 , γ) ∈ δ(q, a, Z ).

56 / 76
Équivalence

Représentation graphique Définition formelle

h Q, Σ, Γ, δ, q0 , F i
Q = {0, 1, 2, 3}
3
Σ = { a, b}
Γ = { A, ⊥}

ε, ⊥ → ⊥ δ(1, a, ε) = {(1, A)}

δ(1, b, A) = {(2, ε)}
δ(2, b, A) = {(2, ε)}
b, A → ε δ(2, ε, ⊥) = {(3, ⊥)}
1 2
q0 = 1
a, ε → A b, A → ε F = {3}

57 / 76
Reconnaissance

3
(1, aaabbb, ⊥)

ε, ⊥ → ⊥

⊥ b, A → ε
1 2

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
` (1, aabbb, A⊥)
ε, ⊥ → ⊥

A
⊥ b, A → ε
1 2

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
` (1, aabbb, A⊥)
ε, ⊥ → ⊥ ` (1, abbb, AA⊥)
A
A
⊥ b, A → ε
1 2

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
A ` (1, aabbb, A⊥)
ε, ⊥ → ⊥ ` (1, abbb, AA⊥)
A
` (1, bbb, AAA⊥)
A
⊥ b, A → ε
1 2

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
` (1, aabbb, A⊥)
ε, ⊥ → ⊥ ` (1, abbb, AA⊥)
A
` (1, bbb, AAA⊥)
A ` (2, bb, AA⊥)
⊥ b, A → ε
1 2

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
` (1, aabbb, A⊥)
ε, ⊥ → ⊥ ` (1, abbb, AA⊥)
` (1, bbb, AAA⊥)
A ` (2, bb, AA⊥)
⊥ b, A → ε ` (2, b, A⊥)
1 2

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
` (1, aabbb, A⊥)
ε, ⊥ → ⊥ ` (1, abbb, AA⊥)
` (1, bbb, AAA⊥)
` (2, bb, AA⊥)
⊥ b, A → ε ` (2, b, A⊥)
1 2 ` (2, ε, ⊥)

a, ε → A b, A → ε

58 / 76
Reconnaissance

3
(1, aaabbb, ⊥)
` (1, aabbb, A⊥)
ε, ⊥ → ⊥ ` (1, abbb, AA⊥)
` (1, bbb, AAA⊥)
` (2, bb, AA⊥)
⊥ b, A → ε ` (2, b, A⊥)
1 2 ` (2, ε, ⊥)
` (3, ε, ⊥)
a, ε → A b, A → ε

58 / 76
L = {mm−1 | m ∈ { a, b}∗ }

G = h{S}, { a, b}, {S → aSa | bSb | ε}, Si

59 / 76
L = {mm−1 | m ∈ { a, b}∗ }

b, ε → B b, B → ε

ε, ε → ε ε, ⊥ → ⊥
1 2 3

a, ε → A a, A → ε

G = h{S}, { a, b}, {S → aSa | bSb | ε}, Si

59 / 76
L = {m ∈ { a, b}∗ , |m| a = |m|b }

G = h{S}, { a, b}, {S → aSb | bSa | SS | ε}, Si

60 / 76
L = {m ∈ { a, b}∗ , |m| a = |m|b }

b, B → BB
b, ⊥ → B⊥
b, A → ε

ε, ⊥ → ⊥
1 2

a, A → AA
a, ⊥ → A⊥
a, B → ε

G = h{S}, { a, b}, {S → aSb | bSa | SS | ε}, Si

60 / 76
L = { ai b j ck | i ≥ 0, i = j ou i = k}

61 / 76
L = { ai b j ck | i ≥ 0, i = j ou i = k}

ε, ⊥ → ⊥
2 3 c, ε → ε
ε
→ b, A → ε
ε ,ε

a, ε → A 1

ε,
ε→
ε
c, A → ε ε, ⊥ → ⊥
4 5 6

b, ε → ε c, A → ε

61 / 76
L = { ai b j ck | i ≥ 0, i = j ou i = k}

ε, ⊥ → ⊥
2 3 c, ε → ε
ε
→ b, A → ε
ε ,ε

a, ε → A 1

ε,
ε→
ε
c, A → ε ε, ⊥ → ⊥
4 5 6

b, ε → ε c, A → ε

L = { ai b j ck | i = j ou i = k} ne peut être reconnu par un automate à

pile déterministe !

61 / 76
Langages hors-contexte déterministes

Automate à pile déterministe :

|δ(q, a, Z )| ≤ 1 pour tout q ∈ Q, a ∈ Σ ∪ {ε}, Z ∈ Γ
si δ(q, ε, Z ) est défini, alors δ(q, a, Z ) ne peut être défini pour
aucun a ∈ Σ.

non-déterministe

déterministe

62 / 76
Limites des automates à pile

Certains langages ne peuvent être reconnus par les automates à

pile (ne peuvent être engendrés par une grammaire
hors-contexte).
Exemple : le langage m]m avec m ∈ {0, 1}∗ :
1 L’automate lit le premier m et le stocke dans la pile.
2 Il lit le premier symbole du second m.
3 Comment vérifier qu’il est identique au symbole se trouvant au
fond de la pile ?

63 / 76
Machines de Turing

Proches des automates finis mais avec une mémoire infinie et à

accès direct.
Modèle plus proche d’un ordinateur.
Une machine de Turing (MT) peut faire tout ce qu’un ordinateur
peut faire.
Thèse de Church-Turing : tout traitement réalisable par un
algorithme peut être accompli par une machine de Turing.

64 / 76
Généralités

La mémoire de la MT est matérialisée par une bande de

lecture/écriture.
Elle possède une tête de lecture/écriture pouvant se déplacer
vers la gauche et vers la droite.
Au départ, la bande contient le mot à reconnaître et possède des
 dans toutes les autres cases.

65 / 76
Caractéristiques

Une MT peut lire et écrire sur la bande de lecture/écriture.

La tête de lecture/écriture peut se déplacer vers la droite et vers
la gauche.
La bande de lecture écriture est infinie.
Lorsque la MT atteint l’état d’acceptation ou l’état de rejet, elle
s’arrête et accepte ou rejette le mot.
Si la MT n’atteint pas l’état d’acceptation ou de rejet, elle peut
continuer indéfiniment.

66 / 76
Représentation graphique

a → b, D
1 2

La machine est en 1, la tête de lecture est sur a, elle :

écrit un b sur la bande (à la place du a),
décale la tête de lecture d’une case vers la droite (D)
va en 2.

67 / 76
Représentation graphique

a → b, D
1 2

La machine est en 1, la tête de lecture est sur a, elle :

écrit un b sur la bande (à la place du a),
décale la tête de lecture d’une case vers la droite (D)
va en 2.
Cas particuliers :
a → G : la machine n’écrit rien.
a : la machine n’écrit rien et ne bouge plus (elle arrive
généralement dans un état final).

67 / 76
Définition

Une MT est un octuplet h Q, Σ, Γ, , δ, q0 , q A , q R i où :

Q est l’ensemble des états,
Σ est l’alphabet de l’entrée (qui ne contient pas le symbole
spécial ),
Γ est l’alphabet de la bande ( ∈ Γ et Σ ⊆ Γ),
δ est la fonction de transition :

δ : Q × (Γ ∪ {ε}) → ℘( Q × Γ × { D, G })
q0 ∈ Q est l’état initial,
q A ∈ Q est l’état d’acceptation,
q R ∈ Q est l’état de rejet, avec q R 6= q A .

68 / 76
Configurations et mouvement
M = h Q, Σ, Γ, δ, q0 , q A i
Configuration : (u, q, av) ∈ Γ∗ × Q × Γ∗ où :
q représente l’état courant de l’unité de contrôle
u est la partie de la bande se trouvant à gauche de la tête.
v est la partie de la bande se trouvant à droite de la tête.
a est le symbole se trouvant sous la tête.
Configuration initiale : (ε, q0 , m) où m est le mot à reconnaître
Configuration d’acceptation : (u, q A , v)
Configuration de rejet : (u, q R , v)
Mouvement :

(ua, qi , bv) ` (u, q j , acv)si(q j , c, G ) ∈ δ(qi , b)

(ua, qi , bv) ` (uac, q j , v)si(q j , c, D ) ∈ δ(qi , b)

69 / 76
Exemple

Principe d’une machine reconnaissant L = {m]m | m ∈ {0, 1}∗ }.

1 Fait des allers-retours entre les deux occurrences de m pour
vérifier qu’elles contiennent bien le même symbole. Si ce n’est
pas le cas, ou qu’un # supplémentaire est détecté, va dans l’état
de rejet. Les symboles sont éliminés au fur et à mesure qu’ils sont
vérifiés (par le symbole x à gauche, et z à droite).
2 Lorsque tous les symboles à gauche de ] ont été éliminés, vérifie
qu’il ne reste plus de symboles à droite de ]. Si c’est le cas, va
dans l’état d’acceptation, sinon va dans l’état de rejet.

70 / 76
Exemple — début d’exécution

...   a b b # a b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a

71 / 76
Exemple — début d’exécution

2a

...   x b b # a b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #

71 / 76
Exemple — début d’exécution

2a

...   x b b # a b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #

71 / 76
Exemple — début d’exécution

2a

...   x b b # a b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z

71 / 76
Exemple — début d’exécution

3a

...   x b b # a b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z
δ (3 a , a ) = (z, 4, G ) vérifie la lettre

71 / 76
Exemple — début d’exécution

...   x b b # z b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z
δ (3 a , a ) = (z, 4, G ) vérifie la lettre
δ(4, α) = (α, 4, G ) pour α 6= x revient vers x

71 / 76
Exemple — début d’exécution

...   x b b # z b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z
δ (3 a , a ) = (z, 4, G ) vérifie la lettre
δ(4, α) = (α, 4, G ) pour α 6= x revient vers x

71 / 76
Exemple — début d’exécution

...   x b b # z b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z
δ (3 a , a ) = (z, 4, G ) vérifie la lettre
δ(4, α) = (α, 4, G ) pour α 6= x revient vers x

71 / 76
Exemple — début d’exécution

...   x b b # z b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z
δ (3 a , a ) = (z, 4, G ) vérifie la lettre
δ(4, α) = (α, 4, G ) pour α 6= x revient vers x
δ(4, x ) = ( x, 1, D ) relance le processus

71 / 76
Exemple — début d’exécution

...   x b b # z b b   ...

δ(1, a) = ( x, 2a , D ) enregistre a
δ (2 a , α ) = (α, 2a , D ) pour α 6= # cherche #
δ (2 a , #) = (#, 3a , D ) 3a cherche une lettre non-z
δ (3 a , a ) = (z, 4, G ) vérifie la lettre
δ(4, α) = (α, 4, G ) pour α 6= x revient vers x
δ(4, x ) = ( x, 1, D ) relance le processus
δ(1, b) = ( x, 2b , D ) . . .

71 / 76
Exemple — machine
z → z, D 5 

a, b
,# qA
α→D z → z, D
#→D

#→D b, #
2a 3a
D a→
x, z,
a→ G

x → x, D
1 4 qR
G
b→ z,
b→ β→G
x,
D
2b 3b a, #
#→D

α→D z→D

α = Γ \ {#}, β = Γ \ { x }.
72 / 76
Déterminisme

Pour toute MT A non déterministe, il existe une MT A0 telle que

L ( A ) = L ( A 0 ).
Le non déterminisme n’augmente pas la puissance du modèle
des MT.

73 / 76
Langages récursivement énumérables

Un langage est récursivement énumérable si et seulement si il

existe une MT qui le reconnaît.
Un langage est récursivement énumérable si et seulement si il
existe une MT déterministe qui le reconnaît.

74 / 76
Rapports avec la compilation

Analyse lexicale et automates finis

Analyse syntaxique et automates à pile
Production de code et machines de Turing

75 / 76
Sources

Michael Sipser,
Introduction to the Theory of Computation.
PWS Publishing Company, 1997.
John Hopcroft, Rajeev Motwani, Jeffrey Ullman,
Introduction to Automata Theory, Languages and Computation.
2ème édition, Pearson Education International, 2001.
John Aho, Jeffrey Ullman, The Theory of Parsing, Translation and
Compiling, Vol I : Parsing.
Prentice-Hall, 1972

76 / 76