8/6/2019 Thorie des langages 2010-2011
1/81
Thorie des langages. .
Mis jour par D. Chiadmi
Ecole Mohammadia dIngnieurs
Fvrier 2011
8/6/2019 Thorie des langages 2010-2011
2/81
date Contenu DevoirS15 Fri
S16 Mer. 23/2/11 Ch1 - Langages : vocabulaire, chanes, concatnation, langages,expressions rguliresCh2/1- Systmes de rcriture : grammaires, drivation,dfinition des langages, langage engendr par une grammaire
Jeu. 24/2/11 Ch2/2- Systmes de rcriture : Classes de grammaires,formalisme, Arbres de drivation, Ambigut, Dcidabilit,Exemple : Grammaires Expr arithmtique
S17 Mer. 2/3/11 Ch3/1 - Automates finis
2
Jeu. 3/3/11 Ch3/2 - Automates finis : Automates dterministes, minimaux Travail rendre
S18 Mer. 9/3/11 Ch4- Langages rguliers et langages dtat fini : automate ER
Jeu.10/3/11 Ch5- Dfinitions des langages par rcurrence : langage grammaireCh6 Automates piles
Remise dudevoir
S19 Mer. 19/3/11 Contrle continu
8/6/2019 Thorie des langages 2010-2011
3/81
Chapitre 1: Langages1. Vocabulaire, chanes Vocabulaire ou alphabet : un ensemble fini dlments
lments : lettres, caractres ou symboles / / x , , , , # V : Cardinal du vocabulaire V / / V = {, , } ; # V = 3
Chane est une suite ventuellement vide dlments dun
EMI D. Chiadmi - Thorie des langages S4 2011 33
vocabulaire // mot ou phraseEx : aba est une chane de V = {a, b}
est une chane de V = {, , }dbut x:=1 fin est une chane de V = {dbut, fin, :=, 1, x, }
Rq : ambigut entre chanes du vocabulaireEx: V= {a, aa} a aa avec aa a
8/6/2019 Thorie des langages 2010-2011
4/81
A. Notations
V0 = {} o est la chane videV1 = V // Si V = {a} alors V1 = {a }V* = Vi i 0 // Si V = {a} alors V* = {, a, aa, aaa, }
V+
= Vi
i >0 // Si V = {a} alors V+ = {a, aa, aaaa, }|x| : longueur dune chane x // | | = 4Vn : ensemble des chanes sur V de longueur n
EMI D. Chiadmi - Thorie des langages S4 2011 44
B. Sous chane
u sous chane de w si x, y V* tel que w = x u y
u prfixe de w si x = u suffixe de w si y =
8/6/2019 Thorie des langages 2010-2011
5/81
C. Opration sur les chanes
Concatnation de x et y note . donne x.y ou y.x
Proprits : associative - x, y, z V* x.(y.z) = (x.y).z
admet un lment neutre - x V* x. = .x = x
EMI D. Chiadmi - Thorie des langages S4 2011 55
.
Un langage sur un vocabulaire V est tout sous ensemble de V*
Proprits : Un langage L est infini ssi n N, x L | |x| > n
8/6/2019 Thorie des langages 2010-2011
6/81
8/6/2019 Thorie des langages 2010-2011
7/81
Expression de langage ? Comment exprimer un langage ?
Si petite taille : donner le vocabulaire et leschanes le constituant
EMI D. Chiadmi - Thorie des langages S4 2011 7
Si grande taille : (1) donner le vocabulaire , (2)impossible de donner lensemble des chanes
formalisme ou systme de rcriture :expressions rgulires, grammaires
8/6/2019 Thorie des langages 2010-2011
8/81
Expression de langage ?Comment reconnatre quune chane appartient au langage ?
Comment distinguer entre les chanes du langage et lesautres chanes du vocabulaire V ?
EMI D. Chiadmi - Thorie des langages S4 2011 8
Construction dun algorithme de
reconnaissance du langage
8/6/2019 Thorie des langages 2010-2011
9/81
Est une ER dcrivant le langage // V : vocabulaire
Est une ER dcrivant le langage {}
Tout a V est une ER dcrivant le langage {a}
Soit r et s 2 ER dcrivant le langage R et Salors
- r + s est une ER dcrivant le langage R S
3. Expressions rgulires
EMI D. Chiadmi - Thorie des langages S4 2011 99
- r.s est une ER dcrivant le langage RS
- r* est une ER dcrivant le langage R*= Rn n0
Ex: (A+B++Z+a+b++z).(A+B++Z+a+b++z+0+1++9)*
le langage dfini par cette ER (valeur de lexpression rgulire) est le
langage des identificateurs C
8/6/2019 Thorie des langages 2010-2011
10/81
Chapitre II.
Systmes de rcriture: grammaires
Systmes de rcriture
GrammairesLangages engendrs par une grammaire
EMI D. Chiadmi - Thorie des langages S4 2011 1010
Ambiguit
8/6/2019 Thorie des langages 2010-2011
11/81
1. Dfinition:
S = o S est le systme de rcriture , V est un
vocabulaire et R un ensemble fini de couples de chanes sur V
(, ) R est une rgle de rcriture note :
A- Systme de rcriture : Formalisation
EMI D. Chiadmi - Thorie des langages S4 2011 1111
Les rgles
1
2
k
partie gauche partie droite
1 | 2 || k
8/6/2019 Thorie des langages 2010-2011
12/81
2. Relations
Dfinition: Relation sur E = toute partie de E E
Pour x, y E
est vraie pour (x, y) SSI (x,y) ou x y
Ex: est la relation partout fausse sur E
E E est la relation partout vraie sur E
est la relation unit ou identit sur E = {(x , x) / x E } ( = )
EMI D. Chiadmi - Thorie des langages S4 2011 12
Une relation est rflexive si xE xxet transitive si x,y,z E (xy et yz) xz
Alors : relation de prordre
est symtrique si x,y E xy yxUne relation de prordre symtrique relation dquivalence
antisymtrique relation dordre partiel
8/6/2019 Thorie des langages 2010-2011
13/81
Les relations tant des parties de E E : oprations ensemblistes
Soient et relations sur E : complmentaire
: runion
: intersection
Oprations sur les relations:
EMI D. Chiadmi - Thorie des langages S4 2011 13
(x,y) SSI xy ou xy
(x,y) SSI xy et xy
x y SSI (x,y) ( non xy)
SSI cd x,y E xy xy
8/6/2019 Thorie des langages 2010-2011
14/81
3. Classes de dfinitions (description)
Existence de plusieurs classes de dfinitions quipeuvent tre traduites en un algorithme de
reconnaissance
Les dfinitions sont fondes sur des s stmes de
EMI D. Chiadmi - Thorie des langages S4 2011 1414
rcriture :1. Automates et machines
2. Grammaires : engendrer toutes les chanes dulangage partir dune chane donne axiome de la
grammaire
8/6/2019 Thorie des langages 2010-2011
15/81
B- Grammaire par lexemple une phrase est compose dun sujet suivi dun verbe suivi duncomplment
Exemple : Ltudiant suit un cours
sujet verbe complment
EMI D. Chiadmi - Thorie des langages S4 2011 15
Ensuite il faut expliquer ce quest un sujet , un verbe, un complment
Rgle 2 : sujet = article adjectif nom | article nom adjectif |article nom
Rgle 3 : article = le | la | un | des | l
Rgle 4 : adjectif = malin | stupide | couleur Rgle 5 : couleur = vert | rouge | jaune
Etc.
15
8/6/2019 Thorie des langages 2010-2011
16/81
1. Grammaires formelles (invent par Noam Chomsky)
DfinitionG = < VT , VN , S , R > o
VT Vocabulaire terminal
VN Vocabulaire non terminal Avec V= VT VN vocabulaire de la grammaire
S VN : axiome de la grammaire
disjoints
EMI D. Chiadmi - Thorie des langages S4 2011 1616
R = rgles de la grammaire // Rgle de production
Le systme de rcriture est dfini par < V, R >
Non terminaux Terminaux Chane de T et NT
MAJUSCULE Minuscule Lettre grecque
Convention
8/6/2019 Thorie des langages 2010-2011
17/81
Exemple 1
G = ( VT, VN, S, P) avec VT = { il elle parle est devient court reste sympa vite}
VN= {PHRASE PRONOM VERBE COMPLEMENT
VERBETAT VERBACTION } S = PHRASE
P = {
EMI D. Chiadmi - Thorie des langages S4 2011 17
PRONOM il | elle
VERBE VERBETAT | VERBACTION
VERBETAT est | devient | reste
VERBACTION parle | court COMPLEMENT sympa | vite }
17
8/6/2019 Thorie des langages 2010-2011
18/81
Exemple 2
Un exemple est fourni par G1 (syntaxe possible) :
E E + T | E - T | TT T * F | T / F | F
F num | id
E, T, F : non terminaux (VN) dfinis par des rgles de productions
EMI D. Chiadmi - Thorie des langages S4 2011 1818
_
+, -, *, /, num,id : terminaux (VT)
E : symbole de dpart (axiome) de la grammaire.
R : Rgles
Pb : Trouver les phrases de L(G1) : Drivation
8/6/2019 Thorie des langages 2010-2011
19/81
2. Relations de drivation dans un systme de rcriture
Soient S = et x, y V* ;on note une relation sur V* V* V* tels que
xS y ou xR y x se rcrit direct en y
ssi ( ) R / x = uv et y = uv
xR y plusieurs rgles de R permettent de rcrire x en yn
EMI D. Chiadmi - Thorie des langages S4 2011 1919
Remarques
1. x0
y ssi x = y2. La donne dune drivation ne permet pas toujours de retrouver lesrgles de rcriture appliques. // rgles de production
x* y en appliquant un nb qq de rgles vent. nulx+ y en appliquant un nb non nul de rgles
8/6/2019 Thorie des langages 2010-2011
20/81
Grammaires : reconnaissance
2. Langage engendr par une grammaire = L(G)
Ensemble des chanes sur VT que lon peut driver de
laxiome S= {x VT* / S *R x}
EMI D. Chiadmi - Thorie des langages S4 2011 2020
G1 G2 si L(G1) = L(G2)
L(G1) ??
8/6/2019 Thorie des langages 2010-2011
21/81
Langage engendr par une grammaire
L(G) est lensemble des chanes sur VT que lon peut driver delaxiome S
= {x VT* / S *R x} E/ \
EMI D. Chiadmi - Thorie des langages S4 2011 2121
G1 G2 si L(G1) = L(G2)
L(G1) ??
| / \T T F| | |F F| |id + num* id
8/6/2019 Thorie des langages 2010-2011
22/81
3. Classes de grammaires
Une grammaire est de type 3 si elle est soit linaire
gauche, soit linaire droite.
Grammaire linaire droite si*
- Grammaires de type 3 (rgulire) :
Exemple1:
S aS | T | abU |cc
EMI D. Chiadmi - Thorie des langages S4 2011 2222
,
A a avec A VN et a VT*
Grammaire linaire gauche si
A Ba avec A,B VN et a VT*
A a avec A VN et a VT*
T cT | U abS
Exemple 2S aS |bS | quivalent (a|b)*
8/6/2019 Thorie des langages 2010-2011
23/81
Classes de grammaires (suite)
Grammaires de type 2 // hors contexteA avec AVN et V*
Langage de Dick : S ( S ) S |
Grammaire de type 1 // sous-contexte
A
Les grammaires hors contexte sontutilises pour dfinir la syntaxede la plupart des langages deprogrammation
EMI D. Chiadmi - Thorie des langages S4 2011 2323
o , V*
, AVN et V+
Langage de correspondance entre paramtres formels et
effectifs L = {an bm cn dm, n 1, m 1}Rqs :
A est une - rgleA B avec B VN est une 1-rgle
8/6/2019 Thorie des langages 2010-2011
24/81
Remarques Type 1 : SC
Type 2 : HC
Type 3 : Rgulier
restrictif
-
EMI D. Chiadmi - Thorie des langages S4 2011 2424
Proprit : Les grammaires de type 1 englobent les
grammaires de type 2 qui englobent les grammaires detype 3.
+
8/6/2019 Thorie des langages 2010-2011
25/81
Problmes dcidables et indcidables
Un pb est dit
dcidable pour G sil un alg qui calcule la rponse (oui
ou non) au un pb pos
indcidable dans le cas contraire.
EMI D. Chiadmi - Thorie des langages S4 2011 2525
. Exemple de problme de dcidabilitL(G) est-il vide?L(G) est-il infini?
L(G) = VT* ?
L(G) = langage rgulier ?
Un mot ou L(G) ? rcursivit
Equivalence L(G1) = L(G2) ?
8/6/2019 Thorie des langages 2010-2011
26/81
4. Choix dun formalisme pour dfinir un langage
de programmation
Formalisme ou type de grammaire selon les critres suivants:
1. Doit tre suffisamment puissant pour contenir unedfinition du langage
EMI D. Chiadmi - Thorie des langages S4 2011 2626
2. Suffisamment simple pour que chaque dfinition puissetre compile en un algorithme efficace dereconnaissance des programmes du langage dfini
3. Doit contenir une dfinition du langage concise et facile comprendre
8/6/2019 Thorie des langages 2010-2011
27/81
Formalisme (suite)
Critre 1exclut les grammaires rgulires
Parenthses grande profondeur Structures de blocs
EMI D. Chiadmi - Thorie des langages S4 2011 2727
Mais peut tre utilise pour la lexicographie deslangages de programmation (identificateurs,
constantes)
8/6/2019 Thorie des langages 2010-2011
28/81
Critre 2 exclut les grammaires gnrales qui
engendrent des langages non rcursifs
// un langage est dit rcursif si x chane de V, algorithme qui dcide oui ou non x langage
Formalisme (suite)
EMI D. Chiadmi - Thorie des langages S4 2011 2828
La plupart des langages de programmation sont dfinis
par des grammaires hors contexte
8/6/2019 Thorie des langages 2010-2011
29/81
4. Arbres de drivation (AD)
Un AD pour une squencex VT* selon G est un arbre dedrivations
- La racine : tiquete par l'axiome,- Les feuilles : tiquetes par les T ou
E/ \
E T| / \T T F
EMI D. Chiadmi - Thorie des langages S4 2011 2929
-
- kfils tiquets de ghe dte par
N1,N2,...,Nk si A N1N2...NkP
2- un fils tiquet par si A P
- x : concatnation des tiquettes des feuilles gauche droite
| | |F F| |id + num* id
8/6/2019 Thorie des langages 2010-2011
30/81
Arbres de drivation : exemple
Soit la grammaire suivante avec comme axiome :V = {a,b} R = { ab , ab}
a b a b
EMI D. Chiadmi - Thorie des langages S4 2011 3030
L(G) = {an bn/ n N*}
Pour tout w V*
w L(G) n N*
/ w = an
bn
a b
G0 = ( VN VT E P); VN = {E} ;
8/6/2019 Thorie des langages 2010-2011
31/81
5. Ambigut
Une grammaire hors contexteG =< VT , VN , S , R > est dite ambigu sil existe unechane terminale admettant au moins deux arbres de
drivation de racine S
G0 = ( VN, VT, E , P); VN = {E} ;
VT = {+,,(,),id, num}
P = { E E + E | E E | (E) | id | num }
EMI D. Chiadmi - Thorie des langages S4 2011 3131
E/ \E E| / \
| E E| | |id + num* id
E \E E
/ \
E E| |id + num * id
Pb :lAD influe sur lasmantique choix unique
8/6/2019 Thorie des langages 2010-2011
32/81
Ambigut
un langage hors contexte est ambigu si toutes lesgrammaires hors contexte qui lengendrent sont
EMI D. Chiadmi - Thorie des langages S4 2011 3232
ambigus
8/6/2019 Thorie des langages 2010-2011
33/81
limination des ambiguts par rcriture de G
1- en imposant des dlimiteurs2-en sparant un non terminal E en deux
Solution1 : dlimiteur (par un terminal) Ex1 :
EMI D. Chiadmi - Thorie des langages S4 2011 33
I Si Ealors I | Si Ealors Isinon I | autre I Si Ealors Ifinsi| Si Ealors Isinon Ifinsi| autre
Ex2 : E E+E|E-E |E*E| (E) | id | num
E (E+E)|( E-E) |(E*E)| (E) | id | num
33
8/6/2019 Thorie des langages 2010-2011
34/81
limination des ambiguts par rcriture de G
solution2 :- Sparer I en 2 NT I-close et I-nclose : I entre
alors et sinon doit toujours tre closeI IC | InC //I-close | I-ncloseIC si E alors IC sinon InC | autre
EMI D. Chiadmi - Thorie des langages S4 2011 34
InC si E alors I |si E alors IC sinon InC
- Sparer les niveaux de priorits- E E + T | E - T | T- T T * E | F
- F (E) | num | id
34
8/6/2019 Thorie des langages 2010-2011
35/81
Chapitre III. Automates finisI. Dfinition:
Cest un quintuplet (Q, V, , I, F) o
Q ensemble fini dtats
EMI D. Chiadmi - Thorie des langages S4 2011 35
sous ensemble de Q x V{}x Q = ens de transitions
I Q sous ensemble d tats initiaux
F Q sous ensemble d tats finaux (finals)
35
8/6/2019 Thorie des langages 2010-2011
36/81
transition
(p,a,q) transition o p,q Q
et a V = a-transition
: ori ine a
EMI D. Chiadmi - Thorie des langages S4 2011 3636
Q : extrmit p q
8/6/2019 Thorie des langages 2010-2011
37/81
Quelques dfinitions
Tout automate peut tre dessin comme suit:
p q
Signifie que (p,a,q) a
Si nifie ue a et b a,b
EMI D. Chiadmi - Thorie des langages S4 2011 3737
p q
p Marque un tat initial
p Marque un tat finalou p
8/6/2019 Thorie des langages 2010-2011
38/81
Entre : ER rsur V
Sortie : AFND
Mthode: Dcomposer ren sous expressions
1- r q fr
EMI D. Chiadmi - Thorie des langages S4 2011 38
-
3- rs
4- r*
q frs
q q1 f
r
sr
8/6/2019 Thorie des langages 2010-2011
39/81
Exemple
Soit 1 AFND reconnaissant des nombresrels xx..xExx ou xxx.xxx
={0 , . . . , 9 , . ,E}ch ch
EMI D. Chiadmi - Thorie des langages S4 2011 39
.
ch
ch
ch
ch
ch
ch
E
.
8/6/2019 Thorie des langages 2010-2011
40/81
Quelques dfinitions (suite)
Chemin
Un chemin de A de longueur n = suite detransitions de / (ri , ai+1 , r i+1) pour 0 i n
a1 an = trace du cheminr0 rn
a1 an
EMI D. Chiadmi - Thorie des langages S4 2011 4040
Par convention, un chemin de longueur 0 est
la transition (p,,p) p
8/6/2019 Thorie des langages 2010-2011
41/81
Mot : un mot x est reconnu par un automate sil existe une
trace x menant dun tat initial un tat final
Quelques dfinitions (suite)
EMI D. Chiadmi - Thorie des langages S4 2011 4141
Un langage reconnu par un automate fini devocabulaire V est appel langage dtats fini sur V
Langage : Soit A un automate,L(A) ={ des mots reconnus par lautomate A }L(A) = le langage reconnu par A
P it
8/6/2019 Thorie des langages 2010-2011
42/81
Proprits
1. 2 automates A et B sont quivalents sils ont le mmevocabulaire et reconnaissent le mme langage.
2. Soient A = (Q, V, , I, F) un automate fini ; x, y V*,
p, q deux tats de A et a V- Un chemin mne de p q avec la trace xy un tat r
EMI D. Chiadmi - Thorie des langages S4 2011 4242
p r r qet
- aes tunchemindepq r, s Q /
p q
a
chemin
p r
a
s q
chemin chemintransition
8/6/2019 Thorie des langages 2010-2011
43/81
Automates dterministes
Un AFD est un cas particulier d'un AFND o : Il y a un unique tat initial Aucun tat n'a de -transition (q,a), qQ & aV, au + un tat successeur
On note (p,a) lunique tat q / (p,a,q)
EMI D. Chiadmi - Thorie des langages S4 2011 4343
Exemple
pair impair
0 1
1
0tat initial
= tat final
Proprits
8/6/2019 Thorie des langages 2010-2011
44/81
Proprits
Soit A= (Q,V, ,q0, F) automate fini dterministe1. Pour tout tat p et toute chane x,
x
(p,x) = q un chemin p qtrace2. L(A) = {x V*/(q0, x) F}
EMI D. Chiadmi - Thorie des langages S4 2011 4444
3. Pour tout tat p et toutes chanes x,y (p,xy) = ( (p,x) ,y)
Preuve: par rcurrence sur la lg de y
Proprits (suite)
8/6/2019 Thorie des langages 2010-2011
45/81
Dfinition 2- p est accessible pour A i l y a u n e c h a n e x s u r V | p = (q0,x)
-un automate dterministe est dit initialement connect si tous
ses tats sont accessibles
4. Soit R lensemble des tats accessibles de A
Proprits (suite)
EMI D. Chiadmi - Thorie des langages S4 2011 4545
B = (R,V, , q0, RF) est lautomate obtenu en supprimantles tats inaccessibles. = (R x V x R)
Automate dterministe A et B initialementconnect
A t t dt i i t t ti
8/6/2019 Thorie des langages 2010-2011
46/81
Automate dterministe: construction
Thorme 2
Un langage reconnu par un AFND est aussireconnu par un AFD
EMI D. Chiadmi - Thorie des langages S4 2011 4646
Pb : ?AFND AFD
AFD Construction (suite)
8/6/2019 Thorie des langages 2010-2011
47/81
AFD Construction (suite)
Soit A = (Q, V, , q0, F) AFND,
Dfinition1 : { -succs} de
EMI D. Chiadmi - Thorie des langages S4 2011 47
q Q : -succs(q) = { p | (q,,p) } S Q : -succs(S) = qS -succs(q)
AFD Construction (suite)
8/6/2019 Thorie des langages 2010-2011
48/81
AFD Construction (suite)
Dfinition2 : LAFD B=(Q', V, , q0 ,F'), quivalent
A, est dfini par : Q' P(Q) , l'ensemble des parties de Q
EMI D. Chiadmi - Thorie des langages S4 2011 48
q = - ermeture q
F' = {S Q| S F }
(S,a) = - fermeture {p |(q,a,p) , qS} , a V
Exple : dun AFND un AFD
8/6/2019 Thorie des langages 2010-2011
49/81
Exple : d un AFND un AFD
1. Partir de -succs de ltat initial2. Rajouter dans la relation de transition toutes lesfermetures des nouveaux tats produits avec leurstransitions
3. Recommencer jusqu ce quil ny ait plus de nouvel tat4. Tous les tats contenant au moins un tat terminal
deviennent terminaux
EMI D. Chiadmi - Thorie des langages S4 2011 49
tat a b c
0 2 - 0 1
1 3 4 - -
2 - - 1,4 0
3 - 1 - -
4 - - 3 2
5. Renumroter alors les tats
Exple : dun AFND un AFD
8/6/2019 Thorie des langages 2010-2011
50/81
tat a b c 0 2 - 0 1
1 3 4 - -
2 - - 1,4 0
3 - 1 - -
4 - - 3 2
tat a b c0,1 2,3,0 2,4 0,1
2,3,0 2,0 1 1,4,2
2,4 - - 1,4,3,2
2,0 2,0 - 1,4,0
1 3 4,2 -
1,4,2 3 4 1,3,4,2
tat a b c
0 1 2 0
1 3 4 5
2 - - 63 3 - 7
4 8 2 -
EMI D. Chiadmi - Thorie des langages S4 2011 50
1,4,3,2 3 1,4,2 1,3,4,2
1,4,0 2,3,0 4,2 3,0,1
3 - 1 -
4 - - 3
3,0,1 2,3,0 1,4,2 0,1
-fermeture(0) = {0,1}
g({0,1},a) = -ferm{2,3}= {2,3,0}
g({0,1},b) = -ferm {4} = {2,4}
g({0,1},c) = -ferm {0} = {0,1}
g({2,3,0},a) = -ferm{2} = {2,0}g({2,3,0},b) = -ferm{1}= {1}
g({2,3},c) = -ferm{1,4}= {1,4,2} Etc.
5 8 9 6
6 8 5 6
7 1 2 10
8 - 4 -
9 - - 8
10 1 5 0
Algorithme : De lAFND lAFD
8/6/2019 Thorie des langages 2010-2011
51/81
Algorithme : De l AFND l AFD
q'0 := -fermeture(q0) ; Q' := {q'0} ; marque(q'0) := faux ; := ;Tantque ( S Q') & ( non marque (S)) faire
marque(S) := vrai ;pour tout a V faire
T := -fermeture({pQ | (q,a,p) & q S});si T Q' alors
EMI D. Chiadmi - Thorie des langages S4 2011 51
:= ; nouve tat
marque(T) := faux ;fsi
:= {(S,a) T} /*nouv. trans.*/
fpourftqfin.
8/6/2019 Thorie des langages 2010-2011
52/81
ExercicesDonnez un automate fini dterministe
reconnaissant chacun des langagessuivants :
EMI D. Chiadmi - Thorie des langages S4 2011 52
.
conscutifs sur lalphabet {a,..,z}2. ((a+b) a)* sur le vocabulaire {a,b}
3. (0+1)*0 sur le vocabulaire {0,1}
8/6/2019 Thorie des langages 2010-2011
53/81
Exercices (suite)
Donner intuitivement une expression rgulirepour chacun des langages suivants:
L1= lensemble des mots sur lal habet a, b, c
EMI D. Chiadmi - Thorie des langages S4 2011 53
telle que jamais de b avant la premireoccurrence de a }. Un mot sans a ou un motsans b fait partie de L1.
L2= {lensemble des mots sur lalphabet ASCIcommenant par /* et se terminant par */, et sans*/ entre les deux}
8/6/2019 Thorie des langages 2010-2011
54/81
Exercices (suite)Le systme dimmatriculation marocain est compos
de 3 champs conscutifs :Compteur Srie rgion
Ex : 125 25
EMI D. Chiadmi - Thorie des langages S4 2011 54
vec
- Compteur entre 1 et 999999- Srie { , , }- Rgion entre 1 et 76
Ecrire un automate qui dcrit un tel langage.
8/6/2019 Thorie des langages 2010-2011
55/81
Exercice (grammaire)Soit la grammaire des expressions arithmtiques avec + et * :G = (Vt, Vn, R, Exp), telle que :
Vt = {(, ), +, *, num}Vn = {Exp}R = {Exp num
Exp ( Exp )
EMI D. Chiadmi - Thorie des langages S4 2011 55
xp xp + xp
Exp Exp * Exp}
1. Donner quelques mots gnrs par G2. Donner un arbre de drivation pour la chane num + num * num Larbre est-il unique? Que peut on dire de G et du langage engendr par G?
Justifier.1. En gnral, on peut avoir plusieurs grammaires gnrant le mme langage.2. Proposer une grammaire quivalente G
Chapitre IV Automates minimaux
8/6/2019 Thorie des langages 2010-2011
56/81
Chapitre IV.Automates minimaux
Dfinition : Un automate dterministe A est minimal si toutautomate dterministe quivalent A comporte au moins
autant dtats que A
Soit A= (Q, V, ,q , F) automate fini dterministe
EMI D. Chiadmi - Thorie des langages S4 2011 5656
Deux tats p,q de A sont quivalents:p A q si x V* : (p, x) F (q, x) F
x V* p q (p,x) (q,x)
8/6/2019 Thorie des langages 2010-2011
57/81
Soit (A)= (R, V, , [q0], G) O
R: ens des classes dquivalence de la relation G: ens des classes dquivalence des tats de F
EMI D. Chiadmi - Thorie des langages S4 2011 5757
[a] : classe d de a pour la relation
([p],a) = [(p,a)] pour aV , pQ
Proposition
8/6/2019 Thorie des langages 2010-2011
58/81
Si A automate dterministe initialement connect, alors (A) estun automate dterministe A, initialement connect et tousses tats sont 22 non quivalents.
xV* ,pQ : ([p],x) = [(p,x)] p F [p] G
EMI D. Chiadmi - Thorie des langages S4 2011 5858
=
(A) est initialement connect
Corollaire
Si A automate dterministe minimal alors A est initialement
connect et ses tats sont 22 non quivalentsProprit caractristique des automates minimaux
Thorme 1
8/6/2019 Thorie des langages 2010-2011
59/81
A.D.M. A.I.C. et tous ses tats sont 22 non tsThorme 2:Existence dun automate minimal un automate donnSi A automate dterministe et
B lautomate obtenu sans les tats inaccessibles de A
EMI D. Chiadmi - Thorie des langages S4 2011 5959
ors es m n ma e
Thorme 3:Si 2 automates dterministes sont ts et minimaux alors ils sont
isomorphes Unicit de lautomate minimal
Construction dun automate minimal quivalent
8/6/2019 Thorie des langages 2010-2011
60/81
q
un automate donn (1)
Soit A= (Q,V, ,q0,F)
1. Enlever les tats inaccessibles de A B = (R, V, , q0, G)
EMI D. Chiadmi - Thorie des langages S4 2011 6060
2. Calculer la congruence pour B : p,qQ
p q ssi xV* (p,x) G (q,x) G
3. Construire lautomate
(B)= (S, V, , [q0], H)
Construction dun automate minimal quivalent
8/6/2019 Thorie des langages 2010-2011
61/81
O
S ens des classes de la relation
H ens des classes des tats de G
q
un automate donn (2)
EMI D. Chiadmi - Thorie des langages S4 2011 6161
([p],a) = [(p,a)] aV , pR
k (o k 0) relation sur R :
p k q xV* / |x| k
(p,x) G (q,x) G
Nous avons les proprits suivantes (3)
8/6/2019 Thorie des langages 2010-2011
62/81
1. k 0 k est une relation dquivalence
2. = k
k03. k 0 k+1 k4. p 0 q ssi p G q G
EMI D. Chiadmi - Thorie des langages S4 2011 6262
5. k 0 p k+1 q ssip k q et aV / (p,a) k (q,a)
6. Si n est le nb dtats de lautomate B alors
kn / k = k+1 =
8/6/2019 Thorie des langages 2010-2011
63/81
Rgle gnrale (4)
Pour construire la relation :
On calcule partir de lindice 0 la suite desrelations k ((4) et (5)) jusquau premier indice
EMI D. Chiadmi - Thorie des langages S4 2011 6363
mtelque:m = m+1 qui est donc
exemple
e
Pour tout e V
8/6/2019 Thorie des langages 2010-2011
64/81
1 2
e
1 2r
2
1 2r
1 s1
3
2
EMI D. Chiadmi - Thorie des langages S4 2011 64
1 2 21
1 2r
11
Tout langage dtats fini sur V est un langage rgulier sur V
8/6/2019 Thorie des langages 2010-2011
65/81
Dfinition : systme dquation associ un automate fini A = (Q,V, , I, F) automate fini q1, . . , qn liste sans rptition des tats de A
i,j= { a V{} / ( q
i, a , q
j) 1 i,j n }
x1, . . , xn : n variables non lments de VLe systme dquations sur V pour 1 i n
EMI D. Chiadmi - Thorie des langages S4 2011 6565
nxi = + i,j xj si qi Fj=1
nxi = i,j xj si qi Fj=1
Ce systme a pour plus petite solution :
8/6/2019 Thorie des langages 2010-2011
66/81
x1= L(A1) , . . , xn= L(An)pour 1 i n Ai = (Q,V, , qi, F)
Thorme
Si , deux langages sur V et x V alors:x = .x + admet comme plus petite solution x=*
EMI D. Chiadmi - Thorie des langages S4 2011 6666
x: s x=
Un langage dtats fini sur V SSI un langage rgulier sur V
L = L(A) = L(Ai) = langages rguliers = rgulieriI iIExemple:
Chapitre VI
Dfi iti d l
8/6/2019 Thorie des langages 2010-2011
67/81
Dfinition des langages par rcurrence
Rappels
G = < VT , VN , S , R >grammaire = ens de rgles de production o
VT Vocabulaire terminal VN Vocabulaire non terminal
EMI D. Chiadmi - Thorie des langages S4 20116767
= T N
S VN : axiome de la grammaire R : rgles de la grammaire
But : tant donne une grammaire G, dfinir par rcurrence lelangage L(G) engendr par G et rciproquement.
Exemples
S it G l i i t
8/6/2019 Thorie des langages 2010-2011
68/81
Soit G la grammaire suivante:VT= {a,b} VN= {s, x, y}R={s ay, y bs, y ayy, y b,
s bx, x as, x bxx, x a }
Pb: recherche du langage engendr par cette grammaire L(G)
EMI D. Chiadmi - Thorie des langages S4 20116868
,
Par rcurrence:ab, ba, aabb, abab, abba, baba, baab,On peut montrer:
S w ssi |w|a= |w|
by w ssi |w|b= |w|a +1x w ssi |w|a= |w|b +1
**
*
Rciproquement: tant donn un langage, on chercheune grammaire qui lengendre
8/6/2019 Thorie des langages 2010-2011
69/81
une grammaire qui l engendre
Exemple 1:
Soit L= {w {a,b}*/ bb non facteur de W }
On construit lautomate correspondant :
EMI D. Chiadmi - Thorie des langages S4 20116969
S X
ab
a
S aSS bXX aSS 1X 1
R=
Exemple2 :
8/6/2019 Thorie des langages 2010-2011
70/81
Soit L= {w {a,b}* / |w|a= 2|w|b }O n a :
aab a2nbn
baa bn
a2n
aba w1ww2 avec w1w2 L
EMI D. Chiadmi - Thorie des langages S4 20117070
SoitS SaSaSbSS SaSbSaSS SbSaSaSS 1
R=
Chapitre V
Langages dtats finis et langages rguliers
8/6/2019 Thorie des langages 2010-2011
71/81
Langages d tats finis et langages rguliers
Tout langage rgulier sur V est un langage dtats finis sur V
Dfinition 1 e : expression rgulire sur V e = lan a e sur V = valeur de e
EMI D. Chiadmi - Thorie des langages S4 201171
V(e) = nb doccurrences de signes dans e
Dfinition 2Un automate fini est simple sil nadmet quun tat initial et
quun tat final et aucune transition na comme extrmit ltatinitial ni comme origine ltat final
Proprit 1
8/6/2019 Thorie des langages 2010-2011
72/81
Si e expression rgulire sur V alors il 2 et un automatesimple A= ({1..}, V, , {1}, {}) qui reconnat lelangage (e)
Preuve
EMI D. Chiadmi - Thorie des langages S4 201172
e =
e = ou e V{}
1 2e
1 2
Preuve (suite)
8/6/2019 Thorie des langages 2010-2011
73/81
V(e)= x e = f* ou e = f + g ou e = f . g
avec f, g expressions rgulires sur V et V(f), V(g)x
Si e = f * C = ({1..+1}, V, , {1}, {+1})
EMI D. Chiadmi - Thorie des langages S4 201173
reconna t e et =
Si e = f + g L(A) L(B) = L(C)o C = ({1..+-2}, V, , {1}, {+-2})
Si e = f . g L(A) . L(B) = L(C)
o C = ({1..+-1}, V, , {1}, {+-1})
e
Pour tout e V
8/6/2019 Thorie des langages 2010-2011
74/81
1 2
1 2r
2
1 2r
1 s1
3
2
EMI D. Chiadmi - Thorie des langages S4 201174
1 2 21
111 2r
Exemple si e = f*
8/6/2019 Thorie des langages 2010-2011
75/81
Le langage 010 est reconnu par lautomate simple:
p r
1
s q0 0
*
EMI D. Chiadmi - Thorie des langages S4 201175
1
p
r s
q
0 0
p0
Si e = f + g L(A) L(B) = L(C)
8/6/2019 Thorie des langages 2010-2011
76/81
Exemple:Le langage 0* est reconnu par lautomate simple :
01 1
q r
0
p
Le langage 101 est reconnu par lautomate simple :
EMI D. Chiadmi - Thorie des langages S4 201176
p q
q
0
p
r
0s
t
1 1
Le langage 0* + 101 est reconnu par lautomate simple:
Si e = f . g L(A) . L(B) = L(C)
8/6/2019 Thorie des langages 2010-2011
77/81
Si e f . g L(A) . L(B) L(C)Exemple:Le langage (0+1)* est reconnu par lautomate simple
q r
0,1
p
Le langage 00 est reconnu par lautomate simple
EMI D. Chiadmi - Thorie des langages S4 201177
p q r
Le langage (0+1)*00 est reconnu par lautomate simple
q r
0,1
p s0 t0
Tout langage dtats fini sur V est un langage rgulier sur V
8/6/2019 Thorie des langages 2010-2011
78/81
Dfinition : systme dquation associ un automate fini A = (Q,V, , I, F) automate fini q1, . . , qn liste sans rptition des tats de A i,j = { a V{} / ( qi, a , qj ) 1 i,j n } x1, . . , xn : n variables non lments de VLe systme dquations sur V pour 1 i n
EMI D. Chiadmi - Thorie des langages S4 2011 78
n
xi = + i,j xj si qi Fj=1
n
xi = i,j xj si qi Fj=1
Ce systme a pour plus petite solution :
8/6/2019 Thorie des langages 2010-2011
79/81
x1= L(A1) , . . , xn= L(An)pour 1 i n Ai = (Q,V, , qi, F)
Thorme :
Si , deux langages sur V et x V alors:x = .x + admet comme plus petite solution x=*
EMI D. Chiadmi - Thorie des langages S4 2011 79
x: s x=
Un langage dtats fini sur V SSI un langage rgulier sur V
L = L(A) = L(Ai
) = langages rguliers = rgulieriI iI
Exemple: trait en cours
8/6/2019 Thorie des langages 2010-2011
80/81
Exemple: Soit lautomate A
EMI D. Chiadmi - Thorie des langages S4 2011 80
Solution du systme dquations: Langage reconnupar lautomate A
8/6/2019 Thorie des langages 2010-2011
81/81
Notation: | = +
EMI D. Chiadmi - Thorie des langages S4 2011 81