Lab 1 LFA [PDF]

Zitiervorschau

Universitatea Tehnică a Moldovei Facultatea Calculatoare Informatică şi Microelectronică Departamentul ISA

LUCRARE DE LABORATOR Nr.1 la Limbaje Formale şi Automate Tema:

Limbajele regulate

A efectuat:

st.grupei TI-173 Semeniuc Eric lector superior Duca Ludmila

A verificat:

Chişinău 2018

Cuprinsul: Scopul lucrării ………………………………………………..2 Datele inițiale …………………………………………………2 Arborele de derivare…………………………………………..3 Metoda tabelară……………………………………………….4 Metoda grafului a automatului finit………………………….5 Metoda analitică ……………………………………………...5 Concluzia……………………………………………………….6

2

Scopul lucrării: 1. Pentru gramatica formală G=(VN, VT, P, S) construiţi 5 şiruri care aparţin limbajului L(G) generat de această gramatică. Lungimea şirului trebuie să fie nu mai mică decît numărul de caractere din alfabetul Vn 2 2. Pentru fiecare şir să se construiască arborele de derivare. 3. Desenaţi automatul finit echivalent acestei gramatici. 4. La ce clasă a gramaticilor dacă Chomsky aparţine gramatica dată.

Datele iniţiale : VN ={A, B,C,D,E} VT ={ g , f , h , n , m }

P={ 1. A→fC 2. A→mB 3. A→mD 4. C→nB 5. B→fA 6. B→gE 7. B→hD 8. B→hB 9. D→nE 10. E→g 11. E→ mA } 1. A→mD→mhB→mhfA→mhfmB→mhfmfA→mhfmfmD→mhfmfmmE→mhfmfmmg; A

B

B

A

B

A

D

E

m

h

f

m

f

m

m

g

2. A→mB→mgE→mgmA→mgmmB→mgmmhB→mgmmhhD→mgmmhhnE→mgmmhhng; A

B

E

A

B

B

D

E

m

g

m

m

h

h

n

g

3

3.A→mD→mhE→mhmA→mhmmB→mhmmfA→mhmmfmB→mhmmfmgE →mhmmfmgg; A

D

E

A

B

A

B

m

n

m

m

f

m

g

E

g

4. A→mB→mfA→mfmD→mfmhB→mfmhfA→mfmhfmD→mfmhfmnE→mfmhfmng; A

B

A

D

B

A

D

E

m

f

m

h

f

m

n

g

5.A→mD→mnE→mnmA→mnmmB→mnmmfA→mnmmffC→mnmmffnB→ mnmmffngE→mnmmffngg; A

D

E

A

B

A

C

B

E

m

n

m

m

f

f

n

g

g

4

AF=(Q, , , q0, F), unde Q – mulţimea de stări  - vocabular  - funcţia de tranziţie q0 – starea iniţială F – mulţimea stărilor finale Algoritmul de construire AF: 1. Q = VN{X}={A,

B,C,D,E,X} =VT={ g , f , h , n , m }

2. 3. q0=A 4. F={X}

Metoda analitică: Pentru fiecare productie difinim ,,  ” a sa.

Funcții de tranziție: 1.

(A,f)=C

2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

(A,m)=B (A,m)=D (C,n)=B (B,f)=A (B,g)=E (B,h)=D (B,h)=B (D,n)=E (E,g)=X (E,m)=A

Echivalarea gramaticii cu AF 1. 2. 3. 4.

Q = VN{X}={ A , B , C, D, E, X } =VT={ m, n, e, +, 1 } q0={A} F={X} 5

Metoda tabelară

A C B D E X

f C

g

h

n

m B,D

B A

-

E X -

D B

E

-

-

-

Mulțimea de producții: JFLAP: Gramarr->Input.CYKParse

6

Reprezentarea cuvintelor Cuvintul 1: mhfmfmmg ;

Cuvintul 2: mgmmhhng;

7

Cuvintul 3: mhmmfmgg;

Cuvintul 4: mfmhfmng;

8

Cuvintul 5: mnmmffngg;

Schema automatului finit echivalent gramaticii:

Concluzii: În urma efectuării date de laborator am obţinut experienţă în domeniul limbajelor şi anume a limbajelor regulate care sunt foarte importante în proiectarea compilatoarelor. Astfel am perceput în practică lucrul cu acest tip de limbaje, adică construirea şirurilor, a arborelor de derivare precum şi desenarea automatelor finite echivalente, etc. Pentru desenarea grafului a automatului finit am folosit programul JFLAP. 9

Am reprezentat autmatul finit prin cele 3 metode: grafica, tabelara si analitica.

10