Lucrări de laborator Limbaje formale și automate

Lucrarea practică № 1

1. Pentru gramatica formală G=(VN, VT, P, S) construiți 5 șiruri care aparțin limbajului L(G) generat de această gramatică.

2. Construiți arborii de derivare pentru aceste șiruri.

3. Construiți (desenați) automatul finit echivalent.

4.

Varianta 2.

VN={S, R,L },

VT={a, b,c,d,e,f } ,

P= {

1. S - aS

2. S - bS

3. S - cR

4. R - dL

5. L - fL

6. L - eL

7. L - d

}

Șiruri ce aparțin limbajului

1) S- aS - abS - abcR - abcdL - abcdeL - abcded

2) S - bS - bcR - bcdL - bcdfL- bcdfeL - bcdfed

3) S - aS - acR - acdL - acdfL - acdfeL - acdfed

4) S - bS - bcR - bcdL - bcdeL - bcdefL - bcdefd

5) S - aS - abS - abcR - abcdL - abcdfL - abcdfd

Schema automatului finit echivalent gramaticii:

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

a)S - >aS b)L - >d

S - >bS

S - >cS

R - >dL

L - >fL

L - >eL

Algoritmul de construire AF:

1. Q = VN{x}={ S, R,L }

2. =VT={ a, b,c,d,e,f }

3. q0=S

4. F={X}

1. (S,a) = {S}

2. (S,b) = {S}

3. (S,c) = {R}

4. (R,d) = {L}

5. (L,f) = {L}

6. (L,e) = {L}

7. (L,d) = {X}

Reprezentarea prin tablel

a b c d e f

S S S R - - -

R - - - L - -

L - - - X L L

Concluzie

Efectuând lucrarea de laborator dată am însușit mai bine temele teoretice, am făcut cunoștință cu tipurile de gramatici, cu automatele finite care sunt mecanisme pentru recunoașterea limbajelor de tipul 3 (regulate). Un automat finit (AF) se compune dintr-o bandă de intrare și un dispozitiv de comandă.

In rezultatul executarii lucrarii date s-a obtinut arborii de derivare și automatul finit echivalent care verifica gramatica regulata G conform producțiilor indicate și generează toate cuvintele, care apartin limbajului L generat de aceasta gramatica. Adica putem spune ca limbajul generat de gramatica data este echivalent cu automatul finit și automatul finit verifica pe deplin limbajul L(G) .