LES GRAMMAIRES

1\ Notations :

- Le mot vide est noté : ε

- L’ensemble des mots formés à partir d'un alphabet X est noté : X*

- La concaténation de 2 mots w1 et w2 est notée : w1.w2

- La longueur d'un mot w est noté : |w|

- Le miroir d'un mot est noté : wr

- Le langage vide est un langage qui ne contient aucun mot, il

est noté : ∅

- Le langage ∅ est différent du langage {ε}

- La puissance d'un mot est définie comme suit :

wn = wn-1 * w / w0 = ε

Exemple :
Les puissances du mot abb sont : { ε, abb, abbabb, abbabb, ... }
2\ Opérations sur les langages :
- Union : L1 ⋃ L2
- Intersection : L1 ∩ L2
- Complément : { w / w∈X* et w∉L }
- Différence : L1 − L2
- Produit : L1 × L2
- La concaténation : L1.L2
- Langage miroir : Lr
- Puissance concaténative : Ln = Ln-1 * L / L0 = {ε}
- Fermeture itérative : L* = L0 U L1 U L2 U Li …

3\ Les grammaires :
Une grammaire est un quadruplet G = (T, N, S, P) où :

T = l'ensemble des terminaux : c'est l’alphabet sur lequel est

défini le langage, ils sont désignés par des lettres minuscule
a, b, c...

N = l'ensemble de non-terminaux : ce sont des symboles

intermédiaires pour produire de nouveaux objets, Ils sont
désignés par des lettres majuscules A, B, C, ...

S = l'axiome : c'est le point de départ de la grammaire et il fait

partie de N

P = l'ensemble des règles de production : c'est avec ces règles

qu'on construit notre grammaire
Remarque : (T U N)* veut dire "n'importe quoi" c'est l'ensemble
de toutes les combinaisons possibles entre T et N

Deux grammaires G1 et G2 sont dites équivalentes, notées

G1 ≡ G2, si elles génèrent le même langage.
G1 ≡ G2 ⇔ L(G1) = L(G2)

4\ Classification des grammaires :

il existe 4 types de grammaire :

1) Type 3 (Grammaires régulières) : Une grammaire est de

type 3 ssi elle est régulière droite ou bien régulière gauche.

Grammaire régulière droite :

Si toutes les productions dans P sont de la forme :
A  wB ou A  w avec A,B ∈ N et w ∈ T*

Exemple :
A  aabB, A  B, A  aa, A  ε : sont de type 3
A  aBB, A  aBa, A  AB : ne sont pas de type 3

Grammaire régulière gauche :

Si toutes les productions dans P sont de la forme :
A  Bw ou A  w avec A, B ∈ N et w ∈ T*

Exemple : A  Baab, A B, A  aa, A  ε : sont de type 3

2) Type 2 (Grammaires algébriques) : Une grammaire est de
type 2 si et seulement si toutes les productions de P sont de la
forme : A  α avec A ∈ N et α ∈ (T U N)*

Exemple : A  aBb, A  aBBa, A  BB, A  Bab,

A  abB, A  ε sont de type 2 (algébriques )

Remarque : La seule condition sur les grammaires algébriques

porte sur le membre gauche, il faut qu'il soit constitué d’un seul
non-terminal.

3) Type 1 (Grammaires Contextuelles) : Une grammaire est

de type 1 si et seulement si toutes les règles de production de
P sont de la forme :
αAβ  αwβ avec α,β ∈ (T U N)*, A ∈ N, w ∈ (T U N)+

La règle αAβ  αwβ signifie que le non terminal A est remplacé

par w si son contexte gauche est α et son contexte droit est β.

Remarque : il existe une contrainte sur le mot vide (ε) : seul

l’axiome peut générer le mot vide et dans ce cas il n’apparaît
dans aucun membre droit d’une règle de production.

Exemple : aAb  aBBb, aA  aBBa, Ab  BBb, A  AB/a

sont de type 1

4) Type 0 (Grammaire Générale) : Une grammaire est de type

0 si les règles de production dans P n'ont aucune restriction
Donc pour résumer :
Type 3 : A  wB (ou A  Bw) et A  w, A ∈ N et w ∈ T*
Type 2 : A  w, A ∈ N et w ∈ (T U N)*
Type 1 : αAβ  αwβ
Type 0 : aucune condition

Ainsi, nous avons la hiérarchie de Chomsky :

Type 3 ⊆ Type 2 ⊆ Type 1 ⊆ Type 0

Etant donnée une grammaire G, on vérifie dans l’ordre :

Si elle est de type 3
Sinon si elle est de type 2
Sinon si elle est de type 1
Sinon elle est de type 0.

Remarques :
- Un langage peut être généré par différentes grammaires qui
peuvent être de type différent.
- Un langage prend le plus petit type au sens de l’inclusion (On
prend toujours la grammaire la plus restrictive)
 LES AUTOMATES

1\ Définition :
Un automate est une machine abstraite qui permet de
reconnaître les mots d’un langage, il prend en entrée un mot w
et fournit comme résultat :
- accepté : si le mot est reconnu par l’automate
- rejeté : si le mot n’est pas reconnu par l’automate

A chaque type de langage, on associe un type d’automate :

• langages de Type 3  Les Automates d’Etats Finis
• langages de Type 2  Les Automates à Piles
• langages de Type 1  Les Automates à Bornes Linéaires
• langages de Type 0  Les Machines de Turing

2\ Automates d’états Finis (AEF) :

Ce type d'automate lit les symboles d’un mot à reconnaitre un
par un et va d’état en état selon les transitions, le mot lu est soit
accepté par l'automate soit rejeté

Un automate d’états finis déterministe est un quintuplé

A = (X, Q, q0, σ, F) où :
• X : l'alphabet d’entrée
• Q : l'ensemble des états
• q0 ⊆ Q : l'état initial
• F ⊆ Q : l'ensemble des états finaux
• σ : la fonction de transitions qui associe à un état donné p et
un symbole donné à un état d’arrivée

Remarque : σ (p, a) = q signifie que l’automate réalise une

transition de l’état p vers l’état q en lisant la lettre a.

3\ Représentation des automates :

Les automates d’états finis sont souvent représentés par des
graphes orientés mais peuvent aussi être représentés par des
matrices
Remarque : Un AEF possède un seul état initial mais peut
avoir plusieurs états finaux

4\ Fonction de succession de transitions :

Soit A = (X, Q, q0, σ, F) un automate d’états fini
déterministe. On étend naturellement, la fonction
de transition σ à la fonction de succession de
transitions σ* comme suit :
• σ*(q, σ) = q
• σ*(q, a) = σ(q, a) a ∈ X
• σ*(q, aw) = σ*(σ (q, a),w) a ∈ X et w ∈ X*
Remarque : Un mot est reconnu si et seulement si :
- l’automate a terminé la lecture du mot
- et se trouve dans un état final (état d’acceptation)

5\ Equivalence de deux AEF :

Deux automates d’états finis A1 et A2 sont équivalents, noté
A1 ≡ A2, si et seulement s’ils acceptent le même langage.
A1 ≡ A2 ⇔L(A1) ≡ L(A2)

Remarque : Un langage peut être reconnu par plusieurs

automates. Par contre un automate ne peut reconnaitre qu’un
seul langage.
6\ Variantes des automates d’états finis :
Il existe plusieurs variantes d’automates d’états finis :
1) Les automates simples déterministes.
2) Les automates simples non-déterministes.
3) Les automates généralisés.

1) Les automates simples déterministes : On dit qu'un

automate est déterministe si pour tout état et symbole en entrée
donné, l'automate ne peut passer
qu'à un seul état suivant

Remarque : Dans les automates

déterministes, il n y'a pas de choix à
faire pour l’état suivant après la
lecture d’un certain symbole.

Un automate déterministe est dit

complet ssi : à toute paire (q,a) la
fonction σ associe exactement un
état.

Remarque : Dans un automate complet, il y a possibilité de lire

n’importe quel symbole à partir de n’importe quel état.

Exemple : cet automate est déterministe

mais non complet, car en effet, dans l’état
q0, on ne peut pas lire la lettre b.
Le langage reconnu par cet automate
est : { abn / n ≥0 }
Pour rendre complet un automate
déterministe non complet il suffit de :
rajouter un état, appelé états puits
généralement noté ∅, et de rajouter
toutes les transitions manquantes vers
cet état.

Remarques :
- Un automate déterministe complet permet de lire tous les
mots de l’alphabet (pas nécessairement les reconnaitre)
- L’automate complet obtenu reconnaît le même langage que
l’automate initial (l’état puits n’est pas un état final).

2) Les automates simples non déterministes :

ce type d'automate permet plusieurs transitions correspondant
à la même lettre à partir des états de
l’automate.

Dans cet exemple, à partir de q0, on a le

choix entre deux transitions par a : l’une
vers q1 et l’autre vers q3.
Donc, σ (q0, a) = {q1, q3}

Remarque : Dans les automates non

déterministes, un choix est permis
pour passer à l’état suivant.
3) Les automates généralisé :
Dans un automate généralisé, les transitions directes peuvent
être causées par des mots (jusqu’à maintenant, les transitions
se faisaient en lisant un seul symbole à la fois).

Exemple :
À l’état q1, on a 3 possibilités :
• lire a et rester dans q1
• lire abb et passer à q2
• passer directement à q3 sans
lecture.

Remarques :

- Un état q est accessible s'il existe

un chemin de l'état initial de
l'automate vers q.

- Un état q est co-accessible

s'il existe un chemin de l'état q
vers un état final.

- Un automate est émondé si

tous ses états sont accessibles
et co-accessibles, pour rendre
un automate émondé, il suffit
de supprimer tous les états non
accessibles et non
co-accessibles.
7\ Automate simple vs généralisé :
Par opposition aux automates généralisés, les automates
déterministes et non déterministes sont dits simples (toutes les
transitions se font en lisant une seule lettre à la fois)

En pratique, les automates simples déterministes, sont très

intéressants pour la reconnaissance des mots. Donc, l’idéal
serait de transformer n’importe quel type d’automate, vers un
automate déterministe, cette transformation se fait en 2 étapes :

1- Transformer un automate généralisé vers un automate

simple (déterministe ou non déterministe)

2- Transformer l’automate simple vers un automate

déterministe (s’il ne l’est pas déjà)
8\ Étapes de transformation :
1- éliminer les transitions par mot en ajoutant des états
intermédiaires.
2- éliminer les transitions spontanées ε-transition
3- regrouper les transitions
4- ajouter les états finaux

Pour réaliser ces transformations on utilise la table des

transitions pour éviter toutes erreurs

Remarque : on peut déduire la grammaire d'un langage à partir

de son automate par les règles suivantes :

Les états = les non terminaux (N)

L’état initial = l’axiome (S)

Les lettres lues par transition = les terminaux (T)

Les transitions = les règles de productions (P)

Chaque état final est représenté par une production d’arrêt

avec epsilon.
9\ Création d'automate à partir d'autres automates :
Soit l'automate A qui reconnait le langage L, pour trouver les
automates qui reconnaissent les langages suivants on doit :

L\ :
- ajouter un état puit pour rendre l'automate complet
- inverser les états finaux et non-finaux
- l'état initial ne change pas

Lr :
- inverser le sens des transitions
- inverser entre l'état final et initial
- si on a plusieurs états finaux on créé un nouvel état initial qui
pointera vers les anciens états finaux avec ε

L1 U L2 :
- ajouter un nouvel état initial qui pointera avec ε vers les états
initiaux de L1 et L2 qui deviendront des états normaux

L1.L2 :
- l'état final de L1 n'est plus final et pointe désormais vers l'état
initial de L2
 LES EXPRESSION RÉGULIÈRES

1\ Introduction :
Les langages réguliers sont les langages générés par des
grammaires de type 3 appelées grammaires régulières et
reconnus par des automates d’états finis, les mots de ce
langage possèdent une forme particulière et peuvent être
dénotés par des expressions régulières

2\ Définition :
Une expression régulière est une suite de caractères qui décrit
ou dénote un ensemble de mots.

Si r et s sont deux expressions régulières sur X décrivant

respectivement les langages R et S alors :

• r+s est une expression régulière qui décrit le langage R U S

• r.s est une expression régulière qui décrit le langage R.S
• r* est une expression régulière qui décrit le langage R*
• (r) est une expression régulière qui décrit le langage (R)

Priorité des opérateurs : étoile * > concaténation . > addition +

Remarque : deux expressions régulières E1 et E2 sont

équivalentes, notées E1 ≡ E2, si et seulement si elles dénotent
le même langage.
Exemple :
E1= (a+b)(a+b)*
E2= (a+b)*(a+b)
Dans les deux cas, le langage dénoté est une suite aléatoire de
a et b avec au minimum une lettre a ou b, donc E1 ≡ E2

3\ Propriétés :
1. Commutativité : p+q ≡ q+p
2. Associativité : p+(q+r) ≡ (p+q)+r p(qr) ≡ (pq) r
3. Distribution : (p+q)r ≡ pr + qr p(q+r) ≡ pq + pr
4. Elément neutre : p.ε ≡ ε.p ≡ p p+∅ ≡ ∅+p ≡ p
5. Elément absorbant : p.∅ ≡ ∅.p ≡ ∅
6. ∅* ≡ ε
7. (p*)* ≡ p*
8. (p*+q*)* ≡ (p*.q*)* ≡ (p+q)*
9. p. p* ≡ p*.p
10. p* ≡ (p+ε)*

4\ Conclusion :
Pour démontrer qu’un langage est régulier on dispose de 3
méthodes, il faut lui trouver soit :

1) une grammaire régulière qui le génère

2) un automate d’état finis qui le reconnait
3) une expression régulière qui le dénote.
 LES LANGAGES ALGÉBRIQUES

1\ Introduction :
Les langages réguliers sont excellents mais possèdent malgré
tout quelques défauts par exemple ils ne peuvent pas exprimer
les mots de la forme anbn de plus les AEF ne possèdent pas de
mémoire, pour résoudre ces problèmes on a inventé les
langages algébriques

2\ Définition :
Un langage est dit algébrique s'il existe une grammaire
algébrique qui le génère, pour rappel une grammaire est une
grammaire algébrique si et seulement si toutes ses règles sont
de la forme : A α avec A ∈ N et A ∈ (T U N)*

3\ Les automates à piles :

Ce type d'automate possède la
particularité d'avoir une pile comme
unité de stockage, un automate à
pile est un septuplet
P = (Σ, Γ, Z0, Q, q0, F, σ) où :

• Σ : l'ensemble fini de l’alphabet d’entrée

• Γ : l'ensemble fini de l’alphabet auxiliaire
• Z0 ∈ Γ : le symbole initial de la pile
• Q : l'ensemble fini d’états et q0 ∈ Q l’état initial
• F⊆ Q : l’ensemble des états finaux.
• σ est une fonction de transition qui prend comme argument un
triplet (u, q, a) où :
• u est le sommet de la pile
• q est un état de Q
• a est un symbole d’entrée de Σ ou le mot vide.
Et qui retourne une paire (α, p) où :
• α est un mot sur (Σ U Γ)* (le contenu en haut de la pile)
• p est le nouvel état

Remarque : Σ U Γ constitue l’alphabet du langage de la pile.

1) Si α = v1....vn alors σ (u, q, a) = (v1...vn, p) : le sommet de

pile est dépilé, ensuite on empile v1, ... et vn dans cet ordre, le
sommet de pile contiendra vn

2) Si α = u alors σ (u, q, a) = (u, p) : la pile reste inchangée

3) Si α = ε alors σ (u, q, a) = (ε, p) : on dépile seulement le

sommet de la pile

4\ Modes de reconnaissances :
Un mot peut être reconnu de 2 manières : par état final ou par
pile vide, dans la configuration finale :
• Le contenu de la pile n’a pas d’importance.
• Le mot d’entrée a été entièrement lu.
• L’automate se trouve dans un état final.