jeudi 18 juin 2015

Chapitre 1: Notion de langage



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*.  Cest 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 lopé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