Théorie des langages 2010-2011

8/6/2019 Thorie des langages 2010-2011

1/81

Thorie des langages. .

Mis jour par D. Chiadmi

Ecole Mohammadia dIngnieurs

Fvrier 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


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


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


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 =


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


.

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


6/81


7/81

Expression de langage ? Comment exprimer un langage ?

Si petite taille : donner le vocabulaire et leschanes le constituant


Si grande taille : (1) donner le vocabulaire , (2)impossible de donner lensemble des chanes

formalisme ou systme de rcriture :expressions rgulires, grammaires


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 ?


Construction dun algorithme de

reconnaissance du langage


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


- 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


10/81

Chapitre II.

Systmes de rcriture: grammaires

Systmes de rcriture

GrammairesLangages engendrs par une grammaire


Ambiguit


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


Les rgles

1

2

k

partie gauche partie droite

1 | 2 || k


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 } ( = )


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


13/81

Les relations tant des parties de E E : oprations ensemblistes

Soient et relations sur E : complmentaire

: runion

: intersection

Oprations sur les relations:


(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


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


rcriture :1. Automates et machines

2. Grammaires : engendrer toutes les chanes dulangage partir dune chane donne axiome de la

grammaire


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


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


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 = {


PRONOM il | elle

VERBE VERBETAT | VERBACTION

VERBETAT est | devient | reste

VERBACTION parle | court COMPLEMENT sympa | vite }

17


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


_

+, -, *, /, num,id : terminaux (VT)

E : symbole de dpart (axiome) de la grammaire.

R : Rgles

Pb : Trouver les phrases de L(G1) : Drivation


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


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


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}


G1 G2 si L(G1) = L(G2)

L(G1) ??


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/ \


G1 G2 si L(G1) = L(G2)

L(G1) ??

| / \T T F| | |F F| |id + num* id


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


,

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)*


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


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


24/81

Remarques Type 1 : SC

Type 2 : HC

Type 3 : Rgulier

restrictif

-


Proprit : Les grammaires de type 1 englobent les

grammaires de type 2 qui englobent les grammaires detype 3.

+


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.


. 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) ?


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


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


27/81

Formalisme (suite)

Critre 1exclut les grammaires rgulires

Parenthses grande profondeur Structures de blocs


Mais peut tre utilise pour la lexicographie deslangages de programmation (identificateurs,

constantes)


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)


La plupart des langages de programmation sont dfinis

par des grammaires hors contexte


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


-

- 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


30/81

Arbres de drivation : exemple

Soit la grammaire suivante avec comme axiome :V = {a,b} R = { ab , ab}

a b a b


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} ;


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 }


E/ \E E| / \

| E E| | |id + num* id

E \E E

/ \

E E| |id + num * id

Pb :lAD influe sur lasmantique choix unique


32/81

Ambigut

un langage hors contexte est ambigu si toutes lesgrammaires hors contexte qui lengendrent sont


ambigus


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 :


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


35/81

Chapitre III. Automates finisI. Dfinition:

Cest un quintuplet (Q, V, , I, F) o

Q ensemble fini dtats


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


36/81

transition

(p,a,q) transition o p,q Q

et a V = a-transition

: ori ine a


Q : extrmit p q


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


p q

p Marque un tat initial

p Marque un tat finalou p


38/81

Entre : ER rsur V

Sortie : AFND

Mthode: Dcomposer ren sous expressions

1- r q fr


-

3- rs

4- r*

q frs

q q1 f

r

sr


39/81

Exemple

Soit 1 AFND reconnaissant des nombresrels xx..xExx ou xxx.xxx

={0 , . . . , 9 , . ,E}ch ch


.

ch

ch

ch

ch

ch

ch

E

.


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


Par convention, un chemin de longueur 0 est

la transition (p,,p) p


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)


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


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


p r r qet

- aes tunchemindepq r, s Q /

p q

a

chemin

p r

a

s q

chemin chemintransition


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)


Exemple

pair impair

0 1

1

0tat initial

= tat final

Proprits


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}


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)


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)


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


46/81

Automate dterministe: construction

Thorme 2

Un langage reconnu par un AFND est aussireconnu par un AFD


Pb : ?AFND AFD

AFD Construction (suite)


47/81


Soit A = (Q, V, , q0, F) AFND,

Dfinition1 : { -succs} de


q Q : -succs(q) = { p | (q,,p) } S Q : -succs(S) = qS -succs(q)



48/81


Dfinition2 : LAFD B=(Q', V, , q0 ,F'), quivalent

A, est dfini par : Q' P(Q) , l'ensemble des parties de Q


q = - ermeture q

F' = {S Q| S F }

(S,a) = - fermeture {p |(q,a,p) , qS} , a V

Exple : dun AFND un AFD


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


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


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 -


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


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


:= ; nouve tat

marque(T) := faux ;fsi

:= {(S,a) T} /*nouv. trans.*/

fpourftqfin.


52/81

ExercicesDonnez un automate fini dterministe

reconnaissant chacun des langagessuivants :


.

conscutifs sur lalphabet {a,..,z}2. ((a+b) a)* sur le vocabulaire {a,b}

3. (0+1)*0 sur le vocabulaire {0,1}


53/81

Exercices (suite)

Donner intuitivement une expression rgulirepour chacun des langages suivants:

L1= lensemble des mots sur lal habet a, b, c


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}


54/81

Exercices (suite)Le systme dimmatriculation marocain est compos

de 3 champs conscutifs :Compteur Srie rgion

Ex : 125 25


vec

- Compteur entre 1 et 999999- Srie { , , }- Rgion entre 1 et 76

Ecrire un automate qui dcrit un tel langage.


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 )


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


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


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)


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


[a] : classe d de a pour la relation

([p],a) = [(p,a)] pour aV , pQ

Proposition


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


=

(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


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


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


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)


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


61/81

O

S ens des classes de la relation

H ens des classes des tats de G

q

un automate donn (2)


([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)


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


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 =


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


mtelque:m = m+1 qui est donc

exemple

e

Pour tout e V


64/81

1 2

e

1 2r

2

1 2r

1 s1

3

2


1 2 21

1 2r

11

Tout langage dtats fini sur V est un langage rgulier sur V


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


nxi = + i,j xj si qi Fj=1

nxi = i,j xj si qi Fj=1

Ce systme a pour plus petite solution :


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=*


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


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


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)


,

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


69/81

une grammaire qui l engendre

Exemple 1:

Soit L= {w {a,b}*/ bb non facteur de W }

On construit lautomate correspondant :


S X

ab

a

S aSS bXX aSS 1X 1

R=

Exemple2 :


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


SoitS SaSaSbSS SaSbSaSS SbSaSaSS 1

R=

Chapitre V

Langages dtats finis et langages rguliers


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


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


72/81

Si e expression rgulire sur V alors il 2 et un automatesimple A= ({1..}, V, , {1}, {}) qui reconnat lelangage (e)

Preuve


e =

e = ou e V{}

1 2e

1 2

Preuve (suite)


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})


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


74/81

1 2

1 2r

2

1 2r

1 s1

3

2


1 2 21

111 2r

Exemple si e = f*


75/81

Le langage 010 est reconnu par lautomate simple:

p r

1

s q0 0

*


1

p

r s

q

0 0

p0

Si e = f + g L(A) L(B) = L(C)


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 :


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)


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


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


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


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 :


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=*


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


80/81

Exemple: Soit lautomate A


Solution du systme dquations: Langage reconnupar lautomate A


81/81

Notation: | = +


Documents

Théorie des langages 2010-2011