Scribd
Importer
127 vues15 pages

0 - CH 1 - Mots Et Langages

Ce document définit les notions de base des langages formels et des automates. Il présente les définitions d'alphabet, de mot, de langage formel et décrit les opérations élémentaires sur les langages comme l'union, l'intersection ou la concaténation.

Transféré par

Dhia Snoussi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
127 vues15 pages

0 - CH 1 - Mots Et Langages

Ce document définit les notions de base des langages formels et des automates. Il présente les définitions d'alphabet, de mot, de langage formel et décrit les opérations élémentaires sur les langages comme l'union, l'intersection ou la concaténation.

Transféré par

Dhia Snoussi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
Vous êtes sur la page 1/ 15

Théorie des langages et des

automates

Année Universitaire 2020/2021


Définitions - Alphabet

 Un alphabet  est un ensemble dont les éléments sont des symboles (lettres par
exemple).
 Les alphabets sont toujours supposes finis.
 Exemples :
 1  {0; 1}
 2  {A; C; G; T}
 3  {a, b, c, …, x, y, z} : l’ensemble de toutes les lettres (minuscules)
 4  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, , , , , (, )}.
 5  {♠, ♣, ♥, ♦}
 etc.

2
Définitions - Mots

 Un mot (ou encore chaîne) w est une suite finie de symboles d’un même alphabet
que l'on note par simple juxtaposition : w  a1a2 ... an; ai  
 Exemples :
 w 1  10110 est un mot de 1

 w 2  ordinateur est un mot de 3

 w 3  (7  6)  3 est un mot de 4

3
Définitions - Mots

 La longueur d'un mot w est le nombre de symboles qui le composent, et est notée
|w|.
 Le mot vide, noté , est composé de 0 (zéro) symboles.
 ||  0
 Le produit de concaténation de deux mots x  a1a2 …an et y  b1b2 … bm est le
mot xy obtenu par juxtaposition : xy  a1a2 …an b1b2 … bm
 |xy|  |x| + |y|.

4
Définitions - Mots

 n est l’ensemble de toutes les chaînes de longueur n.


 0  {} ; cet ensemble n’est pas vide. Il contient la chaîne vide .
 * est la réunion des n pour n  0. C'est donc l'ensemble de toutes les
chaînes, chaîne vide comprise.
 La fermeture de Kleene d’un alphabet est l’ensemble de tous les mots de longueur
quelconque de , on la note *.
 + est la réunion des n pour n > 0.
 L’ensemble des mots non vide construits sur  est la fermeture positive de  et est
noté +.

5
Définitions - Mots

 Un mot x est une sous chaîne d’un mot w si et seulement si il existe deux mots y
et z tels que w  yxz. Les mots w, x, y et z doivent appartenir à un même
alphabet.
 Un mot x est préfixe d’un mot w si et seulement si il existe un mot y définit sur le
même alphabet  que x et w tel que w  xy.
 Un mot x est suffixe d’un mot w si et seulement si il existe un mot y définit sur le
même alphabet  que x et w tel que w  yx.

6
Définitions – Mots

Concaténation : pour tout m, n  *, l’opération de concaténation  est définie par :


 : Vm  Vn  Vm + n
(x1 … xm, y1 … yn)  x1…xm  y1…yn  x1…xmy1…yn
 La concaténation est associative : (w1  w2)  w3  w1  (w2  w3)

  est l’élément neutre pour la concaténation w      w  w

Exemple
  {a, b} w  babb
 Les préfixes de w  , b, ba, bab, babb

 Les suffixes de w  , b, bb, abb, babb

7
Définitions – Mots

Puissance : soit un alphabet  et w  *,

wn  {  si n  0
w  wn – 1

Exemple

  {a, b} w  aab
 w0  
 w1  aab
 w2  aabaab
 w3  aabaabaab

8
Définitions – Mots

 Soit  un alphabet. Soit A une partie de . Pour tout mot w  *, la longueur en
A de w est le nombre d'occurrences de lettres de A dans le mot w. Ce nombre est
note |w|A.
 |w|  |w|∑.
 Pour tout symbole   , |w| le nombre d’occurrences du symbole  dans w.

9
Définitions - Mots

 Occurrence de symboles : nombre de fois où un symbole apparait dans un mot. On


note |w| le nombre d’occurrences du symbole  dans w.
 Miroir : Soit w  a1 … an, avec a1; … ; an  . Le mot miroir de w est le mot note
~ ou w~ ou encore wr défini par :
w
w  an … a1
~~
 (uv)~  vu
 (w~)~  w.

10
Définitions - Langage

 Un langage défini sur un alphabet  est une partie de * c’est donc un ensemble
de mots défini sur .
 Un langage L sur un alphabet  est un sous ensemble de * : L  *
 L  P (*)
 Les sous-ensembles de * sont appelés des langages formels.
Exemple   {a, b}, {anbn / n  0} est un langage.
 Exemples triviaux :
 Ø, le langage vide.
 {}, le langage réduit à l’unique chaîne vide.
 L1  {w  * / w  w~}
 L2  {w  * / |w|  2k, k  0}
 L3  {w  * / |w|a  2k, k  0}

11
Opérations sur les langages
 Union
L1 ∪ L2  {w  * / w  L1 ou w  L2}
 Intersection
L1 ∩ L2  {w  * / w  L1 et w  L2 }
 Complèmentaire
Lc  * \ L  {w  * et w  L }
 Différence
L1 \ L2 (ou L1 – L2)  {w  * / w  L1 et w  L2 }
 Concaténation
L1.L2  {w  * /  u  L1 et v  L2 / w  u.v}
L{}  {}L  L
L (M ∪ N)  L(M) ∪ L(N)
L (M ∩ N)  L(M) ∩ L(N)

12
Opérations sur les langages

 Puissances
L0  {}
L1  L
Ln + 1  LnL (n 1)
Si  est un alphabet alors n est l’ensemble des mots de longueur n.
Itération (étoile) L* n∪ 0Ln  {w1 … wn / n  0 et w1, … wn  L}
Itération stricte (plus) L+  ∪ Ln  {w1 … wn / n > 0 et w1, … wn  L}
n>0

13
Opérations sur les langages: Exemples

   {a, b}
 L1  {a, b}
 L2  {aa, bb, ab, ba}
 L3  {a, ab, bb}

L1 ∪ L2  {a, b, aa, bb, ab, ba}


L1 ∩ L2  Ø
L1 ∩ L3  {a}
L1 \ L2  {a, b}
L3 \ L1  {ab, bb}
L1.L2  {aaa, abb, aab, aba, baa, bbb, bab, bba}

14
Opérations sur les langages : Propriétés

Soient A, B et C trois langages définis sur un alphabet 


 A.(B.C)  (A.B).C

 A ∪ (B ∪ C)  (A ∪ B) ∪ C

 A.(B  C)  A.B  A.C

 A. Ø  Ø

 A  Ø  A

 A  B  A.C  B.C

 A  B  C.A  C.B

15

Vous aimerez peut-être aussi