limbaje 2
Post on 09-Nov-2015
214 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
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
-
Proprietati de nchidere pentru L3
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
-
Proprietati de nchidere pentru L3
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
-
Proprietati de nchidere pentru L3
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
-
Proprietati de nchidere pentru L3
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
1 Proprietati de nchidere pentru L3
2 Lema Bar-Hillel
3 Automate finite deterministe
4 Automate finite nedeterministe
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
1 Proprietati de nchidere pentru L3
2 Lema Bar-Hillel
3 Automate finite deterministe
4 Automate finite nedeterministe
LFAC (2014-15) Curs 2 11 / 26
-
Automate finite deterministe
Automate finite
Mecanism de recunoastere (acceptare) pentru limbajeLimbaje de tip 3Multime finita de stari
LFAC (2014-15) Curs 2 12 / 26
-
Automate finite deterministe
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
-
Automate finite deterministe
Reprezentare prin diagrame(grafuri) de tranzitie
Stari:
Stare initiala:
Stari finale:
Functia de tranzitie:
LFAC (2014-15) Curs 2 14 / 26
-
Automate finite deterministe
Reprezentare prin matricea de tranzitie
A = ({q0, q1}, {a, b}, , q0, {q1})
LFAC (2014-15) Curs 2 15 / 26
-
Automate finite deterministe
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
-
Automate finite deterministe
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
-
Automate finite deterministe
Exemple
LFAC (2014-15) Curs 2 18 / 26
-
Automate finite deterministe
Exemple
L(A) = {anbm|n 0,m 1}
LFAC (2014-15) Curs 2 18 / 26
-
Automate finite deterministe
Exemple
L(A) = {anbm|n 0,m 1}
L(A) = {a, b}
LFAC (2014-15) Curs 2 18 / 26
-
Automate finite deterministe
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
1 Proprietati de nchidere pentru L3
2 Lema Bar-Hillel
3 Automate finite deterministe
4 Automate finite nedeterministe
LFAC (2014-15) Curs 2 20 / 26
-
Automate finite nedeterministe
Automate finite nedeterministe
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
-
Automate finite nedeterministe
Exemple
LFAC (2014-15) Curs 2 22 / 26
-
Automate finite nedeterministe
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
-
Automate finite nedeterministe
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
-
Automate finite nedeterministe
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
-
Automate finite nedeterministe
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
-
Automate finite nedeterministe
Exemplu
LFAC (2014-15) Curs 2 26 / 26
Proprietati de nchidere pentru L3Lema Bar-HillelAutomate finite deterministeAutomate finite nedeterministe
top related