limbaje formale, automate si compilatoareotto/lfac2018-19/lfac1.pdf · limbaje formale opera¸tii...

Limbaje Formale, Automate si Compilatoare

Curs 1

2018-19

LFAC (2018-19) Curs 1 1 / 45

Prezentare curs

Limbaje Formale, Automate si Compilatoare - Curs 1

1 Prezentare curs

2 Limbaje formale

3 Mecanisme de generare a limbajelor: gramatici

4 Ierarhia lui Chomsky

5 Limbaje si gramatici de tip 3 (regulate)

6 Proprietati de ınchidere pentru familia de limbaje regulate

LFAC (2018-19) Curs 1 2 / 45

Prezentare curs

Limbaje Formale, Automate si Compilatoare

Titulari curs:

O. Captarencu: [email protected]

http://profs.info.uaic.ro/ ˜ otto/lfac.html

A. Moruz:[email protected]

LFAC (2018-19) Curs 1 3 / 45

http://profs.info.uaic.ro/~otto/lfac.html

Prezentare curs

Sistem evaluare

7 seminarii, 6 laboratoare;

AS = activitatea la seminar (max 10 puncte);

AL = activitatea la laborator (max 10 puncte);

T1,T2 teste scrise ın saptamanile 8, respectiv ın sesiune;

Punctajul final se obtine astfel:

P = 3 * AS + 3 * AL + 2 * T1 + 2 * T2

Conditii miminale de promovare: AS ≥ 5, AL ≥ 5, T 1 ≥ 5, T 2 ≥ 5;

Punctaj minim pentru promovare: P ≥ 50;

Nota finala se va stabili conform criteriilor ECTS;

LFAC (2018-19) Curs 1 4 / 45

Prezentare curs

Sistem evaluare

AS = activitatea la seminar (max 10 puncte):

doua teste scrise

AL = activitatea la laborator (max 10 puncte):

1 test laborator, 1 proiect (note de la 0 la 10)

AL = media celor 2 note

LFAC (2018-19) Curs 1 5 / 45

Prezentare curs

Tematica cursului (partea I)

LFAC (2018-19) Curs 1 6 / 45

Prezentare curs


LFAC (2018-19) Curs 1 7 / 45

Prezentare curs


Limbaje si gramatici

Limbaje regulate; gramatici, automate , expresii regulate

Limbaje independente de context; gramatici, automate pushdown

LFAC (2018-19) Curs 1 8 / 45

Prezentare curs

Tematica cursului (partea II)

Limbaje de programare: proiectare si implementare

Analiza lexicala

Analiza sintactica

Traducere ın cod intermediar

LFAC (2018-19) Curs 1 9 / 45

Prezentare curs

Bibliografie (selectii)1 A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman: Compilers:

Principles, Techniques, and Tools. Boston: Addison-Wesley, 20072 Gh. Grigoras. Constructia compilatoarelor - Algoritmi

fundamentali, Ed. Universitatii Al. I. ”Cuza Iasi”, ISBN

973-703-084-2, 274 pg., 20053 Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006).

Introduction to Automata Theory, Languages, and Computation

(3rd ed.). Addison-Wesley4 J. Toader - Limbaje formale si automate, Editura Matrix Rom,

Bucuresti, 1999.5 J. Toader, S. Andrei - Limbaje formale si teoria automatelor. Teorie

si practica, Editura Universitatii ”Al. I. Cuza”, Iasi, 2002.LFAC (2018-19) Curs 1 10 / 45

Limbaje formale


1 Prezentare curs

2 Limbaje formale





LFAC (2018-19) Curs 1 11 / 45

Limbaje formale

Alfabet, cuvant, multtime de cuvinte

Alfabet: V o multime finita (elementele lui V = simboluri )

LFAC (2018-19) Curs 1 12 / 45

Limbaje formale



Cuvant: sir finit de simboluri

cuvantul nul este notat cu ǫ sau λ.

LFAC (2018-19) Curs 1 12 / 45

Limbaje formale





Lungimea unui cuvant u: numarul simbolurilor sale. Notatie: |u|.

|ǫ| = 0

LFAC (2018-19) Curs 1 12 / 45

Limbaje formale






|ǫ| = 0

V ∗ - multimea tuturor cuvintelor peste alfabetul V, inclusiv ǫ.

{0, 1}∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000, 001, . . .}

LFAC (2018-19) Curs 1 12 / 45

Limbaje formale






|ǫ| = 0

V ∗ - multimea tuturor cuvintelor peste alfabetul V, inclusiv ǫ.

{0, 1}∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000, 001, . . .}

V+ - multimea tuturor cuvintelor nenule peste alfabetul V

{0, 1}+ = {0, 1, 00, 01, 10, 11, 000, 001, . . .}

LFAC (2018-19) Curs 1 12 / 45

Limbaje formale

Operatii pe cuvinte

Concatenarea a doua cuvinte x, y: cuvantul x · y obtinut din

simbolurile lui x, ın ordinea ın care apar, urmate de cele ale lui y

de asemenea ın ordinea ın care apar:

x = 0100, y = 100, x · y = 0100100

x = 000, y = ǫ, x · y = 000

LFAC (2018-19) Curs 1 13 / 45

Limbaje formale

Operatii pe cuvinte




x = 0100, y = 100, x · y = 0100100

x = 000, y = ǫ, x · y = 000

Concatenarea este asociativa

LFAC (2018-19) Curs 1 13 / 45

Limbaje formale

Operatii pe cuvinte




x = 0100, y = 100, x · y = 0100100

x = 000, y = ǫ, x · y = 000


(V ∗, ·) este monoid (ǫ este element neutru), se numeste monoidul

liber generat de V .

LFAC (2018-19) Curs 1 13 / 45

Limbaje formale

Operatii pe cuvinte




x = 0100, y = 100, x · y = 0100100

x = 000, y = ǫ, x · y = 000




Cuvantul v este un prefix al cuvantului u daca ∃w ∈ V ∗ : u = vw ;

daca w ∈ V+ , atunci v este un prefix propriu al lui u.

LFAC (2018-19) Curs 1 13 / 45

Limbaje formale

Operatii pe cuvinte




x = 0100, y = 100, x · y = 0100100

x = 000, y = ǫ, x · y = 000




Cuvantul v este un prefix al cuvantului u daca ∃w ∈ V ∗ : u = vw ;

daca w ∈ V+ , atunci v este un prefix propriu al lui u.

Cuvantul v este un sufix al cuvantului u daca ∃w ∈ V ∗ : u = wv ;

daca w ∈ V+ , atunci v este un sufix propriu al lui u.LFAC (2018-19) Curs 1 13 / 45

Limbaje formale

Fie V un alfabet. O submultime L ⊆ V ∗ este un limbaj (formal)

peste alfabetul V (sau V-limbaj) daca L are o descriere

(matematica) finita.

O descriere poate fi:

LFAC (2018-19) Curs 1 14 / 45

Limbaje formale





neformala (ın limbaj natural):

multimea cuvintelor peste alfabetul {0, 1} care contin un numar par

de 0.

L = {x ∈ V+: |x | este par}.

{anbn|n ∈ N}.

{w ∈ {0, 1}∗|w se termina in 00}.

LFAC (2018-19) Curs 1 14 / 45

Limbaje formale





neformala (ın limbaj natural):

multimea cuvintelor peste alfabetul {0, 1} care contin un numar par

de 0.

L = {x ∈ V+: |x | este par}.

{anbn|n ∈ N}.

{w ∈ {0, 1}∗|w se termina in 00}.

formala (descriere matematica):

o descriere inductiva a cuvintelor

o descriere generativa a cuvintelor (gramatica generativa)

o descriere a unei metode de recunoastere a cuvintelor din limbaj

(automat finit, automat pushdown, etc.)

LFAC (2018-19) Curs 1 14 / 45

Limbaje formale

Operatii cu limbaje

Operatiile cu multimi (reuniune, intersectie etc)

Produs de limbaje: L1 · L2 = {u · v |u ∈ L1, v ∈ L2}

Exemplu:

L1 = {an,n ≥ 1}, L2 = {bn,n ≥ 1}

L1 · L2 = {anbm,n ≥ 1,m ≥ 1}

Iteratia (produsul Kleene): L∗ =⋃

n≥0 Ln, unde:

L0 = {ǫ}

Ln+1 = Ln · L

Exemplu:

L = {a}, L0 = {ǫ},L1 = L,L2 = {aa}, . . . ,Ln = {an}

L∗ = {an,n ≥ 0}

LFAC (2018-19) Curs 1 15 / 45

Mecanisme de generare a limbajelor: gramatici


1 Prezentare curs

2 Limbaje formale





LFAC (2018-19) Curs 1 16 / 45


Gramatici

Definitie 1

O gramatica este un sistem G = (N,T ,S,P), unde:

N si T sunt doua alfabete disjuncte:

N este multimea neterminalilor

T este multimea terminalilor

S ∈ N este simbolul de start (neterminalul initial)

P este o multime finita de reguli (productii) de forma x → y, unde

x , y ∈ (N ∪ T )∗ si x contine cel putin un neterminal.

LFAC (2018-19) Curs 1 17 / 45


Derivare

Definitie 2

Fie G = (N,T ,S,P) o gramatica si u, v ∈ (N ∪ T )∗.

Spunem ca v este derivat direct (ıntr-un pas) de la u prin aplicarea

regulii x → y, si notam u ⇒ v, daca ∃p, q ∈ (N ∪ T )∗ astfel ıncat

u = pxq si v = pyq.

LFAC (2018-19) Curs 1 18 / 45


Derivare

Definitie 2




u = pxq si v = pyq.

Daca u1 ⇒ u2 . . . ⇒ un, n > 1, spunem ca un este derivat din u1 ın

G si notam u1 ⇒+ un.

LFAC (2018-19) Curs 1 18 / 45


Derivare

Definitie 2




u = pxq si v = pyq.

Daca u1 ⇒ u2 . . . ⇒ un, n > 1, spunem ca un este derivat din u1 ın

G si notam u1 ⇒+ un.

Scriem u ⇒∗ v daca u ⇒+ v sau u = v .

LFAC (2018-19) Curs 1 18 / 45


Limbaj generat

Definitie 3

Limbajul generat de gramatica G este:

L(G) = {w ∈ T ∗|S ⇒+ w}

LFAC (2018-19) Curs 1 19 / 45


Limbaj generat

Definitie 3

Limbajul generat de gramatica G este:

L(G) = {w ∈ T ∗|S ⇒+ w}

Definitie 4

Doua gramatici G1 si G2 sunt echivalente daca L(G1) = L(G2).

LFAC (2018-19) Curs 1 19 / 45


Exemplu

G = (N,T ,S,P), N = {S,X ,A}, T = {a, b}, P consta din:

1 S → aXb2 aX → aAb3 Xb → bA4 aA → aa5 A → ǫ

L(G) = {ab, abb, aabb}

Gramatica echivalenta cu un singur neterminal ?

Ce limbaj genereaza gramatica daca sunt eliminate utlimele doua

reguli?

LFAC (2018-19) Curs 1 20 / 45


Exemplu

L = {anbn|n ≥ 1}

Definitia inductiva:

ab ∈ L

Daca X ∈ L, atunci aXb ∈ L

Nici un alt cuvant nu face parte din L

LFAC (2018-19) Curs 1 21 / 45


Exemplu

L = {anbn|n ≥ 1}

Definitia inductiva:

ab ∈ L

Daca X ∈ L, atunci aXb ∈ L

Nici un alt cuvant nu face parte din L

Definitia generativa:

G = ({X}, {a,b},X ,P), unde P = {X → aXb,X → ab}

Derivarea cuvantului a3b3:

X ⇒ aXb ⇒ a(aXb)b ⇒ aa(ab)bb

LFAC (2018-19) Curs 1 21 / 45


Exemplu

L = {anbncn|n ≥ 1}

G = (N,T ,S,P), N = {S,X}, T = {a, b, c}, P consta din:1 S → abc2 S → aSXc3 cX → Xc4 bX → bb

Derivarea cuvantului a3b3c3:

S ⇒(2) aSXc ⇒(2) aaSXcXc ⇒(1) aaabcXcXc ⇒(3)

aaabXccXc ⇒(4) aaabbccXc ⇒(3) aaabbcXcc ⇒(3)

aaabbXccc ⇒(4) aaabbbccc = a3b3c3

LFAC (2018-19) Curs 1 22 / 45

Ierarhia lui Chomsky


1 Prezentare curs

2 Limbaje formale





LFAC (2018-19) Curs 1 23 / 45



1 Gramatici de tip 0 (generale)

Nu exista restrictii asupra regulilor

LFAC (2018-19) Curs 1 24 / 45





2 Gramatici de tip 1 (dependente de context)

reguli de forma pxq → pyq unde x ∈ N, y 6= ǫ, p, q ∈ (N ∪ T )∗,

S → ǫ, caz ın care S nu apare ın dreapta regulilor

LFAC (2018-19) Curs 1 24 / 45








3 Gramatici de tip 2 (independente de context)

reguli de forma A → y unde A ∈ N si y ∈ (N ∪ T )∗

LFAC (2018-19) Curs 1 24 / 45








3 Gramatici de tip 2 (independente de context)

reguli de forma A → y unde A ∈ N si y ∈ (N ∪ T )∗

4 Gramatici de tip 3 (regulate)

reguli A → u sau A → uB unde A,B ∈ N si u ∈ T ∗.

LFAC (2018-19) Curs 1 24 / 45


ExempleTip 1: pxq → pyq unde x ∈ N, y 6= ǫ, p, q ∈ (N ∪ T )∗, S → ǫ

G = (N,T ,S,P), N = {S,A,B}, T = {a,b, c}, P:

(1)S → aaAc

(2)aAc → aAbBc

(3)bB → bBc

(4)Bc → Abc

(5)A → a

Gramatica tip 1

G = (N,T ,S,P), N = {S,X}, T = {a,b, c}, P:

(1)S → abc

(2)S → aSXc

(3)cX → Xc (nu este regula de tip 1!, gramatica va fi de tip 0)

(4)bX → bb

LFAC (2018-19) Curs 1 25 / 45


ExempleTip 2: A → y unde A ∈ N si y ∈ (N ∪ T )∗

Tip3: A → u sau A → uB unde A,B ∈ N si u ∈ T ∗.

G:

(1)x → axb

(2)x → ǫ

(Gramatica tip 2)

G:

(1)x → ax

(2)x → bx

(3)x → ǫ

(Gramatica tip 3)

LFAC (2018-19) Curs 1 26 / 45


Exemple

FieG = ({E}, {a,+,−, (, )},E , {E → a,E → (E + E),E → (E − E)})

.

Ce tip are gramatica G ?

Construiti derivari din E pentru cuvintele (a + a) si ((a + a)− a)

Cuvantul (a + a − a) poate fi derivat din E?

Descrieti limbajul L(G)

Fie G = ({A,B}, {a, b},A, {A → aA,A → B,B → bB,B → ǫ})

Ce tip are gramatica G ?

Descrieti limbajul L(G)

LFAC (2018-19) Curs 1 27 / 45


Clasificarea limbajelor

Un limbaj L este de tipul j daca exista o gramatica G de tipul j

astfel incat L(G) = L, unde j ∈ {0, 1, 2, 3}.

Vom nota cu Lj clasa limbajelor de tipul j, unde j ∈ {0, 1, 2, 3}.

Are loc: L3 ⊂ L2 ⊂ L1 ⊂ L0

Incluziunile sunt stricte:

orice limbaj de tip j + 1 este si de tip j ∈ {0,1,2}

exista limbaje de tip j care nu sunt de tip j + 1, j ∈ {0,1,2}

LFAC (2018-19) Curs 1 28 / 45


Proprietati

Fiecare din familiile Lj cu 0 ≤ j ≤ 3 contine toate limbajele finite

Fiecare din familiile Lj cu 0 ≤ j ≤ 3 este inchisa la operatia de

reuniune:

L1, L2 ∈ Lj =⇒ L1 ∪ L2 ∈ Lj ,

∀j : 0 ≤ j ≤ 3

LFAC (2018-19) Curs 1 29 / 45


Notatii alternative pentru gramatici de tip 2: BNF

LFAC (2018-19) Curs 1 30 / 45


gramatici DTD

genereaza multimea documentelor XML cu o anumita structura

(limbaj independent de context)

LFAC (2018-19) Curs 1 31 / 45


gramatici DTD

Un ”cuvant” din limbajul generat de gramtica DTD:

LFAC (2018-19) Curs 1 32 / 45


XML Schema

- rol similar gramaticilor DTD

LFAC (2018-19) Curs 1 33 / 45

Limbaje si gramatici de tip 3 (regulate)


1 Prezentare curs

2 Limbaje formale





LFAC (2018-19) Curs 1 34 / 45


Gramatici de tip 3

O gramatica G = (N,T ,S,P) este de tip 3 daca regulile sale au

forma: A → u sau A → uB unde A,B ∈ N si u ∈ T ∗.

Exemplu: G = ({D}, {0, 1, ..., 9},D,P)

Unde P este:

D → 0D|1D|2D| . . . |9D

D → 0|1| . . . |9

LFAC (2018-19) Curs 1 35 / 45


Exemple

Fie gramatica G = ({A,B}, {l , d},A,P) unde P este:

A → lB, B → lB|dB|ǫ (l = litera, d = cifra)

LFAC (2018-19) Curs 1 36 / 45


Exemple



L(G): multimea identificatorilor

Fie gramatica G = ({A,B}, {+,−, d},A,P) unde P este:

A → +dB| − dB|dB, B → dB|ǫ (d = cifra)

LFAC (2018-19) Curs 1 36 / 45


Exemple



L(G): multimea identificatorilor

Fie gramatica G = ({A,B}, {+,−, d},A,P) unde P este:

A → +dB| − dB|dB, B → dB|ǫ (d = cifra)

L(G): multimea constantelor intregi

LFAC (2018-19) Curs 1 36 / 45


Forma normala

O gramatica de tip 3 este in forma normala daca regulile sale sunt

de forma A → a sau A → aB, unde a ∈ T , si, eventual S → ǫ ( caz

in care S nu apare in dreapta regulilor).

Pentru orice gramatica de tip 3 exista o gramatica echivalenta in

forma normala.

LFAC (2018-19) Curs 1 37 / 45


Forma normala

Obtinerea gramaticii in forma normala echivalenta cu o gramaticade tip 3:

Se poate arata ca pot fi eliminate regulile de forma A → B

(redenumiri) si cele de forma A → ǫ (reguli de stergere), cu

exceptia, eventual a regulii S → ǫ.

Orice regula de forma A → a1a2 . . . an se inlocuieste cu

A → a1B1,B1 → a2B2, . . ., Bn−2 → an−1Bn−1, Bn−1 → an, n > 1,

B1, . . . ,Bn−1 fiind neterminali noi.

Orice regula de forma A → a1a2 . . . anB se inlocuieste cu A → a1B1,

B1 → a2B2, . . ., Bn−2 → an−1Bn−1, Bn−1 → anB, n > 1, B1, . . . ,Bn−1

fiind neterminali noi

Transformarile care se fac nu modifica limbajul generat de

gramaticaLFAC (2018-19) Curs 1 38 / 45

Proprietati de ınchidere pentru familia de limbaje regulate


1 Prezentare curs

2 Limbaje formale





LFAC (2018-19) Curs 1 39 / 45

Proprietati de ınchidere pentru familia de limbaje regulate

Fie L, L1, L2 limbaje de tip 3 (regulate).

Atunci, urmatoarele limbaje sunt de asemenea de tip 3:

L1 ∪ L2

L1 · L2

L∗

L1 ∩ L2

L1 \ L2

LFAC (2018-19) Curs 1 40 / 45

limbaje formale, automate si compilatoareotto/lfac2018-19/lfac1.pdf · limbaje formale opera¸tii...

Documents