limbaje formale si automate

UNIVERSITATEA TRANSILVANIA DIN BRAOV DEPARTAMENTUL PENTRU NVMNT LA DISTAN

FACULTATEA DE MATEMATIC I INFORMATIC CATEDRA DE INFORMATIC TEORETIC

PROF. DR. DANIELA MARINESCU

ASIST. IOANA PLAJER PREP. ALEXANDRA BICOIANU

LIMBAJE FORMALE

I TEORIA AUTOMATELOR

NVMNT LA DISTAN

BRAOV 2009-2010

- 1 -

Introducere

Teoria limbajelor formale a aprut n conexiune cu studiul limbajelor naturale dar ea a avut o dezvoltare rapid datorit calculatorului electronic i a limbajelor de programare. Cercetrile romneti n limbaje formale au nceput n coala de lingvistic matematic creat i condus de Solomon Marcus, din cadrul Universitii Bucureti. Printre reprezentanii acestei coli se numr: Gheorghe Pun, Gabriel Orman, Cristian Calude. Limbajele formale au o mulime de aplicaii n diferite domenii: compilarea automat, traducerea automat dintr-un limbaj natural ntr-altul, decidabilitate i calculabilitate, demonstrarea teoremelor, analiza imaginilor, modelarea unor procese chimice sau biologice, arhitectura, pictura,

modelarea unor probleme de cercetri operaionale .a.m.d. O nou direcie deschis de Pun Gheorghe, este o aplicaie practic a metodelor lingvistice n studiul proceselor economice. Cursul de fa i propune s trateze aspecte ale teoriei limbajelor formale strns legate de teoria compilrii. El se adreseaz, n special, studenilor de la seciile de informatic, dar poate fi folosit i de cititori care nu au o pregtire special n acest domeniu, pentru c noiunile folosite au fost introduse gradat i metodic.

Astfel cursul este compus din patru mari module:

Modulul 1, Introducere n teoria limbajelor formale, i propune s introduc cititorul n domeniu prin definirea noiunilor de limbaj, de reprezentare a unui limbaj, de gramatic de iruri de tip Chomsky. Se definete o ierarhizare a gramaticilor, datorat lui Chomsky, i se introduc o serie de operaii cu limbaje care vor permite studierea n capitolele urmtoare a proprietilor de nchidere ale diferitelor familii de limbaje.

Modulul 2, Automate finite i limbaje de tip 3, este dedicat limbajelor de tip 3 din ierarhia lui Chomsky, care sunt privite ca limbaje generate de gramatici de tip 3, recunoscute de

automatele finite sau reprezentate de expresii regulate. Se demonstreaz c cele trei moduri de reprezentare sunt echivalente. Se prezint un foarte interesant algoritm de minimizare a automatului finit, algoritm care permite realizarea unui analizor lexical optim.

Modulul 3, Proprieti ale familiei limbajelor de tip 3, prezint proprieti i probleme de decizie ale acestor limbaje, folosind cele trei moduri de reprezentare ale limbajelor

regulate: gramaticile de tip 3, automatele finite i expresiile regulate.

Modulul 4, Limbaje idependente de context i automate push-down, definete o serie de forme speciale ale gramaticilor independente de context, numite forme normale Chomsky

i Greibach, i demonstreaz legtura dintre limbajele generate de geramaticile de tip 2 i limbajele recunoscute de automatele push-down nedeterministe. Se demonstreaz i aici o serie de proprieti ale familiei limbajelor independente de context o lem de pompare pentru limbajele independente de context.

Obiectivele cursului

Cursul i propune ca obiectiv familiarizarea studenilor cu noiuni de limbaje formale i teoria automatelor, necesare n modelarea proceselor, n procesarea limbajelor naturale i, mai ales, n construcia compilatoarelor pentru limbaje de programare evoluate.

- 2 -

Competene conferite

Dup parcurgerea materialului studentul va fi capabil s:

Identifice tipuri diferite de gramatici din ierarhia lui Chomsky;

Construiasc gramatici pentru diferite limbaje din ierarhia lui Chomsky;

Construiasc automate finite i automate push-down n funcie de clasa de limbaje pe care doresc s o recunoasc;

Construiasc reprezentari sub form de expresii regulate pentru anumite limbaje de tip 3;

Scrie programe pentru o serie de algoritmi descrii n cadrul acestui curs.

Resurse i mijloace de lucru

Este indicat s se foloseasc urmtoarele mijloace de lucru:

Parcurgerea cursului cu notarea separat a noiunilor importante care vor trebui reinute;

Refacerea exemplelor prezentate n curs;

Rezolvarea problemelor propuse la sfirit de unitate de nvare;

Testarea programelor realizate la laborator cu exemple rezolvate cu mna.

Structura cursului

Cursul este structurat n 4 module i 14 uniti de nvare, dup cum urmeaz:

Modulul 1 conine 3 uniti de nvare; Modulul 2 conine 4 uniti de nvare; Modulul 3 conine 2 uniti de nvare; Modulul 4 conine 5 uniti de nvare.

Fiecare unitate de nvare necesit ntre 2 i 4 ore de nvare;

Exist 2 teme de control, prima fiind prezentat la sfritul modulului 3 iar cea de a doua la sfritul modulului 4;

Transmiterea temelor de control se va face n mod electronic i sub form de material tiprit;

Transmiterea rezultatelor se va face direct, n ziua exmenului, cu comentarea problemelor aprute, i n format electronic.

Cerine preliminare

Discipline necesare a fi parcurse naintea disciplinei curente:

Algoritmica;

Structuri de date;

Programare procedural

Programare obiect orientat;

Algoritmica grafurilor.

- 3 -

Discipline deservite

Cursul de Limbaje Formale si Teoria Automateleor este absolut necesar n

nelegerea cursului de Tehnici de compilare .

Durata medie de studiu individual

Timpul estimativ de studiu individual necesar parcurgerii modulelor este

urmtorul:

Modulul 1 conine 3 uniti de nvare a cte 2-3 ore=8 ore;

Modulul 2 conine 4 uniti de nvare a cte 3 ore=12 ore;

Modulul 3 conine 2 uniti de nvare a cte 3 ore=6 ore;

Modulul 4 conine 5 uniti de nvare a cte 3-4 ore=16 ore.

Evaluarea

Nota final este compus din 4 evaluari dup cum urmeaz:

ponderea evalurii finale (examen/colocviu) este de 50%;

ponderea evalurilor pe parcurs (teme de control, verificri pe parcurs)

este de 25%

ponderea proiectelor/colocvii de laborator este de 25%.;

- 4 -

Cuprins

Introducere .................................................................................................................................. 1

Chestionar evaluare prerechizite .................................................................................................. 9

Modulul 1. Introducere n Teoria Limbajelor Formale Introducere. .................................................................................................................. 9

Competene ................................................................................................................... 9

Unitatea de nvare I.1 Notiuni generale de teoria limbajelor formale .......................... 9

I.1.1. Introducere....................................................................................... 10

I.1.2. Obiectivele unitii de nvare ......................................................... 10

I.1.3. Noiunea de limbaj ......................................................................... ..10

I.1.4. Rezumat ........................................................................................... 17

Test de evaluare/autoevaluare ................................................................... 16

Unitatea de nvare I.2. Algoritmi normali n sens Markov ........................................ 18

I.2.1. Introducere....................................................................................... 18

I.2.2. Obiectivele unitii de nvare ......................................................... 18 I.2.3. Algoritmi normali n sens Markov.................................................... 18

I.2.4. Exemple ........................................................................................... 19

I.2.5. Rezumat ........................................................................................... 25


Unitatea de nvare I.3. Gramatici analitice i generative ........................................... 26

I.3.1. Introducere....................................................................................... 26

I.3.2. Obiective .......................................................................................... 26

I.3.3. Gramatici analitice i generative ..................................................... 26

I.3.4. Ierarhia lui Chomsky ........................................................................ 30

I.3.5. Operaii cu limbaje ........................................................................... 35

I.3.6. Rezumat ........................................................................................... 38


Modulul II. Automate finite i limbaje de tip 3 ............................................................................ 39

Introducere. ................................................................................................................ 39

Competene ................................................................................................................. 39

Unitatea de nvare II.1. Automate finite i limbaje de tip 3 ....................................... 40

II.1.1. Introducere ..................................................................................... 40

II.1.2. Obiectivele unitii de nvare ....................................................... 40

- 5 -

II.1.3. Automate finite ................................................................................ 40

II.1.4. Legtura dintre gramaticile regulate i automatele finite ................ 45

II.1.5. Rezumat .......................................................................................... 52


Unitatea de nvare II.2. Minimizarea automatului finit ............................................. 53

II.2.1. Introducere ..................................................................................... 53


II.2.3. Minimizarea automatului finit ......................................................... 53

II.2.4. Algoritmi de minimizare a automatului finit .................................... 57

II.2.5. Rezumat .......................................................................................... 61


Unitatea de nvare II.3. Gramatici regulate i expresii regulate ............................... 62

II.3.1. Introducere ..................................................................................... 62


II.3.3. Gramatici de tip 3 i expresii regulate ............................................. 62

II.3.4. Algoritm de transformare a unei gramatici regulate ntr-o

expresie regulat ............................................................................. 65

II.3.5. Rezumat .......................................................................................... 70


Unitatea de nvare II.4. Expresii regulate i automate finite ..................................... 71

II.4.1. Introducere ..................................................................................... 71


II.4.3. Algoritm de construcie a unui automat finit pornind de la o

expresie regulat ........................................................................... 71

II.4.4. Rezumat .......................................................................................... 76


Modulul III Proprieti ale limbajelor regulate .......................................................................... 77

Introducere. ................................................................................................................ 77

Competene ................................................................................................................. 77

Unitatea de nvare III.1 Proprieti de nchidere pentru limbaje regulate. ................ 78

III.1.1. Introducere .................................................................................... 78

III.1.2. Obiectivele unitii de nvare ...................................................... 78

III.1.3. Proprieti de nchidere pentru limbaje regulate ............................ 78

III.1.4. Rezumat ......................................................................................... 85


Unitatea de nvare III.2. Lema de pompare pentru limbaje regulate ......................... 86

- 6 -

III.2.1. Introducere .................................................................................... 86

III.2.2. Obiectivele unitii de nvare ...................................................... 86

III.2.3. Proprieti ale limbajelor regulate ................................................. 86

III.2.4. Lema de pompare .......................................................................... 88

III.2.5. Rezumat ......................................................................................... 90


Tem de contro Il ........................................................................................................ 91

Modulul IV Limbaje independente de context.. ........................................................................... 92

Introducere. ................................................................................................................ 92

Competene ................................................................................................................. 92

Unitatea de nvare IV.1. Arbori de derivaie pentru gramatici independente de

context ...................................................................................................... 93

IV.1.1. Introducere .................................................................................... 93

IV.1.2. Obiectivele unitii de nvare ...................................................... 93

IV.1.3 Arbori de derivaie pentru gramatici I.D.C.. .................................... 93

IV.1.4. Rezumat ......................................................................................... 98


Unitatea de nvare IV.2. Simplificarea gramaticilor independente de context.i

forme normale

IV.2.1. Introducere .................................................................................... 99

IV.2.2. Obiectivele unitii de nvare ...................................................... 99

IV.2.3. Simplificarea gramaticilor independente de context. ...................... 99

IV.2.4. Forme normale pentru gramatici I.D.C. ....................................... 105

IV.2.5. Rezumat ....................................................................................... 114

Test de evaluare/autoevaluare ............................................................... ..113

Unitatea de nvare IV.3.Lema de pompare pentru limbaje independente de contex..115

IV.3.1. Introducere .................................................................................. 115

IV.3.2. Obiectivele unitii de nvare .................................................... 115

IV.3.3. Lema de pompare pentru limbaje I.D.C. ....................................... 115

IV.3.4.Rezumat. ....................................................................................... 120

IV.2.5. Rezumat ....................................................................................... 120

Test de evaluare/autoevaluare ................................................................. 120

Unitatea de nvare IV.4. Automate push-down i legtura lor cu gramaticile

independente de context ................................................... 121

IV.4.1. Introducere .................................................................................. 121


- 7 -

IV.4.3. Automate push-down ................................................................... 122

IV.4.4. Legtura dintre automate push-down i gramatici de tip 2 ........... 126

IV.4.5. Rezumat ....................................................................................... 132


Unitatea de nvare IV.5. Proprieti de nchidere ale familiei limbajelor de tip 2.....133

IV.5.1. Introducere .................................................................................. 133


IV.5.3. Proprieti de nchidere pentru limbaje I.D.C................................ 133

IV.5.4. Rezumat ....................................................................................... 143


Tem de control II ..................................................................................................... 144

Bibliografie .............................................................................................................................. 145

- 8 -

Chestionar evaluare prerechizite

1. Definii urmtoarele noiuni: tip de data, variabil ntr-un algoritm, stare a execuiei unui algoritm (program), calcul efectuat de un program (algoritm), algoritm parial corect, testarea unui program, complexitatea unui algoritm.

2. Descriei metoda backtracking. Precizai 2 exemple de probleme rezolvate prin backtracking.

3. Cum se realizeaz trasmiterea parametrilor pentru funcii (java/c++)?

4. Cum se realizeaz generarea numerelor aleatoare n java/c++?

5. Ce nelegei prin precedena operatorilor? Oferii exemple.

6. iruri de caractere:

a. Cum se determin lungimea unui ir?

b. Cum se determin poziia unui caracter ntr-un ir dat?

c. Cum extragem un subir dintr-un ir?

d. Cum se realizeaz nlocuirea unui subir cu un alt subir?

e. Cum se obine inversul unui ir?

7. Instruciuni repetitive: a. Care este forma general a instruciunii for?

b. Care este forma general a instruciunii while? Precizai pentru fiecare subpunct condiii de ieire din ciclu.

8. Ce este recursivitate? Precizati un exemplu.

9. Definii urmtoarele noiuni: graf neorienatat, graf orientat, muchie, arc, nod surs, nod

scop, lista de adiacen.

10. Definii urmtoarele noiuni:

a. Arbore binar, subarbore, parcurgere n inordine, parcurgere n preordine, parcurgere n

postordine, frunz, succesor, rdcin;

b.Stiv, coad, list simplu nlnuit.

- 9 -

Modulul 1. Introducere n Teoria Limbajelor Formale

Cuprins

Introducere..........................................................................................................................9

Competene.........................................................................................................................9

U1. Noiuni generale de teoria limbajelor formale............................................................10

U2. Algoritmi normali n sens Markov.............................................................................18

U3. Gramatici analitice i generative................................................................................26

Introducere

Introducem, n acest modul, o serie de noiuni folosite n teoria limbajelor formale cum ar fi: alphabet, simbol, cuvnt, subcuvnt, prefix, suffix, cuvnt vid. Noiunea de limbaj formal se definete apoi n mai multe feluri, echivalente ntre ele, pornind de la sisteme de rescriere, pn la gramatici generative i analitice.

n afar de gramatici se mai prezint un exemplu de sistem de rescriere, algoritmul normal n sens Markov, pentru care se dau o serie de exemple de funcionare.

n continuare se prezint o ierarhizare a gramaticilor, numit Ierarhia lui Chomsky, i se definesc operaiile cu limbaje.

Competene

La sfritul acestui modul studenii vor fi capabili s:

Foloseasc noiunile definite n descrierea limbajelor formale;

Construiasc gramatici generative i analitice pentru diferite limbaje;

Construiasc algoritmi normali n sens Markov cu o intrare i o ieire; fixat;

Implementeze algoritmii prezentai ntr-un limbaj de programare general.

- 10 -

Unitatea de nvare M1.U1. Noiuni generale de teoria limbajelor formale

Cuprins

M1.U1.1. Introducere ............................................................................................... 10

M1.U1.2. Obiectivele unitii de nvare .................................................................. 10 M1.U1.3. Noiunea de limbaj .................................................................................... 10 M1.U1.4. Rezumat ................................................................................................... 17

M1.U1.1. Introducere

Noiunile folosite n teoria limbajelor formale au fost preluate din lingvistic dei sunt folosite de multe ori cu sens schimbat. Astfel limbajul este definit ca o

mulime de cuvinte iar n lingvistic, care se refer la un limbaj natural, limbajul este o mulime de fraze care sunt la rndul lor mulimi de cuvinte.

Problema delicat este de a defini n mod finit o mulime infinit sau foarte mare de cuvinte.

In acest prim parte se definete un limbaj prin proprieti specifice ale cuvintelor sale sau printr-un sistem de reguli care conduc la generarea cuvimtelor

sale .

M1.U1.2. Obiectivele unitii de nvare

Aceast unitate de nvare i propune ca obiectiv principal o iniiere a studenilor

n noiuni specifice Limbajelor formale.

La sfritul acestei uniti de nvare studenii vor fi capabili s:

neleag i s explice algoritmii de generare a cuvintelor unui limbaj;

demonstreze corectitudinea unei construcii de limbaj.

Durata medie de parcurgere a unitii de nvare este de 2 ore.

M1.U1.3 Noiunea de limbaj

Noiunea de limbaj se ntlnete att n lingvistic, unde se refer la limbajele naturale, ct i n informatic, unde se refer la limbajele de programare.

- 11 -

O limb natural se definete, conform dicionarului, ca o mulime de cuvinte i de metode de combinare a lor, folosit i neleas de o comunitate uman considerabil. Un limbaj de programare se definete ca o mulime de programe corecte scrise n acel limbaj.

O limb natural sau un limbaj de programare pot fi considerate ca mulimi de secvene, adic iruri finite de elemente ale unui anumit vocabular de baz. Pentru a putea studia proprietile acestor limbaje a fost necesar formalizarea noiunii de limbaj, construirea unei teorii matematice riguroase a limbajelor. O astfel de teorie este suficient

de general pentru a include i limbajele naturale i limbajele de programare, precum i o mulime de alte limbaje, formnd la un loc aa numitele limbaje formale. Pentru a putea defini noiunea de limbaj formal vom introduce o serie de noiuni i notaii folosite frecvent n aceast teorie.

Definiia 1.1.1 Un alfabet sau vocabular, V, este o mulime finit, nevid de elemente.

Definiia 1.1.2 Un element al alfabetului V se numete liter sau simbol.

n cele ce urmeaz vom folosi ca simboluri cifrele, literele latine i greceti mari i mici i simboluri speciale cum ar fi $, #.

Exemplul 1 Exemple de alfabete sunt:

-alfabetul latin: {A, B, C, ..., Z}

-alfabetul grecesc: {, , , ..., } -alfabetul binar: {0, 1}.

Definiia 1.1.3 Un cuvnt peste alfabetul V este un ir finit constnd din zero sau mai multe simboluri ale lui V, unde un acelai simbol poate s apar de mai multe ori.

Notm cu sau , cuvntul vid, format din zero simboluri. Dac V este un alfabet atunci prin V* vom nota mulimea tuturor cuvintelor peste V,

inclusiv cuvntul vid , iar V+= V* - .

Exemplul 2 Dac V = 0, 1 atunci V*=, 0, 1, 00, 01, 10, 11, ...

i

V+=0, 1, 00, 01, 10, 11, 000 , ....

Evident V* i V+ sunt mulimi infinite deoarece ele conin cuvinte de lungime orict de mare.

- 12 -

Definiia 1.1.4 Un limbaj este o mulime de cuvinte peste un alfabet.

Exemplul 3 ntr-un limbaj natural alfabetul, n sensul definiiilor de mai sus, este dicionarul limbii respective, cuvintele sunt frazele, iar limbajul este mulimea tuturor frazelor. ntr-un limbaj de programare simbolurile sunt instruciunile limbajului, cuvintele sunt programele iar limbajul este mulimea tuturor programelor.

n mulimea cuvintelor se introduce o operaie numit concatenare:

Definiia 1.1.5 Dac u i v sunt dou cuvinte din V* atunci concatenarea uv este tot un cuvnt din V*, care se obine prin alturarea simbolurilor lui v dup ultimul simbol al lui u.

Observaia 1.1.1 Evident operaia de concatenare este asociativ, u(vw)=(uv)w, dar nu este

comutativ (n general uvvu) iar cuvntul vid este element neutru relativ la operaia de concatenare: u=u=u.

Definiia 1.1.6 Puterea a i-a a cuvntului u, notat ui, este definit recursiv astfel:

(1) u0 = (2) ui+1 = uiu

Definiia 1.1.7 Lungimea unui cuvnt u, notat lg(u) sau |u|, este numrul de simboluri ale

cuvntului u i este o aplicaie lg: V* N . Prin definiie lg() = 0, fiind cuvntul format din zero simboluri.

Definiia 1.1.8 Un cuvnt u este subcuvnt al lui v dac i numai dac exist cuvintele i astfel nct v = u. Dac = atunci u se numete prefix al lui v iar dac = atunci u se numete sufix al lui v. Un subcuvnt u al lui v se numete subcuvnt propriu al lui v numai dac

u{,v}.

Majoritatea limbajelor care ne intereseaz vor conine o mulime infinit de cuvinte. Se pun atunci trei chestiuni importante:

1. Cum se poate reprezenta un limbaj?

Dac limbajul este finit atunci el s-ar putea reprezenta prin enumerarea cuvintelor sale, dei la un numr mare de cuvinte enumerarea poate fi complicat. Dac ns limbajul este infinit apare problema gsirii unei reprezentri finite pentru limbaj. Apare atunci o alt problem:

2. Exist o reprezentare finit pentru orice limbaj? Evident mulimea V* a tuturor cuvintelor peste un alfabet finit V este o mulime numrabil. Un limbaj este o submulime a lui V*, deci mulimea tuturor limbajelor peste V este mulimea prilor lui V*, adic o mulime nenumrabil. Dei nu am definit nc o reprezentare finit a unui limbaj, se pare c mulimea reprezentrilor finite este numrabil [4] deci ar rezulta c exist mai multe limbaje dect reprezentri finite ale limbajelor.

- 13 -

3. Ce se poate spune despre structura acelor clase de limbaje care admit reprezentri finite? Aceasta este una din principalele problemele de care ne vom ocupa n continuare.

S considerm acum cteva limbaje peste alfabetul {a, b}.

L1={ } L2={ a, ba, aaba, bbbb }

L3={ ap | p numr prim }

L4={ ai b

i | i numr natural }

L5={ u *

,ba | Na(u)=Nb(u) }

unde Na (u) este numrul de apariii ale simbolului a n cuvntul u. Considerm i limbajul vid

, care nu conine nici un cuvnt Se observ c {} pentru c limbajul { } conine un cuvnt i anume . Limbajele L1 i L2 fiind finite se pot reprezenta prin enumerarea cuvintelor lor pe cnd limbajele L3, L4 i L5 sunt infinite i au fost caracterizate de o proprietate pe care trebuie s o satisfac toate cuvintele limbajului. O astfel de proprietate specific este un mijloc de baz de definire a unui limbaj infinit.

Un alt mod de a defini un limbaj infinit este de a introduce un mecanism generativ i de a considera cuvintele produse de acest mecanism.

Se poate, de asemenea, construi un mecanism analitic, de recunoatere. Astfel un limbaj se poate defini ca mulimea tuturor cuvintelor recunoscute de un astfel de mecanism. Mecanismele generative i analitice se pot defini n termenii unui sistem de rescriere. S considerm cteva moduri de definire ale unor limbaje n exemplele urmtoare.

Exemplul 4 Fie L un limbaj peste alfabetul {a, b} definit dup cum urmeaz:

(i) L (ii) Dac x L atunci axb L (iii) Nici un alt cuvnt nu aparine lui L.

Vom demonstra prin dubl incluziune c limbajul L construit conform acestor reguli este chiar limbajul L4 = { a

i b

i | i numr natural }.

a) Demonstrm prin inducie relativ la k faptul c NkLba kk , , adic c

L4L: Din (i) =a0b0L . Dac akbkL prin (ii) aakbkbL adic ak+1bk+1L, deci prin inducie

rezult c L4L.

b) Demonstrm, prin inducie relativ la lungimea cuvintelor din L, faptul c

LL4:

a0b

0 , adic , este singurul cuvnt de lungime 0 din L.

Presupunem c akbk este singurul cuvnt de lungime 2k din L ; atunci din (ii) rezult c ak+1bk+1 este singurul cuvnt de lungime 2k+2 din L. Pentru c L nu conine nici un cuvnt de lungime impar (este uor de

- 14 -

demonstrate aceast afirmaie tot prin inducie) rezult c LL4. Din a) i b) rezult c cele dou limbaje sunt egale adic L4 =L .

Se observ c (i)-(iii) constituie un mecanism generativ pe cnd L4 este definit de o proprietate specific.

Exemplul 5 Fie L definit dup cum urmeaz :

(i) L

(ii) Dac xL, atunci axbL i bxaL

(iii) Dac x1L, x2L atunci x1x2L (iv) Nici un alt cuvnt nu aparine lui L. Vom demonstra c L=L5.

Demonstrm nti c LL5.

Pentru c = a0b0are proprietatea de a avea acelai numr de a i de b, adic 0 de a i 0 de b, iar (ii) i (iii) pstreaz proprietatea (acelai numr de apariii ale lui a i b) rezult c L conine numai cuvinte cu acelai numr de apariii ale simbolului a i b. Se demonstreaz prin inducie c L conine toate cuvintele de lungime mai mic sau egal cu 2i cu aceast proprietate.

Exemplul 6 Fie L un limbaj constnd din toate cuvintele care se pot reduce la prin nlocuirea subcuvintelor ab prin . Astfel cuvintele , ab, abab i aabbab L. Evident LL5 dar LL5 pentru c, de exemplu, baL. Definiia aceasta poate fi considerat ca un mecanism de recunoatere sau analitic. n exemplele date anumite subcuvinte sunt rescrise. n conformitate cu

definiia urmtoare, o mulime finit de reguli de rescriere determin un sistem de rescriere.

- 15 -

Definiia 1.1.9 Un sistem de rescriere este o pereche ordonat SR=(V, F), unde V este un alfabet i F o mulime finit de perechi ordonate de cuvinte peste V. Elementele (,) ale lui F sunt

numite reguli de rescriere sau producii i se noteaz . Un cuvnt peste V genereaz direct un cuvnt (

SR ) dac i numai dac exist

cuvintele u, v, 1 , 1 astfel nct: =u1v =u1v

iar

11 F, adic subcuvntul 1 al lui este nlocuit prin subcuvntul 1.

Un cuvnt peste V genereaz (n mai muli pai) (*

) dac i numai dac exist un

ir finit de cuvinte 0, 1 , ..., k, k 0, unde 0=, k= i i i+1, pentru 0 i k-1. Secvena 0 1... k se va numi derivaie a lui din n conformitate cu sistemul de rescriere, SR.

= 0 1 2.... k=

Astfel relaia este o relaie binar pe V* iar *

este nchiderea reflexiv i tranzitiv a

relaiei . Numrul k se numete lungimea derivaiei sau numr de pai.

Observaia 1.1.2 Dac este o relaie binar pe o mulime W , atunci nchiderea reflexiv i tranzitiv * a relaiei se definete :

(i) P*P pentru orice PW (ii) Dac P1*P2 i P2P3 P1*P3 (iii) P*Q numai dac se poate stabili prin (i) i (ii).

Un sistem de rescriere poate fi transformat ntr-un mecanism generativ prin specificarea

unei submulimi Ax V*, numit mulimea de axiome, i considernd limbajul

(1) Lg(SR, Ax)={ | *

, Ax } Similar un sistem de rescriere poate fi privit ca un mijloc analitic sau de recunoatere, considernd limbajul

(2) La(SR, Ax)={ | *

, Ax } Formula (1) reprezint limbajul generat de perechea (SR, Ax), iar formula (2) reprezint limbajul recunoscut sau acceptat de perechea (SR, Ax).

Observaia 1.1.3 De cele mai multe ori mulimea Ax este format dintr-un singur simbol (simbolul iniial) sau are o structur foarte simpl.

Observaia 1.1.4 De cele mai multe ori V se mparte n dou submulimi : VT, mulimea terminalelor VN, mulimea neterminalelor sau a variabilelor

i limbajul se definete ca o submulime a lui VT *. Revenind la exemplele anterioare, n exemplul 1.1.6, L se poate defini, n termenii unui sistem de rescriere ca:

L = La(SR,{}), unde V={a,b} iar F={ab}.

- 16 -

n exemplul 1.1.4,

L=Lg(SR,{x}){a,b}*, unde

SR=({a,b,x}, {x, xaxb}). Limbajul L din exemplul 1.1.5 este definit acum :

L = Lg(SR,{x}){a,b}*, unde

SR=({a,b,x}, {x, xaxb, xbxa, xxx}). Sistemele de rescriere sunt de asemenea denumite sisteme semi - Thue.

S ne reamintim...

Definiiile pentru: alphabet, simbol, cuvnt, subcuvnt, prefix, suffix, cuvnt vid, limbaj, regul de rescriere, sistem de rescriere, derivaie, axiom.

.

Test de evaluare a cunotinelor

I. ntrebri. Definii noiunile de:

vocabular,

cuvnt,

subcuvnt,

prefix,

suffix,

limbaj,

sistem de rescriere.

II. Exerciii propuse. 1. Furnizai cteva exemple de limbaje peste alfabetul {0, 1}. 2. Care este lungimea cuvntului limbaj? Este aba subcuvnt al lui? Care

este rezultatul pentru (limbaj) 3

?

3. Fie limbajul L = {a

2nb

n | 0

- 17 -

M1.U1.4 Rezumat

Unitatea de nvare prezint cteva elemente introductive n teoria limbajelor formale cum sunt: alphabet, simbol, cuvnt, subcuvnt, prefix, suffix, cuvnt vid.

Noiunea de limbaj formal se definete apoi prin proprieti specifice cuvintelor limbajului, printr-un sistem de generare a cuvintelor sau printr-un sistem de

rescriere. Important pentru fiecare din reprezentri ale unui limbaj este s demonstrm corectitudinea construciei, pentru care s-au prezentat, n unitatea de nvare, mai multe demonstraii.

.

- 18 -

Unitatea de nvare M1.U2. Algoritmi normali n sens Markov

Cuprins

M1.U2.1. Introducere.............................................................................................. 18

M1.U2.2. Obiectivele unitii de nvare ................................................................ 18 M1.U2.3. Algoritmi normali n sens Markov .......................................................... 18

M1.U2.4. Exemple de algoritmi normali.....................................................................19

M1.U2.5. Rezumat......................................................................................................25


Unul din cele mai cunoscute sisteme de rescriere este algoritmul normal n sens

Markov[16]. Caracteristic pentru algoritmul normal Markov este faptul c mulimea de reguli este ordonat i c regulile se aplica unui cuvnt iniial ntr-o anumit ordine.

.


Aceast unitate de nvare i propune ca obiectiv principal familiarizarea

studenilor cu un prim mecanism formal, algoritmul normal n sens Markov.


neleag i s explice algoritmii normali;

construiasc proprii algoritmi normali;

programeze un algoritm normal.

Durata medie de parcurgere a unitii de nvare este de 3-4 ore.

M1.U2.3 Algoritmi normali n sens Markov

Definiia 1.1.10 Un algoritm normal n sens Markov este un sistem de rescriere SR = (V, F) unde

elementele lui F sunt date ntr-o anumit ordine 11, 22 , . . . , kk i exist o submulime, posibil vid, F1F coninnd reguli sau producii finale . ; la fiecare pas al unui proces de rescriere, se aplic prima din regulile lui F care este aplicabil, i n plus se rescrie cea mai din stnga apariie a subcuvntului care este membrul stng al regulei folosite.

- 19 -

Astfel, algoritmii normali n sens Markov posed o proprietate special i anume : pentru orice cuvnt P exist cel mult un cuvnt care poate fi generat din P ntr-un singur pas.

Din punct de vedere formal, dac i numai dac fiecare din urmtoarele condiii este satisfcut.

(i) Exist un numr i, 1 i k i cuvintele ' i " astfel nct ='i", = 'i". (ii) Nici un cuvnt j, j < i, nu este subcuvnt al lui (iii) i apare o singur dat ca subcuvnt al lui 'i. Algoritmul normal reia aplicarea regulilor n ordine atta timp ct este ndeplinita condiia:

(iv) ii nu este un element al lui F1 i unul din cuvintele 1, ..., k este subcuvnt al lui . Dac (iv) nu este ndeplinit, dar sunt ndeplinite (i)-(iii), atunci *. i procesul de rescriere se ncheie.

Deci *. dac i numai dac exist 0, 1 , ..., n astfel nct

=0 1 2 ... n+1 .n= .

O consecin imediat este lipsa ambiguitii. Rezult c exist cel mult un singur cuvnt astfel nct * . . Dac exist un astfel de cuvnt se spune c algoritmul normal se termin cu sau c traduce n . n caz contrar algoritmul cicleaz cu .

M1.U2.4 Exemple de algoritmi normali n sens Markov

Exemplul 7 Fie algoritmul normal peste { a, b } cu regulile de rescriere

1. a

2. b

3. .aba El traduce orice cuvnt din {a,b}* n aba

Exemplificare:

aababba1 ababba 1babba 1bbba1bbb2 bb2 b 2 3. aba

- 20 -

Exemplul 8 Fie algoritmul cu alfabetul { a, x, y, # } i regulile:

1. yaay 2. xaayx 3. x 4. a##x 5. #a# 6. # 7. ya

El traduce orice cuvnt de forma ai # a

j cu i, j 0 n aij, deci realizeaz nmulirea

a dou numere. Fie i = 2 i j = 3. Atunci: aa#aaa4 a#xaaa2 a#ayxaa2 a#ayayxa1 a#aayyxa2 a#aayyayx

1 a#aayayyx1 a#aaayyyx)3(

a#aaayyy4 #xaaayyy2 #ayxaayyy

2 #ayayxayyy1 #aayyxayyy2 #aayyayxyyy1 #aayayyxyyy 1 #aaayyyxyyy3 #aaayyyyyy5 #aayyyyyy5 #ayyyyyy 5 # yyyyyy6 yyyyyy7* aaaaaa.

Exemplul 9 Trecerea de la un numr natural la succesorul su este dat de

algoritmul peste alfabetul = {a} cu mulimea regulilor format numai dintr-o singur regul:

1. a aa. Algoritmul transform un cuvnt de forma ai n ai+1.

Exemplificare:

aaa .aaaa

Exemplul 10 Algoritmul care calculeaz suma a dou sau mai multe numere

este (, P) unde = {a, #} i mulimea regulilor P :

1. # Acest algoritm transform ai#aj n ai+j, ai#aj#ak n ai+j+k, etc.

Exemplificare:

a3 # a

2 # a

4 a5 # a4 a9

- 21 -

Exemplul 11 Modulul diferenei a dou numere: ai#aj a|i-j|

AN = (, P) unde = {a, #} i P conine regulile:

1. a#a # 2. #

S calculm modulul diferenei dintre 4 i 2.

AN : a4 # a

21 a3 # a 1 a2 # 2 a2

Exemplul 12 Restul mpririi unui numr natural la 5 transform: 5/i5ii aa iar AN = (, P) unde = {a} i P :

1. aaaaa

Exemplificare:

AN : a13 a8 a3

Exemplul 13 Ctul mpririi unui numr natural la 5 transform: # 5/ii aa iar algoritmul este definit de :

AN = (, P) unde = {a, #} i

#

#a#

#aaaaaa#

:P

Exemplificare pentru ctul mpririi numrului natural 13 la 5:

AN : # a13

a # a8 a2 # a3 a2 # a2 a2 # a a2 # . a2

- 22 -

Exemplul 14 Ctul i restul mpririi unui numr natural la 5:

# 5/i5i5/ii a#aa

AN = (, P) unde = {a, #} i

##

#aaaaaa#:P

Calculm ctul i restul mpririi numrului natural 13 la 5:

AN : # a13

a # a8 a2 # a3 . a2 # a3

Exemplul 15 Cel mai mare divizor comun a dou numere naturale:

ai#a

jacmmdc(i,j)

1. axxa 2. a#ax# 3. a##y 4. ya 5. xz 6. za 7. #

El traduce ai # a

j n a

k, unde k este cel mai mare divizor comun al lui i i j.

S calculm cel mai mare divizor comun al lui 6 i 4.

-y#ax-#ax-#xaxa-#xxa-a#xa-a#axa-a#xaa-a#xa-

-#aa-a#za-a#za-a#az-a#z-a#xz-a#xz-

-a#zx-a#x-ay#x-y#x-y#ax-#ax-#axax-

-#xax-a#ax-a#axax-a#xaax-a#xax-a#ax-

-a#xaxa-a#xaxa-a#xaxa-a#xxa-a#xa-

-a#axa-a#xaa-a#xaa-a#xaa-a#xa-a#a

22223223

2423222232423222

23244244243

2333222232242

23222232435

34332323343546

222222

22222222222

a-a#-ay#-y#-y#a-#a-#az-#z-#zx-#x-a#xa-

-a#ax-a#a-a#az-a#z-a#zx-a#x-ay#x-y#x-

Similar dac calculm cel mai mare divizor comun al lui 4i 6 avem:

-a#xaa-a#xa-a#a-a#za-a#za-a#az-a#z-

-a#xz-a#xz-a#zx-a#x-a#ax-a#axx-a#ax-

-a#xaxa-a#xxa-a#xa-a#axa-a#xaa-a#xa-a#a

2324232222324

2322223243332422

4425352525364

- 23 -

-#zx-#x-a#xa-a#ax-a#a-a#az-a#z-a#zx-a#x-

-ay#x-y#x-y#ax-#ax-#xaxa-#xxa-a#xa-a#axa-

222222222

222222232

22222 a-a#-ay#-y#-y#a-#a-#az-#z-

Exemplul 16 mprirea a dou numere naturale: j/ijij/iji a#aa#a

AN = (, P) unde = {a, #, x, y, c, r, s, t} i P:

ra

y

x

s

ssa

ssx

s#cx#c

x##a

#acyx#a

t

tta

rttx

t#ca#c

axaxaa

caac

:P

2

Exemplificri

5423

32454322

332234

42232322425253

r#-ar#-ar-#

-ar#-ra#-a#-xaa#-xaxaa#-xaxaxaa#-xaxaaxa#-

-xaxaxa-#xaxaa#a-xaxaa#a-xaaxa#a-xaxa#a-

-xaa#a-xaa#a-xaa#a-axa#a-xa#a-a#a

- 24 -

-xaxaxaxa#ca-axaxaxa#ca-xaxaxa#ca-xaxaa#ca-

-xaxa#ca-xaa#ca-xa#ca-a#ca-a#yca-axaxaxa#yca

-axaxaxa#cya-xaxaxaxa#a-axaxaxa#a-xaxaxa#a-

-xaxaa#a-xaxa#a-xaa#a-xa#a-a#a

342425

35364647477

77828

2939310410411

-xa#ac-a#ac-a#yac-axaxaxa#yac-axaxaxa#cyca- 422432432323

322

322222222

2222232322

r#c-tr#c-

-tar#c-txar#c-taxar#c-rtxaxa#c-rtaxaxa#c-txaxaxa#c-

-axaxaxa#c-xaxaxa#c-xaxaa#ac-xaxa#ac-xaa#ac-

3

#cs#c

saxaxaxa#cxaxaxaxa#caxaxaxa#acxaxaxa#ac

xaxaa#acxaxa#acxaa#acxa#aca#ac

a#yacaxaxaxa#yacaxaxaxa#cycaxaxaxaxa#ca

axaxaxa#caxaxaxa#caxaxaa#caxaxa#ca

xaa#caxa#caa#caa#ycaaxaxaxa#yca

axaxaxa#cyaxaxaxaxa#aaxaxaxa#axaxaxa#a

xaxaa#axaxa#axaa#axa#aa#a

33

32222

222322332432442

4424244

5252636

374748488

88929

210310311411412

Definiia 1.1.11 Un sistem normal Post este un sistem de rescriere (V, F) unde toate elementele

(, ) ale lui F sunt notate prin xx, x fiind o variabil operaional. (Se presupune c x V i nici nici nu au x ca subcuvnt). Relaia se definete astfel: 11 dac i numai dac exist cuvintele , u, peste V\{x} astfel nct: 1=u, 1=u, i xxF.

Se poate i aici specifica o mulime de axiome i se poate defini limbajul generat i cel recunoscut la fel ca mai sus.

1 S se construiasc un algoritm normal n sens Markov care s realizeze nlocuirea literelor a i b dintr-un cuvnt de intrare, prin cuvintele alpha, respectiv beta adic algoritmul codificrii.

2 S se construiasc un algoritm normal n sens Markov care s calculeze puteri-

le lui 2, adic care s transforme cuvntul an# n a2 . S se exemplifice algoritmul

- 25 -

pentru urmtoarele valori ale lui n: a. n = 2; b. n = 3; c. n = 4.


I. ntrebri. 2. Cum se definete un algoritm normal Markov?. 3. Cnd se oprete un algoritm nornal n sens Markov?

II. Exerciii propuse. 1. S se construiasc un algoritm normal n sens Markov care s calculeze

lungimea unui cuvnt adic care s transforme un cuvnt de w n 0|w|., unde w din {a,b,c}*).

M2.U2.5 Rezumat

Unitatea de nvare prezint unul din primele sisteme de rescriere, algoritmul normal n sens Markov, n care regulile de rescriere sunt ordonate

i se aplic la rndul lor ntr-o anumit ordine. Prezentarea este nsoit de foarte multe exemple pentru nelegerea complexitii unei astfel de construcii, ct i pentru utilizarea acestor exemple n constrcii ulterioare.

S ne reamintim...

Algoritmul normal n sens Markov se caracterizeaz prin faptul c mulimea de reguli este ordonat i c regulile se aplica unui cuvnt iniial ntr-o anumit ordine pn cnd nici o regul nu mai poate fi aplicat sau pn cind s-a aplicat o regul final.

- 26 -

Unitatea de nvare M1.U3. Gramatici generative i analitice

Cuprins

M1.U3.1. Introducere............................................................................................ 26

M1.U3.2. Obiectivele unitii de nvare .............................................................. 26 M1.U3.3. Gramatici generative i analitice ........................................................... 26 M1.U3.4. Ierarhia lui Chomsky............................................................................. 30

M1.U3.5. Operaii cu limbaje................................................................................ 35 M1.U3.6. Rezumat.....................................................................................................38


Noiunea de gramatic formal a fost introdus de lingvistul Noam Chomsky, si reprezint mecanismul generativ cel mai folosit pe parcursul acestui material. Astfel se prezint att gramatici generative ct i analitice i se demonstreaz c ele sunt ntr-o relaie de dualitate, fapt care permite tratarea numai a uneia dintre ele.

Un alt aspect important care va fi tratat este definirea unor operaii cu limbaje ca operaii clasice cu mulimi i chiar a unor operatii specifice limbajelor. .


Aceast unitate de nvare i propune ca obiectiv principal familiarizarea

studenilor cu un al doilea mecanism formal, gramatica generativa n sens Chomsy.


neleag i s explice gramaticile generative;

construiasc propriile gramatici care s genereze un anumit limbaj;

programeze un generarea cuvintelor ntr-o gramatic.


M1.U3.3 Gramatici generative i analitice

Vom defini un tip de mecanism care joac un rol important n teoria limbajelor formale.

Definiia 1.2.1 O gramatic generativ este un quadruplu ordonat G=(VN, VT,S,P) ,

- 27 -

unde VN i VT sunt alfabete finite disjuncte SVN i P este o mulime finit de perechi ordonate (u,v), astfel nct v este un cuvnt din V*, unde V=VNVT i u este un cuvnt din V* care conine cel puin o liter din VN. Elementele lui VN formeaz mulimea neterminalelor sau variabilelor, iar cele ale lui VT formeaz mulimea terminalelor; S se numete simbolul iniial, iar P sunt reguli de rescriere, producii. De fapt o gramatic este un sistem de rescriere (V, P) numit sistem de rescriere indus de G.

Noiunile de derivare direct sau derivare corespund celor introduse n cadrul unui sistem de rescriere.

Limbajul L(G) generat de G este definit de:

L(G)={ w| wV *, S*

w } Vom introduce o noiune dual celei de gramatic generativ i anume cea de gramatic analitic.

Definiia 1.2.2 O gramatic analitic este un quadruplu ordonat G=(VN, VT, S, P), unde VN, VT, S sunt exact ca n definiia 1.3.1, dar P este o mulime finit de

reguli (u, v) astfel nct u este un cuvnt din V* iar vV* conine cel puin o liter din VN. Limbajul L(G) recunoscut de gramatica G, sau acceptat este definit de :

L(G)={ w| wVT*, w*

S }, deci limbajul cuvintelor formate numai din terminale care se reduc la simbolul iniial prin aplicarea regulilor din P.

Definiia 1.2.3 Dou gramatici, G i G1, se numesc gramatici echivalente atunci i numai atunci cnd L(G)=L(G1).

Exemplul 1 Limbajul L = { aib

i | iN } este generat de gramatica generativ

G = ({S}, {a,b}, S, {S, SaSb}) i recunoscut de gramatica analitic

G1 = ({S}, {a,b}, S, {S, aSbS}) Deci L(G) = L(G1).

Exemplul 2 Limbajul L = { w | w{a,b}*, Na(w)=Nb(w) } este generat de gramatica generativ

G = ({S}, {a,b}, S, {S, Sasb, SbSa, SSS}) i recunoscut de gramatica analitic

G1 = ({S}, {a,b}, S, {S, aSbS, bSaS, SSS}) Vom arta n cele ce urmeaz c orice gramatic analitic admite o gramatic generativ, dual a ei, echivalent.

Teorema 1.2.1 Fie G = (VN, VT, S, P) o gramatic generativ (sau analitic). Fie P1 o mulime de reguli

de forma u v dac v u este n P. Atunci L(G1)=L(G) unde G1=(VN, VT, S, P1) este o gramatic analitic (generativ).

- 28 -

Demonstraie:

Dac G este o gramatic generativ vom demonstra c pentru orice cuvnt din (VNVt)* avem

(1.2.1) S *

G

*

1G S

Vom arta nti prin inducie c dac pentru un anume k

u0 u1 ... uk este o derivaie n G, atunci

uk uk-1 .. u0 este o derivaie n G1. Evident, pentru k=1 afirmaia este valabil conform definiiei regulilor lui P1. Procednd inductiv, presupunem c afirmaia este adevrat pentru k pai i fie o derivaie n k+1 pai de forma:

u0 u1 ... uk uk+1 n G. Conform ipotezei induciei

uk G uk+1 uk+1

1G uk

i u0 *

G uk uk

*

1G u0

Atunci din cele dou rezult c

u0

*

G uk+1 uk+1

*

1G u0

Dac acum u0=S vom obine afirmaia (1.2.1) dorit, deci L(G)=L(G1).

Observaia 1.2.1 Pentru o gramatic generativ sau analitic G, gramatica G1 definit mai sus se va numi duala sa.

Vom da n continuare cteva exemple de gramatici conform cu [21].

Exemplul 3 Fie G = ({S, B, C}, {a, b, c}, S, P}), unde mulimea P este format din:

SaSBC SaBC CBBC bBbb bCbc cCCc aBab

S ncercm o derivaie n gramatica G:

S aSBC aaSBCBC aaaSBCBCBC aaaaBCBCBCBC aaaaBBCCBCBC * aaaaBBBBCCCC aaaabBBBCCCC aaaabbBBCCC aaaabbbBCCCC aaaabbbbCCCC aaaabbbbcCCC aaaabbbbccCC aaaabbbbcccC aaaabbbbcccc

- 29 -

Se poate demonstra c L(G)={anbncn | n1}

Exemplul 4[21] Fie limbajul L={ ww | w{0,1}* }. Gramatica G definit de: G=({x0, x1, x2, x3, y0, y1}, {0,1}, x0, P}), unde P este:

P : x0x1x2x3 x1x2 x3

x1x2ix1yi yijjyi yix3x2ix3 ix2x2i

pentru fiecare i i j din {0,1}

Aceast gramatic genereaz limbajul L. S ncercm o derivaie n aceast gramatic:

x0 x1x2x3 0x1y0x3 0x1x20x3 01x1y10x3 01x10y1x3 01x10x21x3 01x1x201x3 0101x3 0101

Exemplul 5 [21] Pentru limbajul L={an | n1} vom avea urmtoarele reguli

gramaticale care se bazeaz pe identitatea n2=1+3+...+(2n-1), unde toate

simbolurile cu excepia lui a sunt simboluri neterminale:

P : x0a x0axx2z x2zaa xaaa yaaa x2zy1yxz xx1x1yx yx1y1yx xy1x1y yy1y1y ax1axxyx2 x2yxy2 y2yyy2

y2xyx2 S ncercm i aici cteva derivaii:

x0 axx2z axaa aaaa x0 axx2z axy1yxz ax1yyxz axxyx2yyxz axxyxy2yxz axxyxyy2xz axxyxyyx2z axxyxyyaa axxyxyaaa axxyxaaaa axxyaaaaa axxaaaaaa axaaaaaaa

aaaaaaaaa = a9 = a3.

- 30 -

Exemplul 6 [21] ] Pentru generarea limbajului L = { a2

| n0 }vom avea urmtoarele reguli gramaticale

x0yxy yxyz zxxxz zyxxy xa y

Vom construi o derivaie n aceasta gramatic pentru n = 2, pornind de la simbolul iniial x0

x0 yxy yzy yxxy yzxy yxxzy yxxxxy xxxy axxxy aaxxy aaaxy aaaay aaaa

Exemplul 7[21 Fie G=({S,B}, {0,1}, S, P) unde

P:

1B

S1B

0BS

Limbajul generat de G este L(G) = {(01)n

| n>0}. Exemplificm derivaia unui cuvnt din limbaj pentru n = 3.

S 0B 01S 010B 0101S 01010B 010101 = (01)3

Exemplul 8 [21] Fie gramatica G=({S,A,B},{a,b},S,P), unde mulimea regulilor P este P={SaSb,Sab}. Este uor de demonstrat c limbajul generat de gramatica G este

L(G) = {anb

n | n>0}.

Pentru n = 4 obinem urmtoarea derivaie:

S aSb aaSbb aaaSbbb aaaabbbb = a4b4

M1.U3.4 Ierarhia lui Chomsky

Gramaticile generative pot fi clasificate prin impunerea de restricii asupra formei regulilor.

Definiia 1.2.4 (Ierarhia lui Chomsky) Pentru i{0,1,2,3}, o gramatic generativ, G=(VN, VT, S, P) este de tip i dac i numai dac regulile de rescriere din P ndeplinesc restriciile de tip (i): (0) Nici o restrictie.

(1) Reguli dependente de context (DC): Fiecare regul din P este de forma u1Au2u1wu2 , unde u1, u2V*, AVN i w {VN VT }

+ cu o singur excepie posibil S, care poate s

apar dac S nu apare n dreapta nici unei reguli din P.

- 31 -

(2) Reguli independente de context (IDC): Fiecare regul din P este de forma

A w cu A VN i w {VN VT } *.

(3) Reguli regulate (R): Fiecare regul este de una din urmtoarele dou forme A aB sau A a , unde A, BVN i aVT. Gramaticile de tip 1 se numesc dependente de context sau contextuale, gramaticile de tip

2 se numesc independente de context, iar gramaticile de tip 3 se mai numesc i regulate sau cu numr finit de stri. Evident c orice gramatic de tip 3 este i de tip 2, orice gramatic de tip 2 este i de tip 1, i orice gramatic de tip 1 este de tip 0.

Dac notm cu Li familia limbajelor de tip (i) avem, evident, urmtoarea incluziune ntre

familiile de limbaje:

L3 L2 L1 L0 Se va demonstra ulterior c incluziunea este proprie, deci c prin restriciile (0)-(3) se obine ntr-adevr o ierarhizare a familiilor de limbaje.

Definiia 1.5 O gramatic este cu lungime cresctoare sau monoton dac i numai dac regula

uv satisface condiia |u| |v| cu o singur excepie posibil S, care, dac apare n mulimea regulilor, atunci S nu apare n partea dreapt a nici unei reguli.

Observaia 1.2.2 Gramaticile dependente de context sunt gramatici cu lungime cresctoare. Se poate demonstra c gramaticile cu lungime cresctoare i gramaticile dependente de context sunt echivalente.

Teorema 1.2.2

Pentru fiecare gramatic monoton, G, exist o gramatic dependent de context, G, echivalent cu G, adic L(G) = L(G).

Demonstraie. Fie gramatica monoton G=(VN, VT, S, P), n care regulile din P sunt monotone, adic de

forma uv unde |u| |v|. Presupunem c regula uv nu este dependent de context i c este de forma:

A1 A2 Am B1 B2 Bn

Pentru c gramatica este monoton avem m n iar Ai i Bi pot fi simboluri terminale sau variabile. Presupunem c toate simbolurile Ai sunt variabile (n caz contrar nlocuim fiecare simbol terminal Ai printr-un nou symbol neterminal Ai i adugm regula Ai Ai).

Considerm noi variabile C1,C2, , Cm. i nlocuim regula iniial uv prin mulimea de reguli dependente de context P(u,v):

A1 A2 Am C1 A2 Am

C1 A2 Am C1 C2 Am C1 C2 Cm-1Am C1 C2 Cm Bm+1 Bm+2 Bn C1 C2 Cm-1Cm Bm+1 Bn C1 C2 Cm-1Bm Bm+1 Bn C1 C2 Cm-1Bm Bm+1 Bn C1 C2 Cm-2Bm-1 Bm Bn

- 32 -

.. C1 B2 Bn B1 B2 Bn

Fie acum gramatica G = (VN {C1, C2, , Cm}, VT, S, P\ {uv} P(u,v) ). Este uor de demonstrat acum c L(G) = L(G). Procednd de aceeai maniera cu fiecare regula monoton care nu este dependent de context se obine n final gramatica echivalent G.

Exemplul 9 S aplicm algoritmul din teorema 1.2.2 pentru gramatica din exemplul 1.2.3, G = ({S, B, C}, {a, b, c}, S, P}), cu P :

SaSBC SaBC CBBC bBbb bCbc cCCc aBab

Singura regul monoton care nu este dependent de context este regula CBBC nlocuim aceast regul cu urmtoarea mulime de reguli dependente de context:

CB C1B C1B C1C2 C1C2 C1C C1C BC

Obinem n final gramatica dependent de context echivalent cu G, G= ({S,B,C, C1, C2}, {a,b,c}, S, P), unde P:

S aSBC S aBC bB bb bC bc cC Cc aB ab CB C1B C1B C1C2 C1C2 C1C C1C BC.

Observaia 1.2.3 Gramaticile din exemplele 3, 4, i 6 sunt gramatici monotone deci, conform teoremei 1.2.2, limbajele generate sunt dependente de context. Gramatica din exemplul 5 este o

gramatic de tip 0 (exist reguli care nu sunt monotone, ca de exemplu regula x1x2), gramatica din exemplul 8 este independent de context iar cea din exemplul 7 este regulat sau de tip 3.

- 33 -

Pentru gramaticile analitice definiiile rmn aceleai ca i pentru gramaticile generative, schimbnd ns membrul drept cu membrul stng n regulile din P. Noiunea de gramatic generativ cu lungime cresctoare i are corespondentul dual n cea de gramatic analitic cu lungime descresctoare.

Exemplul 10 Din punct de vedere lingvistic, gramaticile sunt folosite pentru

analiza frazelor. S considerm urmtoarea gramatic analitic IDC unde VN = { F, A, V, Pn, S, Sn}, (variabile care reprezint, respective: fraza, articol, verb, predicat nominal, substantiv, subiect), VT = {o, fata, este, laboranta}, unde

fiecare din aceste cuvinte ale limbii romne reprezint un simbol al alfabetului terminalelor. Regulile gramaticii sunt:

{oA, fatS, laborantS, esteV, ASSn, VSPn, SnPnF} Frazele recunoscute sunt :

o fata este laborant

o laborant este fat

o fat este fat

o laborant este laborant Fiecare din fraze este corect gramatical dar unele s-ar putea s nu aib nici un neles.

n cele ce urmeaz vom considera numai gramatici generative, aspectul analitic fiind tratat n capitolele II i III prin intermediul automatelor.

Exemplul 11 Se numete palindrom un cuvnt, care este identic cnd este citit de la stnga la dreapta sau de la dreapta la stnga. Astfel n limba romna exist

palindroamele: capac, coc, cuc, lupul, ele, etc. Notm cu y~ reflectatul sau

oglinditul unui cuvnt y, adic cuvntul ale crui simboluri sunt n ordine invers

fa de y. Limbajul { yy~ | y VT* } este n mulimea palindroamelor cu VT={a1,

..., an} i poate fi generat de gramatica:

G=({S}, VT, S, {S, Sa1Sa1, Sa2Sa2, ..., SanSan}).

n exemplul anterior exist regula S iar S apare i n dreapta altor reguli. Vom arta c exist ca pentru orice astefel de gramatic existo gramatic echivalent n care S nu apare n dreapta nici unei reguli.

Teorema 1.2.3

Dac G = (VN, VT, S, P) este o gramatic DC, atunci exist alt gramatic D.C., G1, care genereaz acelai limbaj cu G, pentru care simbolul initial (de start) nu apare n dreapta nici unei reguli ale lui G1. Dac G este I.D.C. sau R atunci i G1 este I,D,C,, respectiv R.

Demonstraie :

Fie S1VNVT. Construim gramatica G1={VN{S1}, VT, S1, P1 }, unde P1 conine toate regulile din P i n plus toate regulile de forma S1 unde S P :

- 34 -

P1=P{S1 S P } Observm c S1VNVT deci nu apare n dreapta nici unei producii din G i nici n dreapta vreunei producii noi adugate n P. S demonstrm acum c L(G)=L(G1).

a) Presupunem c wL(G), deci exist o derivaie n gramatica G de forma S*

w. Atunci prima

regul folosit este de forma S deci derivaia va fi :

SG

*

Gw

Prin definiia lui P1 avem : S1 P1 i deci:

S11G

Pentru c toate regulile lui P sunt n P1 rezult c orice derivaie din G este i o derivaie n gramatica G1 deci

*

1G w

Combinnd cele dou derivaii se obine:

S11G

*

1G w ,

Deci w L(G1), de unde rezult c L(G)L(G1).

b) Presupunem acum c wL(G1), deci exist derivaia S1*

w n gramatica G1. Prima regul

folosit este de forma S1, pentru un anume . Rezult din construcia gramaticii G1 c S

este o regul din P i deci S, n gramatica G. Acum *

w este o derivaie n gramatica G1 dar nu poate avea simbolul S1, cci folosete numai regulile din P1 care sunt i n P. Rezult c

*

w este o derivaie n gramatica G i atunci:

SG

*

Gw,

adic wL(G). Evident c regulile adugate la P pentru a obine P1 sunt de acelai tip cu regulile lui P deci dac G este DC (IDC sau R) atunci i G1 este DC (IDC sau R).

Teorema 1.2.4

Dac L este un limbaj DC, IDC sau R, atunci i L i L\{} sunt limbaje DC, IDC respectiv R.

Demonstraie : Dac L este un limbaj DC, IDC sau R, din teorema 1.2.3 rezult c exist o gramatic G, care poate fi DC, IDC sau R, n care simbolul iniial, S, nu apare n partea dreapt a nici unei reguli de rescriere. n plus singura regul n care membrul drept poate fi este de forma S.

Atunci pentru limbajul L\{} se scoate regula S, iar pentru limbajul L se adug tot regula S. Toate aceste modificri nu au nici o influen asupra restului cuvintelor generate de G pentru c simbolul iniial S nu mai apare n partea dreapt a nici unei reguli de rescriere.

- 35 -

M1.U3.5 Operaii cu limbaje

Pentru c limbajele sunt mulimi, rezult c se pot folosi toate operaiile cu mulimi cunoscute.

Reuniunea a dou limbaje

L1L2={ w | wL1 sau wL2 }

Intersecie a dou limbaje

L1L2={ w | wL1 i wL2 }

Diferena a dou limbaje

L1-L2={ w | wL1 i wL2 }

Complementara unui limbaj relativ la un alphabet V

CV(L)=V*-L

n afar de aceste operaii se pot introduce o serie de operaii specifice limbajelor :

Concatenarea a dou limbaje

L1L2={uv | uL1, vL2 Limbajele i {} reprezint elementul zero i respectiv elementul unitate relativ la concatenarea limbajelor:

L = L=

L{}={}L=L Concatenarea se mai numete i produs.

Puterea unui limbaj se definete recursiv prin:

L0 = {}

Li+1

= Li L .

Produsul Kleene (sau nchiderea Kleene) este definit prin reuniunea tuturor puterilor lui L:

0i

i* LL

nchiderea Kleene - liber este

1i

iLL

Ctul stng a dou limbaje este limbajul format din sufixele cuvintelor din L1 care au prefixul n L2:

L2\L1={v |uvL1, uL2} Derivata stng a unui limbaj relativ la cuvntul v este

s

v L={u |vuL}

adic ctul stng al limbajelor {v}\L

Ctul drept a dou limbaje este limbajul format din prefixele cuvntelor din L1 cu sufixul n L:

- 36 -

L1/L2 = { v| vuL1 pentru uL2 } Derivata dreapt a unui limbaj relativ la cuvntul u este

udL= {v |vuL}

adic ctul drept al limbajelor: L/{u}

Reflectatul sau oglinditul unui limbaj

L~

= { u~ | uL }

Substituia unui limbaj se definete astfel:

aV definim (a) un limbaj peste Va iar apoi se aplic proprietile: ()=, (uv)=(u)(v) u, v V* deci este o aplicaie : V* P(V*)

unde V=Va

aV

.

Substituia unui limbaj L este atunci:

(L)={ v | v(u) pentru uL }

Dac (a) este un singur cuvnt ua, atunci substituia se numete homomorfism h:V*V*. Un

homomorfism se numete -liber dac nici unul din cuvintele (a)=ua nu este .

Observaia 1.3.1 Pentru c V* este un semigrup liber, h este homomorfism de semigrupuri.

Una din problemele pe care le vom studia n capitolele urmtoare este problema nchiderii

familiilor de limbaje de tip i, Li (i = 0, 1, 2, 3) relative la operaiile introduse.

1. Se consider gramatica monoton

G = ( {A,B}, {a,b}, A, P), unde P:

A Ba B BA Aa Bb B b B bB A a

S se construiasc o gramatic echivalent independent de context.

2. Considerm gramatica G=({x0,x,y,z},{a }, x0, P), unde P este mulimea

produciilor:

(1) x0yxy

(2) xyyz

(3) zxxxz

- 37 -

(4) zyxxy

(5) xa

(6) y

(a) S se dea o derivare n G pentru un cuvnt din L(G).

(b) S se verifice care dintre cuvintele urmtoare aparin limbajului:

{aaaaa,aaaa,a}.

3. S se construiasc gramatic pentru generarea limbajului:

L = {anb

n | n>0}

S ne reamintim...

O gramatic generativ este un quadruplu ordonat G=(VN, VT,S,P) ,

unde VN i VT sunt alfabete finite disjuncte SVN i P este o mulime finit de perechi ordonate (u,v), astfel nct v este un cuvnt din V*, unde V=VNVT i u este un cuvnt din V* care conine cel puin o liter din VN.

Limbajul L(G) generat de G este definit de:

L(G)={ w| wV *, S*

w } Gramaticile i, respectiv, limbajele generate de ele, sunt de 4 tipuri: de tip 0 (fr restricii), de tip 1 (dependente de context), de tip 2 (independente de context) i de tip 3 (regulate).

Operaiile cu limbaje sunt: reuniunea, intersecia complementara, concatenarea, puterea, produsul Klenee, oglindirea, substituia, homomorfismul, homomorfismul invers, derivata sng i dreapt

Teste de evaluare/autoevaluare

I. ntrebri. 1. Ce este o gramatic generativ? 2. Cte tipuri de gramatici generative cunoatei i care sunt acestea?

II. Exerciii propuse.

1. Se d gramatica G=({S,A},{,,, p,q,r, },S, P), unde P =

{SSS, SSS, SS, SA, AA, Ap, Aq, Ar }.

- 38 -

S se verifice dac pqrpqr L(G).

2. S se construiasc o gramatic G care generaz urmtorul limbaj:

L = {a2n

bn | n>0}

M1.U3.6. Rezumat. Aceast unitate de nvare prezint noiunea de gramatic formal, care a fost introdus de lingvistul Noam Chomsky. Gramatica generativ reprezint mecanismul generativ cel mai folosit pe parcursul acestul material. S-au prezentat att gramatici generative ct i analitice i s-a demonstrat c ele sunt ntr-o relaie de dualitate, fapt care permite tratarea numai a uneia dintre ele. Un alt aspect important tratat a fost definirea unor operaii cu limbaje ca operaii clasice cu mulimi i chiar a unor operaii specifice limbajelor..

- 39 -

Modulul 2. Automate finite i limbaje de tip 3

Cuprins

Introducere ................................................................................................................ 39

Competene.....................................................................................................................39

U1. Automate finite i gramatici de tip 3.......................................................................40

U2. Minimizarea automatului finit.................................................................................53

U3. Gramatici regulate i expresii regulate.....................................................................61

U4. Expresii regulate i automate finite..........................................................................71

Introducere

Acest modul se refer la limbajele regulate privite ca limbaje generate de gramatici de tip 3, recunoscute de automatele finite sau reprezentate de expresii regulate. Se

demonstreaz c cele trei moduri de reprezentare sunt echivalente. Se prezint doi algoritmi de minimizare a automatului finit, pe baza crora se poate construe un analizor lexical optim.

Competene

La sfritul acestui modul studenii vor fi capabili s:

Construiasc automate finite deterministe i nedeterministe;

Construiasc gramatici generative de tip3 pentru diferite limbaje;

Construiasc expresii regulate pentru diferite limbaje de tip 3;

S construiasca un mod de reprezentare(gramatica, automat finit, expresie regult) pornind de la alt mod de reprezentare echivalent;

Implementeze algoritmii prezentai ntr-un limbaj de programare general

- 40 -

Unitatea de nvare M2.U1. Automate finite i gramatici de tip 3

Cuprins

M2.U1.1. Introducere............................................................................................ 40

M2.U1.2. Obiectivele unitii de nvare .............................................................. 40 M2.U1.3. Automate finite ..................................................................................... 40

M2.U1.4. Legtura dintre gramaticile regulate i automatele finite ........................ 45 M2.U1.5. Rezumat.....................................................................................................52


Din punct de vedere istoric, automatele finite au fost introduse pentru a modela

reelele neuronale dar au o mulime de aplicaii i n alte domenii cum ar fi: analiza lexical (faza iniial a unui compilator), descrierea editoarelor de texte i a altor programe de procesare a textelor, modelarea circuitelor logice i altele.

Automatul finit este un bun model pentru un calculator cu o cantitate extrem de

limitat de memorie. Vom vede c, dei are o memorie foarte mic, un astfel de calculator poate s fac o serie de lucruri utile cum ar fi cele enumerate mai sus.



Construiasc automate finite care s recunoasca un limbaj anume;

Ineleag i s explice algoritmii de trecere de la un automat finit la o

gramatic i invers, de la o gramatic la un automat finit;

Ineleag i s explice algoritmii de trecere de la un automat finit

nedeterminist la unul determinist echivalent

Implementeze algoritmii prezentai ntr-un limbaj de programare general.


M2.U2.3 Automate finite

n modulul 1 am definit noiunea de limbaj regulat sau limbaj de tip 3, ca fiind limbajul generat de o gramatic de tip 3, adic de o gramatic G=(VN,VT,S,P), unde regulile din P sunt de forma :

- 41 -

AaB sau

Aa Aici A i B, sunt simboluri neterminale iar a este un simbol terminal.

Vom defini n cele ce urmeaz un sistem analitic pentru limbajele regulate i anume automatele finite.

Definiia 2.1.1 Un automat finit determinist, notat M=(Q, , , q0, F), este format din: Q - o mulime finit nevid (mulimea strilor); - un alfabet finit de intrare;

- o aplicaie numit funcie de tranziie, care ataeaz fiecrei combinaii o nou stare

QQ: ;

Qq0 starea iniial;

QF mulimea strilor finale.

Din punct de vedere practic un automat finit este format dintr-un control finit, care se poate

afla ntr-una din strile mulimii Q, dintr-o band de intrare mprit n celule n care sunt scrise un numr finit de simboluri din , i un cap de citire care se mic pe banda de intrare secvenial de la stnga la dreapta (de fapt banda de intrare se mic n dreptul capului de citire de la dreapta la stnga ).

Iniial controlul finit se afl n starea q0 iar capul de citire analizeaz cel mai din stnga

simbol scris pe banda de intrare. Interpretarea lui pa)(q, pentru q,pQ i a, este aceea

c automatul M, aflat n starea q i analiznd simbolul a pe banda de intrare, i schimb starea n p i i mut capul de citire cu o celul la dreapta.

S-ar putea ca funcia de tranziie s nu fie peste tot definit, adic s existe p P i a astfel nct (p,a)=. n cazul n care automatul se afl n aceast stare p i capul de citire vizeaz simbolul a pe banda de intrare se spune c automatul se blocheaz fiindca nu este definit micarea urmtoare.

Aplicaia se poate extinde la *Q , prin :

, a , x a)x),(q, (xa)(q,

q)(q,

*

a0 a1 ai an

Figura 2.1.1

CONTROL

FINIT

- 42 -

unde px)(q, nseamn c M, pornind s analizeze secvena x din starea q, ajunge n starea

p n momentul n care capul de citire depete secvena x.

Observaia 2.1.1 n continuare vom folosi notaia i pentru . Definiia 2.1.2 Un cuvnt x este acceptat sau recunoscut de un automat finit M, dac,

px),(q0

pentru Fp .

Limbajul acceptat de automatul M se noteaz

Fx),(qxT(M)0

.

Un automat finit determinist se poate defini n termenii unui sistem de rescriere SR=(V,

P), unde :

Q unde ,QV Qq

0 starea iniial

QF mulimea strilor finale

i P: kjijki

a i Qq ,q unde ,qaq

i n plus pentru fiecare qiak exist exact o regul n P.

Atunci

Fp p,xq xT(M)0

.

Definiia 2.1.3 Numim configuraie instantanee perechea (q,x), format din starea Qq n

care se afl automatul finit i irul de caractere *x rmas necitit pe banda de intrare, unde capul de citire vizeaz cel mai din stnga simbol al lui x.

Dac automatul finit folosete tranziia pa)(q, , atunci vom nota modificarea

configuraiei astfel: )a(q, ),p( . Specificarea unui automat finit M se poate face prin definirea funciei (ntr-un tabel) sau printr-o diagram de stare sau de tranziie. Diagrama de tranziie este un graf orientat n care nodurile sunt strile automatului iar arcele (q,p) sunt etichetate cu a dac (q,a)=p este o tranziie din automatul M.

Exemplul 1

Fie, de exemplu, automatul finit }{qF , }q,q,q,{qQ , }1,0{

F),q,,(Q,M

03210

0

0 1

Q

q0 q1 q2

q1 q0 q3

q2 q3 q0

q3 q2 q1

- 43 -

Fie irul de intrare 10110010; atunci putem urmri execuia automatului astfel:

, Fq,0)(q,10)(q,010)(q,0010)(q

,10010)(q,110010)(q,0110010)(q,10110010)(q

01323

1320

deci 10110010 T(M) .

n mod echivalent, ntr-un calcul de configuraii se scrie: (q0,10110010) (q2,0110010) (q3,110010) (q1,10010)

(q3,0010) (q2,010) (q3,10) (q1,0) (q0,) unde q0 F,

deci s-a obinut din nou c 10110010 T(M) .

Se poate demonstra c automatul finit M de mai sus accept irurile cu numr par de 0 i numr par de 1.

Definiia 2.1.4 Un automat finit nedeterminist, notat M=(Q, , ,q0, F), este format din Q, , q0, F prezentate n definiia 2.1.1, dar funcia de tranziie este aici

Q)(Q:' P .

Deci a)(q,' este o mulime de stri i nu o singur stare.

i aici se poate extinde la Q astfel:

. a ,x , a)(p,'xa)(q,'

{q})(q,'

x)(q,'p

Acum se poate extinde la Q)(P astfel:

k

1iik21

x),(p'x)},p,...,p,({p'

Definiia 2.1.5 Un cuvnt x este acceptat sau recunoscut de un automat finit nedeterminist M

dac Fx),(q0

, adic dac M pornind din starea q0 i analiznd cuvntul x poate ajunge ntr-o stare final.

n termenii unui sistem de rescriere, definiia este aceeai cu cea pentru un automat finit

determinist fr s existe restricie n cazul unei reguli de forma: jki

qaq , de a fi singura

regul cu acest membru stng. Limbajul acceptat de un automat finit nedeterminist este format din mulimea

cuvintelor acceptate T(M) pentru care exist o secven care conduce la acceptare:

T(M) = {w | (q,w) F }

Exemplul 2 Fie automatul finit descris n figura 2.1.2 cu ajutorul diagramei de tranziie; n acest caz T(M) este mulimea cuvintelor care au sau doi de zero consecutivi sau doi de unu consecutivi.

- 44 -

S urmrim funcionarea acestui automat pentru cteva situaii diferite:

a) Dac irul de intrare este 0101, automatul va face toate ncercrile de tranziii posibile, nainte de a trage concluzia c acest cuvnt nu e recunoscut (nu duce automatul ntr-o stare final):

(q0,0101) (q0,101) (q0,01) (q0,1) (q0,) , Fq 0

(q0,0101) (q0,101) (q0,01) (q0,1) (q1,) , Fq1

(q0,0101) (q0,101) (q0,01) (q3,1) blocare ( )1,(q 3 )

(q0,0101) (q0,101) (q1,01) blocare ( )1,(q1 )

(q0,0101) (q3,101) blocare ( )1,(q 3 )

b) Dac irul de intrare este 0110, automatul va accepta acest cuvnt n momentul depistrii unui calcul de configuraii ce duce automatul ntr-o stare final (indiferent cte ncercri nereuite face, automatul accept irul de intrare la nregistrarea unui succes):

(q0,0110) (q0,110) (q0,10) (q0,0) (q0,) , Fq 0

(q0,0110) (q0,110) (q0,10) (q0,0) (q3,) , Fq 3

(q0,0110) (q0,110) (q0,10) (q1,0) blocare ( )1,(q1 )

(q0,0110) (q0,110) (q1,10) (q2,0) (q2,) , Fq 2 succes !

(q0,0110) (q3,110) blocare ( )1,(q 3 )

c) Configuraiile instantanee ce determin acceptarea n cazul cuvntului de intrare 010011 sunt:

(q0,010011) (q0,10011) (q0,0011) (q3,011) (q4,11) (q4,1) (q4,) i (q0,010011) (q0,10011) (q0,0011) (q0,011) (q0,11) (q1,1) (q2,)

Ambele arat faptul c irul de intrare poate fi citit de pe band ajungnd ntr-o

- 45 -

stare final (q2 sau q4), fiind deci recunoscut. Este suficient gsirea uneia dintre ele, cnd se stabilete acceptarea cuvntului de ctre automat.

Pentru aceeai intrare propus anterior, pot fi ncercate i alte posibile transformri de configuraii, dar care nu termin citirea ntr-o stare final sau nici mcar nu permit finalizarea citirii benzii (ajung la blocare, cnd simbolul de pe band i starea automatului finit nu sunt compatibile d.p.d.v. al funciei de tranziie, cum ar fi cazul citirii simbolului 0 ntr-un moment n care automatul se

afl n starea q1, deoarece se observ c ,0)(q 1 ).

M2.U2.3 Legtura dintre gramaticile regulate i automatele finite

Vom demonstra n cele ce urmeaz c limbajele de tip 3 sunt echivalente cu limbajele recunoscute de automatele finite (numite i mulimi regulate).

Teorema 2.2.1 Fie L o mulime de cuvinte acceptate de un automat finit nedeterminist. Atunci exist un automat finit determinist care accept L.

Demonstraie:

Fie F),q,,(Q,M0

un automat finit nedeterminist care accept L, adic

L=T(M).

Definim )F',q',',,(Q'M'0

un automat finit determinist dup cum urmeaz:

Q'P(Q) noile stri (M pstreaz urma strilor n care poate fi M la un moment dat)

card(Q)k0 Q,q ]q,...,q,[q Q'ik21

;

]q[q00

;

,F' ,Q'F' conine cel puin o stare final din F;

i definim tranziiile: }p,...,p,p{a)},q,...,q,({q ]p,...,p,p[a)],q,...,q,([q

j21t21j1t21

Deci dac este aplicat unui element Z=[q1, q2,....,qk ] din Q', rezultatul este calculat prin aplicarea lui la fiecare stare a lui Q din Z=[q1,q2,. . . ,qk ]:

j1,l ,a),(qp

]p,...,p,p[a)],q,...,q,([qk

1iil

j21k21

Se arat prin inducie asupra lungimii irului de intrare x c :

(2.2.1) }q,...,q,{qx),(q ]q,...,q,[qx),q(i210i210

- pentru |x|=0, ]q[q00

afirmaia (2.2.1) este adevrat;

- presupunem c (2.2.1) este adevrat pentru |x| t ; s studiem atunci intrarea xa, unde a i deci |xa| t+1 :

a)x),,q((xa),q(00

Conform ipotezei induciei, }p,...,p,{px),(q ]p,...,p,[px),q(

j210j210

- 46 -

Prin definiie,

}r,...,r,r{a)},p,...,p,({p ]r,...,r,[ra)],p,...,p,([pk21j21k21j21

Astfel,

}r,...,r,r{xa),(q ]r,...,r,[rxa),q(k210k210

Pentru a completa demonstraia mai avem de adugat c Fx),q(0

exact cnd

x),(q0

conine o stare a lui Q care este n F.

Aadar T(M)=T(M).

Exemplul 1 Considerm automatul finit: }){q ,q , {0,1}, },q,({qM

1010 ,

}q,{q,1)(q

,0)(q

}{q,1)(q

}q,{q,0)(q

101

1

10

100

S se construiasc automatul finit determinist M, echivalent cu M.

S reprezentm automatul M sub form de diagram de tranziie:

Construim M conform Teoremei 2.2.1 :

) ]}q,[q],{[q , ][q , , {0,1} , ]}q,[q],[q],{[q (M 10101010

]q,[q],1)q,([q

]q,[q],0)q,([q

]q,[q],1)([q

],0)([q

][q],1)([q

]q,[q],0)([q

1010

1010

101

1

10

100

Deci automatul M va avea diagrama tranziiilor ca n figura 2.2.2:

- 47 -

Teorema 2.2.2

Fie G=(VN, VT, S, P) o gramatic de tip 3. Atunci exist un automat finit nedeterminist

F),q,,(Q,M0

cu T(M)=L(G).

Demonstraie: Construim

NN VT {T},VQ ;

Sq0 ;

Dac PS , atunci T}{S,F i S nu apare la dreapta nici unei

reguli; dac PS , atunci {T}F ;

TVa ,a)(T, ;

Dac a)(B,T atunci VB , Va

PaB

NT

;

Dac a)(B,C atunci VCB, , Va

PaCB

NT

;

Dac exist NVB care nu apare n membrul stng al nici unei reguli din P,

atunci T

Va ,a)(B, .

Atunci M simuleaz derivaiile n G. S artm c, ntr-adevr, T(M)=L(G):

a) Fie L(G)...aaaxn21 , 1n . Atunci:

n1n211n1n2111a...aaaA...aaa...AaS

pentru anumite variabile Ai din VN. Din construcia automatului M avem:

)a(S,A11

)a,(AA212

Figura 2.2.2

[q0] [q1]

[q0,q1]

Star

t

0,1

1

0 1

- 48 -

)a,(AAn1-n

Aadar: (S, a1a2an) (A1, a2an) (An-1, an) (A,)

Adic cuvntul T(M)...aaa n21 x . Pentru c x a fost din L(G)

T(M)L(G)

b) Fie T(M)x , 1|| x exist strile S,A1,,An-1,T astfel nct:

)a,(AT

...

)a,(AA

)a(S,A

n1n

212

11

PaA

...

PAaA

PAaS

1n

221

11

deci are loc derivaia:

n1n211n1n2122111a...aaaA...aaa...AaaAaS

De aici L(G)T(M) L(G) x

Din (a) i (b) L(G)T(M) .

Teorema 2.2.3 Fiind dat un automat finit determinist M, exist o gramatic G de tip 3 astfel nct L(G)=T(M).

Demonstraie:

Presupunem F),q,,(Q,M0

- automat finit determinist.

Definim o gramatic de tip 3, P),q,(Q,G0

astfel nct:

(i) q ap (q,a) = p (ii) q a (q,a) = p F

Demonstraia este similar cu cea din Teorema 2.2.2.

n plus dac T(M) atunci Fq 0 i q este o regul n G.

- 49 -

Teorema 2.2.4 Clasa limbajelor de tip 3 este echivalent cu clasa limbajelor acceptate de automatele finite.

Demonstraia este evident din Teoremele 2.2.1, 2.2.2 i 2.2.3 .

Observaia 2.2.1 Dup unii autori clasa limbajelor acceptate de automatele finite se numete clasa limbajelor regulate. Datorit teoremei anterioare (2.2.4), clasa limbajelor de tip 3 se numete i clasa mulimilor regulate.

Exemplul 2 Fie G=({S,B}, {0,1}, S, P) unde

P:

0B

1SB

0BB

0BS

a) S se construiasc automatul finit, M, care s recunoasc L(G); b) Pornind de la M s se construiasc automatul finit determinist, M1,

echivalent cu M:

c) S se construiasc gramatica G care s genereze T(M1).

Construcie: a) Conform Teoremei 2.2.2, construim automatul finit care s recunoasc limbalul L(G), M =({S,B,A}, {0,1}, , S, {A}), unde:

(A,1){S}(B,1)(S,1)

(A,0)B}{A,(B,0){B}(S,0)

S reprezentm n figura urmtore diagrama tranziiilor din automatul

M =({S,B,A}, {0,1}, , S, {A}):

Start

Figura 2.2.3

S B

A

0

1 0

0

- 50 -

Este uor de verificat c T(M)=L(G) este limbajul cuvintelor peste alfabetul {0,1} care ncep i se termin cu o succesiune de cel puin doi 0 i orice apariie a simbolului 1 este urmt de succesiuni de 0.

b) Pornind de la M, s construim conform Teoremei 2.2.1, un automat finit determinist, M1, echivalent cu M:

) {[A]}[S],,{0,1},Q, (M1

B]}[A,[A],[B],{[S],Q (n Q nu sunt necesare i strile

B]A,[S,B],[S,A],[S, )

[S]B],1)([A,

A][B,B],0)([A,

([A],1)([A],0)

[S]([B],1)

A][B,([B],0)

([S],1)

[B]([S],0)

c) Pornind de la M1, construim G dup cum urmeaz (Teorema 2.2.3): G=( { S],[B],[A],[A,B]}, {0,1}, [S], P )

0B][A,, 1[S]B][A,, B]0[A,B][A,

0[B], 1[S][B], B]0[A,[B]

0[B][S]

:P

Observaia 2.2.2 Gramatica G este mult mai complicat dect gramatica G iniial, dei ele sunt echivalente i evident c dac pornim de la ea se poate construi un automat finit i mai complicat, echivalent cu automatele de mai sus.

Se pune atunci problema dac pornind de la un automat finit nu putem micora numrul de stri sau dac atunci cnd se implementeaz un automat finit nedeterminist se poate obine o reprezentare n memorie optimal. Aceast ultim problem este de mare importana in construcia compilatoarelor i este abordat n [12], [14]. n continuare nu vom ocupa de prima dintre aceste probleme, i anume de micorarea numrului de stri ale unui automat finit determinist.

1. Descriei un automat finit determinist pentru L = {w | w{0,1}*, w are un numr par de 0 i un numr impar de 1}

2. S se construiasc automatul finit care accept limbajul:

- 51 -

L = {0n1

m | n0, m1}{1n0m | n0, m1}

3. Scriei un automat finit determinist, echivalent cu automatul finit nedeterminist din figura de mai jos:

4. Fie automatul finit nedeterminist de mai jos:

S se transforme ntr-un automat finit determinist.

S ne reamintim... Un automat finit determinist, notat M=(Q, , , q0, F), este format din: Q - o mulime finit nevid (mulimea strilor); - un alfabet finit de intrare;

- o aplicaie numit funcie de tranziie, care ataeaz fiecrei combinaii o nou stare

QQ: ;

Qq0 starea iniial;

QF mulimea strilor finale.

Un automat finit nedeterminist, notat M=(Q, , ,q0, F), este format din Q, , q0, F prezentate n definiia 2.1.1, dar funcia de tranziie este aici

Q)(Q:' P .

Deci a)(q,' este o mulime de stri i nu o singur stare.


I. ntrebri. 1. Care este diferena esenial dintre un automat finit determinist i unul

nedeterminist?

2. Prezentai legatura dintre automate finite i gramatici.

II. Exerciii propuse. 1. Fie automatul nedeterminist de mai jos:

- 52 -

S se construiasc un automat finit determinist, A, echivalent cu

automatul dat i s se construiasc apoi o gramatic care s genereze

T(A).

2. Fie gramatica G=({A,B},{a,b},A, P), unde P = {AAa|aB, BBb|b}.

S se determine automatul finit (determinist sau nu) echivalent cu

gramatica G.

M2.U1.5 Rezumat

Unitatea de nvare prezint automatele finite deterministe i nedeterministe i la legatura cu limbajele de tip3, numite i limbaje regulate. S-au prezintat echivalena dintre automatele finite deterministe i cele nedeterministe precum i un algoritm de trecere de la un automat nedeterminist la unul determinist echivalent.

- 53 -

Unitatea de nvare M2.U2. Minimizarea automatului finit

Cuprins

M2.U2.1. Introducere............................................................................................ 53

M2.U2.2. Obiectivele unitii de nvare .............................................................. 53 M2.U2.3. Minimizarea automatului finit ............................................................... 53

M2.U2.4. Algoritmi pentru minimizarea automatului finit .................................... 57

M2.U2.5. Rezumat.....................................................................................................61


Prin trecerea de la un automat finit la o gramatic i apoi de la gramatic la un automat finit se obin n final automate echivalente, adic automate care recunosc acelai limbaj. Problema care se pune este de a vedea dac n mulime

limbaje formale si automate

Documents