Théorie des Langages et Compilation

Cours 1 : Les Langages

Dr MAMBE
 Plan du cours

I. Alphabet
II. Mot
1. Définition
2. Opérations sur les mots
III. Langage
1. Définition
2. Opérations sur les langages

2
 Introduction

De manière générale, les langages sont les supports naturels

de communication. Ils permettent aux hommes d’échanger
des informations. Ils leur permettent également de
communiquer avec les machines.

Les langages utilisés dans la vie de tous les jours entre êtres
humains sont dits naturels. Ils sont généralement informels
et ambigus et demandent toute la subtilité d’un cerveau
humain pour être interprétés correctement.

3
 Alphabet

Définition

Un alphabet ,noté X, est un ensemble fini non vide des éléments appelés
symboles.

Remarque

Un symbole est une entité abstraite qui ne peut pas être définie
formellement comme les lettres, les chiffres….

Exemple

• X = {0,1}, l’alphabet binaire.

• A= {a,b,c,….,A,B,…é,ç…}, l’alphabet de la langue française

• B={le,bon,lait,0,1,$} est un alphabet de 6 symboles.

4
 Mot
Définition

Un mot sur un alphabet X est une suite finie et totalement ordonnées

composées d'éléments de X.

Exemples

• 00, 11, 01001, 10000, 111, 101, ce sont des mots sur l’alphabet X=
{0,1}
• bon est un mot sur l’alphabet de la langue française et un symbole sur
l’alphabet X={le,bon,lait,0,1,$}. Donc, lebonlait est un mot de 3
symboles sur ce dernier alphabet.

5
 Mot
Définition

Notations

• Le mot vide, noté par ε, est le mot qui ne contient aucun élément d’un
alphabet X.

• L’ensemble des mots construits sur un alphabet X est un ensemble infini

noté X*.

• L’ensemble des mots construits sur un alphabet X qui ne contient pas le

mot vide est un ensemble infini noté X+ . On écrit :

X*=X+ ⋃ {ε}

6
 Mot
Définition

Exemple

Soit l’alphabet X= {a, b, c}, donc X* définit sur X est :

X*={ε, a, b, c, aa, bb, cc, ac, ab, ba, bc, ca, cb, aba, abb,…..}
={ε} ⋃{a, b, c} ⋃{aa, ab, bb,ba,cc,..}⋃{aaa, bbb, cccc,…}⋃…⋃{}
={ε}+{a, b, c} +{aa, ab, bb,ba,cc,..}+{aaa, bbb, cccc,…}+…+{}
Si on note: Xi l’ensemble des mots de longueur i construits sur l’alphabet X, donc on a:

7
 Mot
Longueur d’un mot

Définition:

Soient X un alphabet, w ∈ X* et x un des symboles constituant le mot w :

 |w| est la longueur du mot w.
 |w|x est le nombre de l’occurrence de x dans dans le mot w.

Exemple

X={a, b, c}, |abcbaa|=6, |abcbaa|a=3

8
 Mot
Opérations sur les mots

Concaténation
Soient deux mots w, w’ ∊ X*, la concaténation de w et w’ est définie comme la
juxtaposition de w et w’. Elle est notée par w.w’ on bien ww’.

Exemple

X= {0,1},
w=10, w’=00
w.w’=1000 ≠
w’w=0010

9
 Mot
Opérations sur les mots

Puissance d’un mot

Soit un alphabet X , w ∊X* et n ∊ IN, la puissance de w est donnée comme suit :

Exemple
Soit X= {a, b} et w = aba ,
• w0=ε
• w1=w. ε = w=aba
• w2=ww1=ww=abaaba
• w3=ww2=www= abaabaaba

10
 Mot
Opérations sur les mots

Factorisation d’un mot

Soit un alphabet X et w, u ∊X* :

• u est un facteur gauche (préfixe) de w  ∃ v ∊ X* tel que w =uv
• u est un facteur droit (suffixe) de w  ∃ v ∊ X* tel que w =vu
• u est un préfixe propre de w  ∃ v ∊ X+ tel que w = uv
• u est un suffixe propre de w  ∃ v ∊ X+ tel que w = vu

11
 Mot
Opérations sur les mots

Factorisation d’un mot

Exemple:
Soit l’alphabet X= {a, b}, et le mot w = babb :
• Les préfixes de w sont, b, ba, bab, babb
• Les suffixes de w sont, b, bb, abb, babb
• Les préfixes propres de w sont: b, ba , bab
• Les suffixes propres de w sont: b , bb , abb

12
 Mot
Opérations sur les mots
Inverse d’un mot ou Miroir

Le miroir d’un mot w= a1a2……an est le mot noté wR= an ……a2a1 obtenu en inversant les
symboles de w.

Exemple

Soit w=abbc un mot de l’alphabet x={a, b, c}, le mot miroir de w est wR=cbba.

Remarque

Le miroir de n’importe quel mot composé d’un seul symbole est le mot lui-même.
- Le miroir de mot vide est lui-même εR=ε.
- Un mot est un palindrome si wR = w , ex :(aba)R=aba.

13
 Mot
Opérations sur les mots
Relation d’ordre
On définit dans X* plusieurs relations d'ordre :

• Ordre préfixiel = ordre partiel défini par U < V ssi U est un facteur gauche de V.
• Ordre lexicographique (ordre du dictionnaire) = ordre total qui étend l'ordre
préfixiel
• Ordre hiérarchique= est un ordre total. Les mots sont classés d'abord par
longueur, puis pour les mots de
même longueur par ordre lexicographique (suppose que l'on a ordonné les lettres de
l'alphabet).

-> Sur la représentation graphique

Un mot précède un autre dans un

ordre hiérarchique s'il se trouve à un
niveau plus élevé ou bien étant sur le
même niveau s'il se trouve plus à
gauche que celui-ci.
14
 Langage
Définition

Un langage sur un alphabet X est une partie de X*. Donc un langage est un ensemble
de mots.
On note L ⊆ X * ou L ∊ P (X*).

 Exemple
 Soit l’alphabet X={a, b}
 ∅ est le langage vide, il ne contient aucun mot.
 {ε} est un langage.
 {a, b, aa, bb, aba} est un langage
 {w ∊ X* / w= an tel que n >0}={a,aa,aaa,aaaa,…..} est un langage

 Remarque
 Un langage sur un alphabet X peut être fini ou infini
 ∅ est un langage défini sur n’importe quel alphabet.

15
 Langage
Opérations sur les langages

Les langages étant des ensembles, toutes les opérations ensemblistes « classiques »
leur sont donc applicables.

Soient L1, L2 ⊆ X* : L1 ∪ L2= {w ∊ X* / w ∊ L1 ou w ∊ L2}

 Union

L’union de L1 et L2 est l’ensemble des

mots de L1 et L2 : Elle est :
 Associative.
 Commutative
 Elément neutre , le langage vide ∅ : L ∪ ∅=∅ ∪ L=L
 Elément absorbant, le vocabulaire X* : L ∪ X* =X* ∪ L=X*
 Notée + dans la théorie des langages. On écrit aussi : L1+L2= {w ∊ X* / w ∊ L1 ou
w ∊ L2}

16
 Langage
Opérations sur les langages

 Intersection

L’intersection de L1 et L2 est l’ensemble des mots qui appartiennent à la fois à L1 et L2 :

L1 ∩ L2= L2 ∩ L1= {w ∊ X* / w ∊ L1 et w ∊ L2}

Elle est :

 Associative
 Commutative
 Son élément neutre est X*
 Son élément absorbant est ∅ (puisque " ∀L : ∅ ∩ L=L ∩ ∅ = ∅)

17
 Langage
Opérations sur les langages

 Produit ou concaténation

Le produit des langages appelé aussi la concaténation des langages est le

résultat de la concaténation de chaque mot de L1 avec chaque mot de L2 (Ce n’est
pas le produit cartésien) :
Elle est :

L1. L2 = {u. v / u ∊ L1 et v ∊ L2}

Le produit est :
 Associatif
 Il n’est pas commutatif
 Son élément neutre est {ε}
 Son élément absorbant est ∅

18
 Langage
Opérations sur les langages

 Théorème
Le produit de langages est distributif par rapport à l’union

Attention ! : Le produit de langages n’est pas distributif par rapport à l’intersection.

19
 Langage
Opérations sur les langages

 Puissance
La puissance ou l’itération d’un langage est définit comme suit :

Attention ! Ne pas confondre Ln avec le langage contenant les puissances nièmes des
mots de L et qui serait défini par {u ∈ X⋆, ∃v ∈ L, u = vn}.

20
 Langage
Opérations sur les langages

 La fermeture positive
La fermeture positive de L noté L+ et on écrit

 La fermeture de Kleene
La fermeture étoile de L nommée aussi la fermeture de Kleene et notée L* est défini

• L*=L+∪{ε} et L+=L.L*

21
 Langage
Opérations sur les langages

 Exemple

Soit X= {0,1}, L1= {00, 11, 01} et L2= {01, 10}

 L1+ L2= {00, 11, 01, 10}
 L1 ∩ L2= {01}
 L1.L2 = {0001, 0010, 1101, 1110, 0101, 0110} ≠ L2.L1= {0100, 0111, 0101, 1000,
1011, 1001}
 L2 = {ε} +{L2} + {L2. L2} + {L2. L2.L2} +….. +{L2. L2.L2……. L2. L2.L2}

22
 Application

Soit l’alphabet A = {a, b}

Etant donnés les mots u = aa et v = bab
1. Ecrire les mots uv, (uv)2 et u3v.
2. Enoncer tous les mots de longueur 2 définis sur A.
3. Définir autrement les ensembles suivants:
E1 = {u.v / u ∈ A+, v ∈ A+} , E2 = {u.v / u ∈ A+, v ∈ A*} , E3 = {u.v / u ∈ A*,
v ∈ A *}

23