I.1
Alphabet, Mots, Langages
Pour mieux
comprendre cette notion de langage, il faut la comparer à une langue et aux composants
d’une langue ; car comme une langue, un langage comporte de caractère ou
des symboles dont l’ensemble forme l’alphabet, des mots définis sur cet
alphabet, en d’autres termes des mots formés de symboles de l’alphabet, et
l’ensemble de mots est ainsi appelé langage.
L’alphabet
contient des entités les plus élémentaires,
des symboles utilisés par le langage.
Un alphabet est
un ensemble fini non vide. Un alphabet sera en général désigné par une lettre
majuscule (grecque, de préférence).
Ainsi, Σ = { a,
b, c } , Γ = {♥ , ♦ , ♣ , ♠} , Δ = { 0, 1 } , Φ = {→ , ← , ↑ , ↓} Sont des alphabets. Les éléments d’un alphabet
sont appelés lettres ou symboles ou caractères.
Exemple (autres)
:
-
∑ = {a, b, c, d … z}
-
∑ = {0, 1, 2... 9}
-
∑ = {a, f, d, x}
-
∑ = {b, c, 0, $, μ, z}
-
∑ = {ab, de, xyz}
-
∑ = {abc, a, tuv, vu}
·
On considère les éléments comme
atomiques : « abc » peut-être un symbole unique pour un
langage ;
·
Pas de répétitions au sein d'un
alphabet (car, c’est un ensemble) ;
Mais, l’idéal est que les éléments de l’alphabet soit fait d’un
seul symbole, et c’est la représentation-là que nous allons utiliser dans ce
cours.
·
Un élément de l’alphabet peut déjà aussi
bien être un mot ; c’est le cas des mots du langage à un seul caractère.
·
La concaténation «.» ou la suite de symboles issus d'un alphabet,
forme un mot :
-
Soit α un mot
-
∑ = {0, 1} : α1 = 0.0.1.0,
α2 = 1.0.0.0.1.0 ... sont des mots
-
Associative : (a.b).c = a.(b.c)
-
Non commutative : 0.1 ≠ 1.0
·
Quel que soit l'alphabet, il est
possible de former le mot (ou chaîne) vide, noté « ε » (différent de ∅)
·
Taille ou longueur d’un mot : |x|, nombre
de symboles :
-
|0.1.0.0| = 4 (∑= {0, 1})
-
|d.d.ab.ab.d| = 5 (∑= {ab, d})
-
|ε| = 0 (∀ ∑)
Nota : Le
signe de concaténation est souvent utile lorsque l’alphabet contient des éléments
de plus d’un symbole, afin de marquer leur délimitation ; mais lorsque
l’alphabet a des éléments comportant un seul symbole, alors le signe de
concaténation peut être enlevé :
-
(a.b) = (ab), (∑ = {a, b})
·
Ensemble de mots
L’ensemble de tous les mots
(possibles) sur un alphabet ∑ est noté ∑* (on l’appelle la fermeture) ; on
peut le noter aussi ∑+ si le mot vide (ε) est exclu
Par exemple, si ∑ = {a, b, c},
∑*= {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,
...}
∑+= {a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa,
aab, ...}
· Opérations sur les mots
-
Concaténation (produit) de lettres
Soit un alphabet X et w1,
w2 ∈ X* tels que :
w1 = x1x2x3…xn
∀ i ∈ {1,…, n}, xi ∈ X
w2 =
y1y2y3…yp ∀ i ∈ {1,…, p}, yi
∈ X
w1 et w2 sont des concaténations de lettres (mots).
-
Concaténation (produit) de mots
Soit un alphabet X et w1,
w2 ∈ X* des concaténations de
lettres. Alors w tel que :
w = w1.w2 = x1x2x3
… xny1y2y3 … yp est une concaténation de mots.
-
Puissance
Soit un alphabet X et w ∈ X*.
Par exemple, soit X = {a, b} et w =
abb
§
w0 = ε
§
w1 = abb
§
w2 = abbabb
-
Egalité de deux mots
Deux mots sont égaux s’ils sont une
même longueur et que leurs lettres se trouvant à de mêmes positions sont
identiques.
Soit un alphabet X et w1,
w2 ∈ X* tels que :
w1 = x1x2x3…xn
∀ i ∈ {1, … n}, xi ∈ X
w2 =
y1y2y3…yp ∀ i ∈ {1,…, p}, yi
∈ X
On a w1 = w2 si
et seulement si p = n et ∀ i ∈ [1, n], xi = yi.
-
Préfixe, suffixe
Soit un alphabet X et w, u ∈ X*.
u est un préfixe de w si et seulement si ∃ v ∈ X* tel que w = u.v
u est un suffixe de w si et seulement si ∃ v ∈ X* tel que w = v.u
Soit X = {a, b}, w = babb
Les préfixes de w sont
, b, ba, bab, babb
Les suffixes de w sont
, b, bb, abb, babb
-
Préfixe et suffixe propres
Soit un alphabet X et w, u ∈ X*.
u est un préfixe propre de w si et
seulement si u est un préfixe de w et u est différent de w.
u est un suffixe propre de w si et
seulement si u est un suffixe de w et u est différent de w.
Soit X = {a, b}, w = babb
Les préfixes propres de w sont
, b, ba, bab
Les suffixes propres de w sont
, b, bb, abb
-
Miroir d’un mot
Soit un alphabet X et w ∈ X* tel que w = x1x2x3
… xn, avec ∀ i ∈ {1,… ,n} , xi ∈ X.
Le miroir de w, noté
, est défini par :
= xnxn−1
… x2x1
Définition récursive :
Un langage L
sur un alphabet X est un sous-ensemble
de X*, L ⊂ X*. C’est donc un
ensemble de mots.
Soit X = {a, b}
un alphabet.
o
∅ est un langage
o
{ε} est un langage
o
{a, ba, bba} est un langage
o
{w ∈ X* | w = an, n
∈ IN} est un
langage
Nota : Un
langage, en tant qu’ensemble de mot, peut être défini en compréhension c.à.d.
littéralement par une phrase décrivant sa spécification, ou en extension c.à.d.
en citant à l’intérieur des accolades les éléments (mots) du langage, ce qui
n’est pas toujours possible car un langage peut être un ensemble fini ou non
fini.
-
Concaténation : « A.B » (ou AB) mots formés d’un mot de A suivi d’un mot de B,
A, B ⊆ X*, A.B = {w ∈ X* | w = xy, x
∈ A et y ∈ B}.
-
Union : « A ∪ B »
(ou A + B) mots issus soit de A soit de B,
A, B ⊆ X*, A ∪ B = {w ∈ X* | w ∈ A ou w ∈ B}.
o
Associative
o
Commutative
o
Elément neutre : ensemble vide ∅
o
Notée « + » dans la théorie
des langages
-
Intersection : « A ∩ B » :
mots qui existent dans A et dans B,
A, B ⊆ X ∗, A ∩ B = {w ∈ X* | w ∈ A et w ∈ B}.
o
Associative
o
Commutative
o
Elément neutre : X*
-
Différence : « A \ B » :
mots qui existent dans A mais pas dans B,
A, B ⊆ X*, A \ B = {w ∈ X* | w ∈ A et w
B}.
-
Complémentaire : «
» : mots de X* qui ne sont pas dans A
A ⊆ X*,
= X*\ A = {w ∈ X* | w
A}
-
Egalité : Deux langages A, B ⊆ X* sont égaux, noté A = B, si et seulement si A ⊆ B et B ⊆ A.
-
Fermeture de Kleene :
Soit A ⊆ X*. On note A* =
l’opération
étoile (ou fermeture par étoile, ou fermeture de Kleene, ou fermeture
itérative) du langage A.
Note : Ai
= {w ∈ X* tel que |w|
= i}
Exemple : soit ∑= {a, b}
A0 = {ε}, on a toujours le
mot vide (ε) ∈ A*
A2 = {aa, bb, ab, ba}
-
Fermeture positive :
Soit
A ⊆ X*. On note A+ =
la fermeture
positive du langage A.
Théorème : Soit A ⊆ X*. On a A+
= A.A* = A*.A
-
Opération miroir :
Soit A ⊆ X*. On définit l’opération
miroir comme étant
= {
| w ∈A}.
L’opération miroir peut également
être noté AR = {
| w ∈ A}.
Théorème : Soit A, B ⊆ X*. On a (A.B)
R = BR.AR
Nous
distinguons quatre (4) types de langages
selon la hiérarchie de Noam Chomsky
(Linguiste américain – né en 1928 – fondateur de la grammaire
générative) :
-
3 - Langages rationnels : RAT(X*)
-
2 - Langages algébriques :
ALG(X*)
-
1 - Langages contextuels : CS(X*)
-
0 -
Langages récursivement énumérés : RE(X*)
C’est cette
classification qu’on appelle « hiérarchie de Chomsky »
Figure 1 : Hiérarchie de Chomsky
Dans la suite
de ce cours, nous n’allons beaucoup plus parler que des deux (2) premiers types
de langages (rationnels et algébriques), ainsi que de leurs outils.
Figure 1 : Hiérarchie de Chomsky
|