Cours ThÃ©orie de Langag

Théorie des langages et Compilation
Théorie des langages

Pr. Saïd Ouatik El Alaoui
• [email protected]
1
Plan
I. Préliminaire
II. Automates Finis Déterministes (DFA)
III. Automates finis Non déterministes (NFA)
IV. Expressions régulières (ER)
V. Grammaires à contexte libre

[email protected]
2
Chapitre 1
Préliminaire
• Pr. Saïd Ouatik El Alaoui
3
I. Préliminaire
I.1. Chaînes, alphabets et langages
-Définitions:
- Un symbole est une entité abstraite qui ne peut pas être
définie formellement comme les lettres, les chiffres…
- Un mot (ou encore une chaîne ) est une séquence finie de
symboles juxtaposés.
-Exemples :
- a, b, et c sont des symboles.
- ab et abc sont des chaînes (mots).
4
I. Préliminaire
• Un alphabet est un ensemble fini non vide de symboles noté souvent .

La longueur d’une chaîne est le nombre de symboles de cette chaînes, notée | |.
• Exemple: |abc|=3
• La chaîne vide, notée , est la chaîne ne contenant aucun symbole.

• On a: ||=0.
• Un préfixe de longueur k d’une chaîne w de longueur n (avec kn) est une
chaîne constituée par les k premiers symboles de w (lus de gauche à droite).
5
I. Préliminaire
I.1 Chaînes, alphabets et langages
Exemple: si w=abcde alors
• w0=a, w1=ab, w2=abc, w3=abcd, w4=abcde sont tous les préfixes de w.
• Un suffixe de longueur k d’une chaîne w de longueur n (avec k  n) est une

chaîne constituée par les k derniers symboles de w.
• Exemple: si w=abcde alors

w0=e, w1=de, w2=cde, w3=bcde, w4=abcde sont tous les suffixes de w.
6
I. Préliminaire
Un préfixe (ou un suffixe) d’une chaîne est dit préfixe propre (ou suffixe propre)
s’il est différent de la chaîne elle-même.
• Définition: Concaténation
• La concaténation de deux chaînes w1 et w2 est la juxtaposition de deux chaînes,
ainsi la chaîne obtenue est formée par la première (w1) suivie de la deuxième (w2).
On note w1.w2
Exemple: si w1=abc, w2=xyzt alors w1.w2=abcxyzt
• N.B. Pour tout mot w on a: w. = .w=w
7
I. Préliminaire
Définition : Langage
Un langage est un ensemble de chaînes dont les symboles sont pris

dans un certain alphabet.
• Notations :
• * est l’ensemble de toutes les chaînes formées à partir de l’alphabet
 y compris .
• += *-{}
• L est un langage sur  signifie que L  *.
8
I. Préliminaire
• Exemples :
•  et {} par définition sont des langages.
• ={a}, La={a, aa, aaa}
• ={a},  *={ , a, aa, aaa, …}
• si ={0, 1},  *={ , 0, 1, 00, 01, 11, 10, …}
L’ensemble des mots palindromes sur :
P={w*/ si w est lue de gauche à droite ou de droite à gauche le
résultat est le même}.
Exemples :
-  est palindrome.
- w=abba est palindrome.
- w=01010 est palindrome. 9
I. Préliminaire
~
• wR est l’inverse de w, noté aussi w.
• wR est appelé le miroir de w.
• si w=wR alors w est palindrome.
Remarques:
- La concaténation (notée par . ) est une opération associative mais non

commutative.
- * est fermé par la concaténation.

Si u* et v* ➔ u.v *
10
I. Préliminaire
I. Chaînes, alphabets et langages
- Concaténation de langages :
• Soit A et B  *
A.B={w1.w2/ w1A, w2B}.
• Exemple 1: ={a, b}
L1={aba, ab}, L2={ba, a}
Alors : L1.L2={ababa, abaa, abba, aba}
• Exemple 2: ={a, b}
L={aba, ab}
Alors : L.L={abaaba, abaab, ababa, abab}
Notation: L.L est noté L2
11
I. Préliminaire
I. Chaînes, alphabets et langages
- Concaténation de langages :
Soit A un langage sur 
• Généralisation :
• A0={}.
• Ai=Ai-1.A pour i>0 appelée Puissance de A
•A*=i≥0Ai, appelée fermeture de A (ou aussi fermeture de Kleene)
• A+=i≥1Ai appelé fermeture positive de A.
12
I. Préliminaire
- Cas particulier: On a *= i≥0 i
•Remarque :   L+ s.s.s L
Propriétés:
• Soient u, v  * On a :
u=v  |u|=|v| et  1 i  |u| on a: ui=vi
• Pour u  * On a :
Si |u|=0 alors u= 
Si |u|=r alors u=u1.u2.u3….ur avec ui  .
Remarque : Les opérations habituelles sur les ensembles telles que l’union,
l’intersection et la complémentation sont applicables aux langages.
13
Chapitre 2
Automates Finis Déterministes

(DFA)
14
II.1. Concept d’automate fini déterministe
Définition:
On appelle DFA un cinq_uplet M de la forme (, Q, ,q0, F) avec :
: Alphabet d’entrée.
Q: ensemble fini d’états.
q0Q état initial.
F  Q ensemble des états finaux.
 : Q  → Q : fonction de transition.
- Exemple 1:
 ={a, b}
Q={q0, q1, q2}
q0 : état initial 15
II.1. Concept d’automate fini déterministe
- Exemple 1: (suite)
b
a
q0 q1
b
a, b
a  a b
q2 q0 q1 q0
q1 q2 q0
q2 q2 q2
• q2 est l’état final.
• La fonction de transition peut être représentée par un tableau de transition.
16
II.2. Langage reconnu par un DFA
Extension de :
: Q * → Q
(q, w) → q’
(q, )=q
Si |w|>0 alors (q, w)= (q, xu)= ((q, x), u) avec x   et u  * .
Exemple: (q0, aa)=q2

q0*aa=q2
17
Définition: Langage reconnu par un DFA
Soit M=(, Q, , q0, F) un DFA.
T(M)={w  * / (q0, w) F}
Exemples:
(q0, ab)=(q1, b)=q0 ➔ abT(M).
aa T(M) car (q0, aa)F
Notation :
La fonction de transition est notée par * :
(q, w)=q*w
18
Exemple 1: On a: q0*abaabaa=q2 F alors abaabaa T(M)

T(M)= *aa*
- Exemple 2:  ={a, b}
a a
b
q0 q1
T(M)=?
19
T(M)= est l'ensemble des mots contenant un nombre pair de b
T(M)= {w  * / | w|b pair}
| w|b : désigne le nombre d’occurrences de b dans le mot w.
• Définition: Langage régulier

Un langage L sur  est dit régulier s.s.s il existe un DFA tels que :
L=T(M).
Notation :
Reg(): est l’ensemble des langages réguliers sur  .
20
• Exercice:
Soit ={a, b}
1) Montrer que * est régulier.
2) Même question pour +
21
• Exercice:
Soit ={a, b}
a, b
q0
2) Même question pour +
22
• Exercice:
Soit ={a, b}
a, b
q0
2) Même question pour + a, b

a, b
q0 q1
23
3) L= L’ensemble des mots se terminant par a

Donner 1 DFA reconnaissant L.
24
II.3. Union et intersection de langages réguliers
Proposition :
Si L1 et L2  Reg() alors L1L2 et L1L2  Reg().
c.à.d: L’union et l’intersection de deux langages réguliers sont réguliers.
Exemple :  ={a, b}
Soient M1 un DFA pour L1: l’ensemble des mots w tel que |w|a pair.
Soient M2 un DFA pour L2: l’ensemble des mots w tel que |w|b pair.
25
- Exemple (suite):
b b
a
M1 q0 q1
a a
b
q0’ q1’
M2
b
26
- Exemple (suite): Construction d’un DFA pour L1  L2.
a
q0,q0’ q1,q0’
a
b b b
b
a
q0 ,q1’ q1, q1’
27
- Exemple (suite) : Construction d’un DFA pour L1  L2.
a
q0,q0’ q1,q0’
a
b b b
b
a
q0 ,q1’ q1, q1’
28
- Exercice :
Soient deux DFAs M1 et M2 tels que:
M1=(, Q1, *, q0, F1) , L1=T(M1)
M2=(, Q2, *’, q0’, F2) , L2=T(M2)
1) Donner les règles de construction d’un DFA pour L1  L2.
2) Même question pour L1  L2.
3) Le complémentaire d’un langage régulier est-il régulier?
4) Déduire que L1-L2 est régulier.
29
II.4. État puit
-Définition: état puit
M=(, Q, ,q0, F) un DFA. Un état q est dit état puit si  w  * on a: q*wF.
a
q0, q1
b a, b a, b
q2
q2 est un état puit
Exemple :
Soit  ={a, b} un alphabet.
Donner un DFA reconnaissant l’ensemble des mots ne contenant pas ‘aa’.
30
II.4. État puit
Exercice :
Soit  ={0, 1} un alphabet.
Donner un DFA reconnaissant l’ensemble des mots ne contenant pas le
sous mot ‘00’.
31
II.4. État puit
- Remarques:
• Un DFA peut avoir plusieurs états puits.
• Si L est régulier et R  L. Alors R n’est pas forcément régulier.
Exercice :
Soit un DFA, M=( , Q, -, q0, F).
• Étant donné un mot w sur , donner un algorithme permettant
de tester si w est reconnu par M.
• Étant donné un état q, écrire un algorithme permettant de tester
si q est un état puits.
32

Cours ThÃ©orie de Langag

Transféré par

Droits d'auteur :

Formats disponibles

Cours ThÃ©orie de Langag

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours ThÃ©orie de Langag

Transféré par

Droits d'auteur :

Formats disponibles

Théorie des langages et Compilation

Théorie des langages

II. Automates Finis Déterministes (DFA)

III. Automates finis Non déterministes (NFA)

IV. Expressions régulières (ER)

V. Grammaires à contexte libre

• Un alphabet est un ensemble fini non vide de symboles noté souvent .

• La chaîne vide, notée , est la chaîne ne contenant aucun symbole.

• Un suffixe de longueur k d’une chaîne w de longueur n (avec k  n) est une

• Exemple: si w=abcde alors

• N.B. Pour tout mot w on a: w. = .w=w

Un langage est un ensemble de chaînes dont les symboles sont pris

- La concaténation (notée par . ) est une opération associative mais non

- * est fermé par la concaténation.

Automates Finis Déterministes

Exemple: (q0, aa)=q2

Exemple 1: On a: q0*abaabaa=q2 F alors abaabaa T(M)

• Définition: Langage régulier

2) Même question pour +

2) Même question pour +

2) Même question pour + a, b

3) L= L’ensemble des mots se terminant par a

Vous aimerez peut-être aussi