limbaje 2

Limbaje Formale, Automate si Compilatoare

Curs 2

2014-15

LFAC (2014-15) Curs 2 1 / 26

Proprietati de nchidere pentru L3

Curs 2

1 Proprietati de nchidere pentru L3

2 Lema Bar-Hillel

3 Automate finite deterministe

4 Automate finite nedeterministe

LFAC (2014-15) Curs 2 2 / 26


Fie L, L1, L2 limbaje regulate: exista gramaticile G,G1,G2 de tip 3astfel ca L = L(G), L1 = L(G1) si L2 = L(G2).

Atunci, urmatoarele limbaje sunt de asemenea regulate:1 L1 L22 L1 L23 L

4 LR

5 L1 L26 L1 \ L2

LFAC (2014-15) Curs 2 3 / 26


Inchiderea la operatia de iteratie

Fie L limbaj de tip 3 (regulat).Fie G = (N,T ,S,P) de tip 3, n forma normala, care genereaza L(L = L(G)).Presupunem ca simbolul de start S nu apare in partea dreapta avreunei reguli.Gramatica G = (N,T ,S,P ) unde P consta din

reguli A aB din Preguli A aS, pentru orice regula A a din Pregula S

este de tip 3 si genereaza L

LFAC (2014-15) Curs 2 4 / 26


Inchiderea la intersectie

Fie L1, L2 limbaje de tip 3 (regulate).Fie G1 = (N1,T1,S1,P1) si G2 = (N2,T2,S2,P2) gramatici de tip 3, nforma normala, cu L1 = L(G1), L2 = L(G2).Gramatica G = (N1 N2,T1 T2, (S1,S2),P), unde P consta din:

(S1,S2) , daca S1 P1 si S2 P2

(A1,B1) a(A2,B2), daca A1 aA2 P1 si B1 aB2 P2

(A1,A2) a, daca A1 a P1 si A2 a P2

este de tip 3 si genereaza limbajul L1 L2

LFAC (2014-15) Curs 2 5 / 26


Inchiderea la operatia de oglindire

Fie L limbaj de tip 3 (regulat).Fie G = (N,T ,S,P) de tip 3, n forma normala, care genereaza L(L = L(G))Presupunem ca simbolul de start S nu apare in partea dreapta avreunei reguli.

Gramatica G = (N,T ,S,P ) unde P consta dinreguli S aA, pentru orice regula A a din Preguli B aA pentru orice regula A aB din Pregula S regula S a, pentru orice regula S a din P (a T {})

este de tip 3 si genereaza LRLFAC (2014-15) Curs 2 6 / 26

Lema Bar-Hillel

Curs 2


2 Lema Bar-Hillel



LFAC (2014-15) Curs 2 7 / 26

Lema Bar-Hillel

Lema Bar-Hillel (lema de pompare)

Lema 2.1Fie L un limbaj de tip 3. Exista un numar m astfel ncat oricare ar ficuvantul w L cu |w | m, acesta are o descompunere de formaw = xyz, unde 0 < |y | m, si xy iz L oricare ar fi i 0.

Fie G = (N,T ,S,P) astfel ca L(G) = L. Daca |N| este numarul simbolurilor din N ,m = |N|+ 1, se arata ca are loc proprietatea enuntata:Fie w = a1a2 . . . an, n m n |N|+ 1S a1A1 a1a2A2 . . . a1a2 . . . ak Ak . . . a1a2 . . . ak ak+1 . . . asAs . . .a1a2 . . . ak ak+1 . . . asas+1 . . . an1An1 a1a2 . . . ak ak+1 . . . asas+1 . . . an1anAk = As

LFAC (2014-15) Curs 2 8 / 26

Lema Bar-Hillel

Demonstratie

w = a1a2 . . . an, n m

S a1A1 a1a2A2 . . . a1a2 . . . akAk . . .a1a2 . . . akak+1 . . . asAk . . . a1a2 . . . akak+1 . . . asas+1 . . . an1an

Atunci:

S a1a2 . . . akAkAk ak+1 . . . asAk si

Ak as+1 . . . an1anFie x = a1a2 . . . ak , y = ak+1 . . . as si z = as+1 . . . an1an

S xAk , Ak yAk si Ak z

LFAC (2014-15) Curs 2 9 / 26

Lema Bar-Hillel

Demonstratie

Fie x = a1a2 . . . ak , y = ak+1 . . . as si z = as+1 . . . an1an

S xAkAk yAk si

Ak z

Pentru i = 0, xz L(G): S xAk xzPentru i > 0, xy iz L(G):S xAk xyAk xyyAk . . . xyy . . . yAk

xyy . . . yz = xy iz

LFAC (2014-15) Curs 2 10 / 26

Automate finite deterministe

Curs 2


2 Lema Bar-Hillel



LFAC (2014-15) Curs 2 11 / 26


Automate finite

Mecanism de recunoastere (acceptare) pentru limbajeLimbaje de tip 3Multime finita de stari

LFAC (2014-15) Curs 2 12 / 26


Automate finite

Definitie 1Un automat finit determinist este un 5-uplu A = (Q,, , q0,F ), unde:

Q si sunt multimi finite, nevide, numite multimea starilorrespectiv alfabetul de intrare

q0 Q este starea initialaF Q este multimea starilor finale este o functie , : Q Q, numita functia de tranzitie

LFAC (2014-15) Curs 2 13 / 26


Reprezentare prin diagrame(grafuri) de tranzitie

Stari:

Stare initiala:

Stari finale:

Functia de tranzitie:

LFAC (2014-15) Curs 2 14 / 26


Reprezentare prin matricea de tranzitie

A = ({q0, q1}, {a, b}, , q0, {q1})

LFAC (2014-15) Curs 2 15 / 26


Limbajul acceptat

Extensia lui la cuvinte : Q Q1 (q, ) = q, q Q;2 (q,ua) = ((q,u),a)), q Q, u , a .

Observatii:(q,a) = (q,a), q Q, a (q,uv) = ((q,u), v), q Q, u, v

LFAC (2014-15) Curs 2 16 / 26


Limbajul acceptat

Definitie 2Limbajul acceptat (recunoscut) de automatul A = (Q, ,, q0,F ) estemultimea :

L(A) = {w |w , (q0,w) F}.

Un cuvant w este recunoscut de un automat A daca, dupa citirean ntregime a cuvantului w , automatul (pornind din starea initialaq0 ) ajunge ntr-o stare finala.(q, a) = (q, a), q Q, a . Din acest motiv, va fi notata deasemenea cu .

Doua automate A si A sunt echivalente, daca L(A) = L(A)LFAC (2014-15) Curs 2 17 / 26


Exemple

LFAC (2014-15) Curs 2 18 / 26


Exemple

L(A) = {anbm|n 0,m 1}

LFAC (2014-15) Curs 2 18 / 26


Exemple

L(A) = {anbm|n 0,m 1}

L(A) = {a, b}

LFAC (2014-15) Curs 2 18 / 26


Exemple

Automate deterministe pentru:

L = {w {0, 1}|w contine un numar par de 0}

L = {w {0, 1}|w se termina cu 11}

LFAC (2014-15) Curs 2 19 / 26

Automate finite nedeterministe

Curs 2


2 Lema Bar-Hillel



LFAC (2014-15) Curs 2 20 / 26



Definitie 3Un automat finit nedeterminist este un 5-uplu A = (Q,, , q0,F ),unde:

Q, , q0 si F sunt definite ca n cazul automatelor finitedeterministe

este o functie , : Q 2Q, numita functia de tranzitie

Observatie:A este automat determinist, daca

|(q, a)| = 1, q Q, a

LFAC (2014-15) Curs 2 21 / 26


Exemple

LFAC (2014-15) Curs 2 22 / 26


Extensia lui la cuvinte

Fie S multime de stari. Notam (S, a) = qS (q, a).Extensia lui la cuvinte : Q 2Q

1 (q, ) = {q}, q Q;2 (q,ua) = ((q,u),a), q Q, u , a .

LFAC (2014-15) Curs 2 23 / 26


Extensia lui la cuvinte

Fie S multime de stari. Notam (S, a) = qS (q, a).Extensia lui la cuvinte : Q 2Q

1 (q, ) = {q}, q Q;2 (q,ua) = ((q,u),a), q Q, u , a .

Observatii:(q,a) = (q,a), q Q, a (q,uv) = ((q,u), v), q Q, u, v .

LFAC (2014-15) Curs 2 23 / 26


Limbajul acceptat

Definitie 4Limbajul acceptat (recunoscut) de automatul finit nedeterministA = (Q,, , q0,F ) este multimea :

L(A) = {w |w , (q0,w) F 6= }.

Un cuvant w este recunoscut de un automat A daca, dupa citirean ntregime a cuvantului w , automatul (pornind din starea initialaq0 ) poate sa ajunga ntr-o stare finala.

LFAC (2014-15) Curs 2 24 / 26


Determinism = Nedeterminism

Teorema 1Pentru orice automat nedeterminist A, exista unul determinist A

echivalent.

Daca A = (Q,, , q0,F ) atunci A = (2Q,, ,Q0,F ) unde:Q0 = {q0}F = {S|S Q,S F 6= }(S, a) = sS (s, a) (= (S, a)), S 2Q

Pentru aplicatii se construiesc doar starile accesibile din stareainitiala

LFAC (2014-15) Curs 2 25 / 26


Exemplu

LFAC (2014-15) Curs 2 26 / 26

Proprietati de nchidere pentru L3Lema Bar-HillelAutomate finite deterministeAutomate finite nedeterministe

limbaje 2

Documents