LFA - Aplicatii

8/8/2019 LFA - Aplicatii

1/48

IRINA ATHANASIU

DIANA RAICIU RADU SION IRINA MOCANII

Universitatea "Politehnica" din BucuretiCatedra de Calculatoare

L I M B A J E FO R M A L E

i

AUTOMATE


2/48

MATRIX ROMCP. 16 - 162

77500 - BUCURETItel. 01.4113617, fax 01.4114280

e-mail: [email protected]

Descrierea CIP a Bibliotecii Naionale a Romniei

IV.

004.43

Limbaje formale i automate. ndrumar pentru aplicaii/ Irina Athanasiu,Diana Raiciu, Radu Sion, Irina Mocanu, Bucureti, Matrix Rom, 200298 pagini, 25 cmBibliogr.ISBN 973-685-407-8

Athanasiu, IrinaRaiciu, Diana

Sion, RaduMocanu, Irina

Despre autori,

Acest ndrumar are muli autori cu o contribuie secvenial. A nceput cu nite foiscrise de mn care conineau probleme i schie de rezolvri, a mai existat i un textintroductiv n lex n format electronic. n 1992 Diana Raiciu (n prezent Diana

Mrculescu, profesor n Department of Electrical and Computer Engineering dinUniversitatea Carnegie Mellon, SUA) a realizat prima form electronic a acestui ndrumar. Urmtorul autor (1999) a fost Radu Sion (n prezent doctorand ndepartamentul de calculatoare din Universitatea Purdue, SUA). A urmat n 2001doamna asistenta Irina Mocanu. Fiecare dintre autori a corectat textul anterior i amai adugat probleme noi. Cu fiecare nou autor textul prea c devine gata. Amhotrt s public textul n formatul curent care desigur este nc departe de ce puteas fie, pentru c se aniverseaz anul acesta 10 ani de cnd credeam c ndrumarul vafi foarte curnd gata de publicare.

Martie 2002 Irina Athanasiu

ISBN 973 - 685 - 407 - 8


3/48

1/ Elemente de teoria limbajelor formale

1.1 Gramatici1.1.1 Ierarhia Chomsky

Probleme1.1.2 Lema de pompare

Probleme1.1.3 Transformri asupra GIC

1.1.3.1 Eliminare recursivitate stnga1.1.3.2 Eliminare Xproducii1.1.3.3 Eliminare simboli neutilizai

1.1.3.4 Eliminare simboli inaccesibiliProbleme

1 2 Mulimi regulate. Expresii regulateProbleme

1.3 Acceptoare1.3.1 Automate finite

Probleme1.3.2 Automate cu stiv (push-down)

Probleme1.3.3 Maina Turing

Probleme

2 Lex - generator de analizoare lexicale2.1 Expresii regulate. Structura unei specificaii lex.

2.2 Elemente avansate2.2.1 Funcionarea analizorului lexical generat de lex2.2.2 Stri de start2.2.3 Macrodefiniii, funcii i variabile predefmite2.2.4 Fiiere de intrare multiple

2.3 Exemple comentate

3 Teme pentru acas

4 Bibliografie

2

2

34

161718181819

2020

2324

27272844455254

6566

707172

. : 73

.73

74

87

91


4/48

limbaje formale si translatoare Seminar LFA

1 Elemente de teoria limbajelor formale

Definiia 1.1. Se numete alfabetorice mulime finit T de simboli.Definiia 1.2. Se numete limbaj peste un alfabet Torice submulime a mulimii T*.

1.1 Gramatici

Definiia 1.1.1. O gramatic este un cvadruplu G = (N, T, P, S) unde:

N este o mulime finit de simboli numii simboli neterminali T este o mulime finit de simboli numii terminale ( N n T = 0) P este o submulime a mulimii (N u T)* N ( N u T)* x( N u T)* i reprezint mulimea

produciilor gramaticii G. Un element p e P , p = (a,P) se reprezint sub forma: oc ->p S e N se numete simbolul de start al gramaticii

Definiia 1.1.2. Se numete form propoziional n gramatica G orice ir din (N u T)*obinut prin aplicarea recursiv a urmtoarelor reguli:

1. S este o form propoziional;

2. Dac ocpy este o form propoziional i exist o producie p -> 8 atunci i a5y este oform propoziional.

Definiia 1.1.3. Se numete propoziie generat de gramatica Go form propoziional n Gcare conine numai terminale.

Definiia 1.1.4. Se spune c ntre dou forme propoziionale a i p n gramatica G existrelaia de derivare notat cu a =>p dac exist dou iruri wl, w2 i o producie y > 8 astfel

nct a = wlyw2 i P = wl8w2. Se spune c ntre formele propoziionale a i P exist relaia dederivare notat a =>k P dac exist formele propoziionale 80, Si, 82,..., k astfel nct a = 80 =>81 =>... =>8k = p. nchiderea tranzitiv a relaiei de derivare se noteaz cu =>"*

Definiia 1.1.5. Fie G o gramatic. Se numete limbaj generat de gramatic Gi se noteazL(G) mulimea propoziiilor generate de G. Altfel spus:

L(G)={weT* |S=>"ww}

Definiia 1.1.6. Dou gramatici Gl, G2 se numesc echivalente dac genereaz acelai limbajadic L(G1) = L(G2).


1.1.1 Ierarhia Chomsky

Gramaticile pot s fie clasificate conform complexitii produciilor n urmtoarea ierarhie: gramatici de tip 0 (fr restricii) - au produciile de forma:a - P cu a e (N u T)* N (N u T)* , P e (N u T)* gramatici de tip 1 (dependente de context - GDC) - au produciile de forma:a A P - >a yp , a, P e ( N u T)*, A e N, y e (N U T)+

sau de formaS -> k.

n al doilea caz S nu apare n membrul drept al nici unei producii. gramatici de tip 2 (independente de context - GIC) au produciile de forma:

A - ^ a , A s N , a e ( N U T)*. gramatici de tip 3 (regulate la dreapta - GR) - au produciile de forma:

A-H>ocBcuAeN,Be(Nu {A,}) i a e T*.Corespunztor mulimii gramaticilor G[k], k = 0 ,1 , 2, 3 exist mulimea L[k] care reprezint

mulimea limbajelor ce pot fi generate de o gramatic din G[k]. L[0] este mulimea limbajelorgenerale care pot fi generate de o gramatic de tip 0 (fr restricii), L[l] este mulimealimbajelor dependente de context (generate de o GDC), L[2] mulimea limbajelor independentede context (generate de o GIC), iar L[3] mulimea limbajelor regulate (generate de o GR). Sepoate arta c are loc incluziunea:

L [ 3] c L [ 2] c L [ l ] c L [ 0] .

Termenul de "dependent de context" provine din faptul c producia ocAp > ayP, poate sfie interpretat ca - neterminalul A poate s fie nlocuit cu irul y doar n contextul dat deirurile a i p. Similar termenul "independent de context" provine din faptul c o producie deforma A > a se poate interpreta ca - neterminalul A poate s fie nlocuit cu irul a indiferent decontext (indiferent de simbolii ntre care apare).

Se observ c ntr-o gramatic independent de context prin aplicarea unei producii deform A a asupra unei forme propoziionale, lungimea acesteia poate s devin mai mic(dac a este irul vid), egal (dac a este un terminal sau neterminal) sau mai mare (dac a esteun ir de lungime mai mare dect 1). Acest lucru nu este valabil pentru gramaticile dependentede context unde lungimea unei forme propoziionale n urma aplicrii unei producii de forma

a A P - > a y P , a , P ( N u T)*, A e N, y e (N U T)+

devine mai mare (dac y este un ir de lungime mai mare dect 1), cel mult egal (dac y esteun ir format dintr-un neterminal sau un terminal). Prin urmare, nu este evident c oricegramatic independent de context este i dependent de context. Se poate demonstra c pentruorice gramatic independent de context exist o alt gramatic independent de contextechivalent obinut prin transformri, astfel nct modul de cretere a lungimii formelorpropoziionale s fie similar cu cea a gramaticilor dependente de context.

Intuitiv, o caracterizare a gramaticilor de mai sus poate fi fcut din punctul de vedere al"numrrii" simbolilor. Astfel, gramaticile regulate pot "numra" pn la o limita finit. Deexemplu, limbajul specificat prin L = { 0 T | 0 < i < 5 } poate fi generat de o gramatic regulata

3


5/48


G astfel: S-> 0000011111 | 00001111 | 000111 | 0011 | 01 | XDe asemenea, o gramatic independent de context poate pstra un singur contor (limita nu

este cunoscut sau fixat). De exemplu, limbajul L = { 0T j n > 0 } poate s fie generat degramatic independent de context G = ({ S }, {0, 1}, P, S) unde P = { S - OS 1 | X }.

Probleme

S se construiasc gramaticile care genereaz urmtoarele limbaje:

proHeiTu 1.1-1

: L={a nb n jn > 0}

Soluie:

i Orice ir nevid w e L ncepe cu simbolul a i se termin cu simbolul b, astfel nct poate s! fie scris sub forma w = a x b unde x este un ir de terminale care fie este vid, fie este de; aceeai form cu irul w. Prin urmare o gramatic G care genereaz limbajul L poate s fie:: G = ({ S }, { a, b }, P, S) unde: P = { S- a S b | X}.

Verificare:\ Pentru irul vid (X) secvena de derivri este S => L Pentru irul aaabbb secvena de derivri

es te S ;=> aS b => aaS b b => aaaS b b b => aaab b bComentarii:

Gramatica G este independent de context. Se poate arta c n acest caz nu se poate construio gramatic regulat care s genereze acelai limbaj, adic s fie echivalent cu prima.

L = { anbn i n > 0 }

Soluie:Orice ir nevid w e L ncepe cu simbolul a i se termin cu simbolul b, astfel nct poate sfie scris sub forma w = a x b unde x este un ir de terminale care fie este irul ab (n > 0, nu se

accept irul vid), fie este de aceeai form cu irul w. Prin urmare o gramatic G caregenereaz limbajul L poate s fie: G = ({ S }, { a, b}, P, S) unde: P = { S-> a S b | ab }.

VerificateiPentru irul aaabbb secvena de derivri este S =>a Sb =a aSb b= >aa ab bb

Comentarii: . . . . . . . . -Gramatica G este independent de context

limbaje formale si translatoar e Seminar LFA

problem l.-3

L = {a nb n c m d m jn>l im>l }

Soluie:Observm c pentru orice ir w din L exist dou subiruri independente wl = anbn respectiv

w2 = cradm care pot fi generate separat. Vom utiliza dou neterminale A,B pentru generarea: celor dou subiruri independente wl i w2. Primul subir ncepe ntotdeauna cu a i se termin cu b, adic wl = anbn se poate scrie sub forma wl = a v b cu v un ir care este de: aceeai form cu wl, i va fi generat n acelai mod, sau este irul vid. n mod analog,

subirul w2 = cmdm poate fi generat astfel: w2 ncepe n mod sigur cu simbolul c i se; termin cu simbolul d. Prin urmare, w2 se poate scrie w2 = c v d, unde v este de aceeai

form cu w2 sau este irul vid. Astfel, mulimea produciilor va conine producii de forma:; A - aAb | ab i B -> cBd | cd. Pentru concatenarea celor dou subiruri, vom introduceproducia S - AB. Prin urmare o gramatic care genereaz limbajul L este: G = ({ S, A, B },

i { a, b, c, d }, P, S) unde: P = { S->AB, A-aAb | ab, B ->cBd | cd }.

Verificare;

Pentru irurile a b c c d d (n = 1 i m = 2), respectiv a a b b c d (n = 2 i m = 1) se obinurmtoarele secvene de derivri: S=> A B=> a b B=> a b c B d=> a b c c d d respectiv S=> AB=> aAb B=>a a b b B=>a a b b c d.

Comentarii:Gramatica G este independent de context

* problema-4,1^- ' "_ ^>l\:-\'-f"f%V--/./T':T.''ij"-j~V.""''"''*'i"--"---"t^". 0 i m > 0 }

Soluie:

Observm c pentru orice ir w din L exist dou subiruri independente wl = a nbn respectiv: w2 = c

mdm care pot fi generate separat. Vom utiliza dou neterminale A,B pentru generarea ,; celor dou subiruri independente wl i w2. Primul subir ncepe ntotdeauna cu a i se; termin cu b, deci wl = a nbn se poate scrie sub forma wl = a v b cu v un ir care este de

; aceeai form cu wl, i va fi generat n acelai mod; deoarece n > 0wl poate fi i irul vid.: In mod analog, subirul w2 = c

mdm poate fi generat astfel: w2 ncepe n mod sigur cusimbolul c i se termin cu simbolul d. Prin urmare, w2 se poate scrie w2 = c v d, unde v este

: de aceeai form cu w2; deoarece m > 0 w2 poate fi i irul vid. Astfel, mulimea> produciilor va conine producii de forma: A -> aAb | Xi B - cBd | X. Pentru concatenarea

celor dou subiruri, vom introduce producia S - AB. Prin urmare o gramatic care; genereaz limbajul L este: G = ({ S, A, B }, { a, b, c, d }, P, S) unde: P = { S->AB, A->aAb |AB

Verificare:Pentru irurile a b (n = 1 i m = 0), respectiv c d (n = 0 i m = 1) se obin urmtoarelesecvene de derivri: S=> AB=>aA b B=>a b B =>ab i S=> A B=> B=> c B d => cd .


6/48

limbaje formale si translato are .. . . Seminar LFA

problema 1.1-5

L = { anbmcmdn | n > 1 i m y 1 }

Soluie:Orice ir w din L ncepe cu simbolul a, i se termin cu simbolul d. w se poate scrie ca w = au d unde u este un ir care fie este de tipul celui din mulimea L, fie este de forma b mcm, m >1. Acesta din urm se poate scrie sub forma b v c cu v de aceeai form sau v este irul vid.

Astfel, innd seama de observaiile anterioare, o gramatic ce genereaz limbajul L este: G =

({ S, A-}, { a, b, c, d }, P, S) unde P= {S -* aS d| aA d, A- >- bA c| bc }.


Verificare:

Pentru irul a a b c d d ( n = 2 i m = l ) s e obine urmtoarea secven de derivri:d=> a a A d d=> a a b c d d.

a S

Comentarii:Se observ c neterminalul A este utilizat pentru a genera subiruri de forma b mcm.Gramatica G este independent de context.

problema 1.1-6

L = {w e { 0,1 }* | w conine un numr egal de 0 i 1 }

Soluie:

Fie w un ir oarecare astfel nct w e { 0, 1 }* i #0(w) = #,(w) unde prin #a(w) am notatnumrul de apariii ale simbolului a n irul w. Dac w ncepe cu simbolul 0, atunci exist ui v, u,v e { 0, 1 }* cu u i v avnd fiecare un numr egal de 0 i 1 (eventual zero) astfel

nct irul w se poate scrie w = 0 u 1 v, cu u, v e { 0,1 }* cu numr egal de 0 i 1 astfel nct w = 0 u 1 v. Producia care genereaz acest tip de iruri este: S -> 0 S 1 S. De asemenea,dac w e L ncepe cu 1, se arat n mod analog c w se poate scrie w = l u 0 v c u u , v iruricu numr egal de 0 i 1. Pe baza celor de mai sus, rezult c o gramatic care genereazlimbajul L este G = ({ S }, { 0, 1 }, P, S) unde: P={S->OS1S|1SOS|A.}.

Verificare:

Pentru irul 0 1 0 1 1 0, se obine urmtoarea secven de derivri: S => 0 S 1 Sl S = > 0 1 0 S l S = ^ 0 1 0 1 S = ^ 0 1 0 1 1 S O S = > b l 0 1 1 0 S = * 0 1 0 1 1 0 .

Comentarii:

Gramatica G este o gramatic de independent de context.

problema 1.1.-7 _ ! ..

L = { w e { 0, 1 }* | w nu conine subirul 011 }

01 SOS

Soluie:Presupunem c parcurgem un ir din limbajul L ncepnd cu simbolul cel mai din stnga. Seobserv c pot s existe mai multe situaii n ceea ce privete simbolul curent:1 Simbolul curent este 1 i cel anterior a fost tot 1. Atta timp ct simbolul curent este 1 nusuntem la un nceput al unui sub ir de forma 011.2. Simbolul analizat este 0 adic suntem la nceputul unei posibile secvene 011 care trebuierejectat. Atta timp ct simbolul curent este 0 este aceai situaie. Dac simbolul curent este1 se trece n situaia urmtoare (3).3. Simbolul curent este 1 i cel precedent a fost 0, adic suntem n interiorul unei posibilesecvene 011 care trebuie rejectat. De aici, singurul simbol posibil este 0 (1 ar genera

secvena 011), care ar putea s nceap o nou posibila secven 011. Ca urmare, pentru unsimbol 1 suntem n situaia 2.

Vom codifica cele trei situaii posibile prin neterminalele S, A, B. Corespunztor celor demai sus o gramatic G care genereaz limbajul L este: G = ({ S, A, B }, { 0,1 }, P, S), P = {S -> S | 0A |X,A - 0A11B |X,B - 0A | X}.

Verificare:Pentru irurile: 10 1, respectiv 0 10 1, secvenele de derivri sunt: S=> 1 S=> 1 0 A=> 10 1B=> 1 01 iS=> 0 A=> 0 1 B=> 01 0A=> 0 1 01 B=> 0 1 0 1.

Comentarii:Gramatic G este regulat, iar limbajul L este de un limbaj regulat.

p i c h k - i i s . i I . l - K

L = { w 6 { 0 , l } * |w| divizibil cu 3 }

Soluie: Vom presupune c parcurgem irul w de la stnga la dreapta considernd un prefix alacestuia: w = u a v unde u este prefixul, a este simbolul curent (0 sau 1), iar v este restulirului (u, v e { 0,1 }*). Sunt posibile urmtoarele situaii:1. Numrul de simboli din prefixul u este de forma 3 *n, n e N2. Numrul de simboli din prefixul u este de forma 3*n + 13. Numrul de simboli din prefixul u este de forma 3*n+2

Asociem neterminalul S primei stri (care este de altfel cea corespunztoare generrii unuiir din limbajul L), iar celorlalte dou stri neterminalele A, respectiv B. Din prima stare se

trece n a doua dup ce se "citete" simbolul curent (numrul de simboli citii devine 3*n+l),iar de aici, dup "citirea" unui nou simbol, se trece n starea 3 i apoi din nou n starea 1 dup"citirea" urmtorului simbol din ir, etc. Gramatica care genereaz limbajul L este: G = ({ S,

A, B }, { 0,1 }, p, S) unde P = { S - 0A | IA | X, A -> 0B 11B, B -> OS | S }.

Verificare:

Pentru irul 010011, se obine secvena de derivri S=> 0A=> 01B=> 010S=> 0100A=>01001B=> 010011S=> 010011.

Comentarii:Alt gramatic regulat echivalent este Gl = ({ S }, { 0, 1 }, P, S) unde: P= { S - > 0 0 0 S |0 0 1 S 10 1 0 S I 0 1 1 S I 1 0 0 S | 1 0 1 S11 1 0 S11 1 1 S | X}.


7/48

limbaje formale si translatoare

l'rnliluii.i I l-'>

Seminar LFA

Soluie:

irurile din L pot fi de dou tipuri: cu i > j, respectiv i < j. Astfel, un ir w e L poate fi scrisfie sub forma w = 0)0nlJ dac i > j i n = i - j, fie sub forma w = OTl' dac i < j i n = j - i.n ambele cazuri, n > 0. Pentru generarea primului ir, vom observa c acesta ncepe cu 0 i

; se termin cu 1 i poate fi scris sub forma w = 0 u 1 unde u este fie de aceeai form, fie deform 0", cu n > 0. n mod analog, cel de-al doilea ir ncepe cu 0 i se termin cu 1 i poatei fi scris sub form w = 0 u 1 unde u este fie un ir de aceeai form, fie de forma 1", cu n > 0.i innd cont de observaiile de mai sus, o gramatic ce genereaz limbajul L este G = ({ S, A,|B}, {0,1 },P,S)undeP={S-0Sl|0A|lB,A->0A|A.,B-> IB | A.}.

Verificare:

Pentru irul 0 0 0 1 se obine urmtoarea secven de derivri: S => 0 S 1 ==> 0 0 A 1=> 0 00 A l = > 0 0 0 1 .

Comentarii:

G este o gramatic independent de context.

Problema 1.1-10

L = { xmyn | n < m sau 2*m < n, n, m > 1 }Soluie:

Limbajul L conine dou tipuri de iruri: iruri de forma xmyn cu 2*m < n, respectiv cu n < m., Primul tip de ir poate s fie scris sub forma xrayry2*m unde n = 2 * m + r, cu r > 0 i m > 1: iar pentru generarea lui pot s fie utilizate produciile: Sj -> xA yy , A- > x A y y | y C i Ci -> y C | A. Al doilea tip de ir poate s fie scris sub forma xnxty" unde m = n + rc u r >0 i n

> 1. Pentru generarea acestui ir se pot utiliza produciile: S2 -> x B y, B -> x B y | x D, D; -> x D | X. Prin urmare, o gramatic care genereaz limbajul L este: G = ({ S, Si, S 2, A, B, C,\ D }, { x, y }, P, S) unde P = { S -> Si | S 2, S, -> x A y y, A - x A y y | y C, S 2 - x B y, B

-> xB y[ xD , C -> y C | A, D -> x D | A }.

Verificare:

Pentru irul x x x y y (pentru care m = 3 i n = 2, adic m > n) se obine secvena de derivri:s = * S2=> x B y=> xx B yy=>x x x D y y=> x x x y y. Fie irul x x y y y y y (pentru care m =2 i n = 5 adic 2 * m< n). Pentru acest ir se obine secvena de derivri: S=> Si=> x A y y=>x x A y y y y=> xxyC yyy y= >x xy yy yy .

Comentarii:

G este o gramatic independent de context

limbaje formale si translato are Seminar LFA

pinlil'.lll.l 1.1-l 1

L = { ambncpdq | m + n = p + q , m, n, p, q > 0 }

Soluie:Relaia din enun poate fi scris sub forma m - q = p - n. Pot apare dou cazuri:1 m > q- Notm r = m - q = p- n , unde r > 0 i m = q + r & p = n + r. Fie LI limbajul

generat n acest caz. Atunci LI poate fi descris prin: LI = { aqarbncncrdq | n,q > 0, r > 0

}.Orice ir de aceasta form, poate s fie scris ca w = a u d unde u este de aceeai formcu w sau de forma a rbncncr i n acest caz poate fi scris sub forma: u = a v c unde v estefie de aceeai form cu u, fie este de forma bncn. n acest caz, v poate fi scris sub form v= b z c unde irul z este de aceeai form cu v, fie irul vid. Prin urmare, vor fi utilizateproduciile: S -> aSd | A, A -> aAc | B, B - bBc | A

2. m 0 i prin urmare n = p + r & q = m + r. Fie L2limbajul generat n acest caz. Prin urmare L2 = {ambrbpcpdrdm | m, p>0, r>0}.Un ir |oarecare w eL2, poate fi scris sub form w = a u d, unde u este de aceeai form cu w, jsau w este de form brbpcpdr i n acest caz u fie se poate scrie sub forma u - b v . d c u v ;un ir de aceeai form cu u, sau u este de forma x = bpcp. irul nou obinut poate fi ;generat observnd c se poate scrie sub forma x = b z c unde z este un ir de aceeai '

I form cu x. Pot s fie utilizate, produciile: S - aSd | bCd, C - bCd | D, D -> bDc | X. \

Se observ c L = LI u L2 i c cele dou neterminale B i D se comport la fel (adic igenereaz acelai limbaj), i putem renuna la neterminalul D. |Prin urmare, o gramatic G care genereaz limbajul L este: G = ({ S, A, B, C }, { a, b, c, d }, jP, S) unde P = { S -> aSd | A | bCd, A - aAc | B, B -> bBc | X, C H> bCd | B }.

Verificare:

Vom considera dou exemple de derivare: a a b c c c (cazul m > q), respectiv a b b c d d! (cazul m < q). Pentru irul a a b c c c se obine secvena de derivri: S => A=>a A c=> a a ; A c c=> a a B c c=> a a b B c c c = > a a b c c c , respectiv pentru cel de-al doilea ir: S=> a S |

G este o gramatic independent de context.

Problema li-42-7 "1 * ;" ' < *f.'

: L={amb n |n 0, q > 0. Prin urmare, n = p + qim = 2 * p + i

: q i limbajul poate fi scris sub forma: L = { a2*paqbqbp | p, q > 0 } :; Un ir care aparine acestui limbaj, poate s fie scris sub forma wl = a a u b unde u este de ;: aceeai form cu wl sau de form aqbq. j

irul aqbq poate s fie generat n mod asemntor lui wl, observnd c poate s fie scris sub i1 forma w2 = a v b unde v este de aceeai form cu w2 sau este irul ab. Prin urmare o[gramaticaeste G = ({ S, A }, { a, b }, P, S)unde P = { S -> aaSb | aaAb, A - aAbij ab}


8/48

limbaje formale si translatoare Seminar LFA limbaje formale si translatoare Seminar LFA

Verificare:Fie irul: a a a b b (n = 2, m = 3). irul poate s fie obinut utiliznd urmtoarea secven dederivri: S=> a a A b=> a a a b b.

Comentarii:. G este o gramatic, independent de context

IMLIII.I I.! 15

problema 1.1-13

L = { wcwR | w e {a,b}* } unde prin u = wR am notat irul care are proprietatea u, = wn.i+ipentru orice i = 1, 2,..., n unde n = |wj = |u| i w = wi w 2... wn, u = ui U2... un (irul reflectatcorespunztor lui w).

Soluie:

Orice ir din limbajul I, are proprietatea c ncepe i se termin cu acelai simbol sau estedoar simbolul c. n primul caz irul poate s fie scris sub forma w = x u x unde x e { a, b },iar u are aceeai proprietate ca w. Lund n considerare cele de mai sus, gramatica G caregenereaz limbajul L este G = ({ S }, { a, b, c }, P, S) unde P = { S -> aSa | bSb | c }. ntr-adevr, orice ir u generat de G are proprietatea c exist w e {a,b}* astfel nct u = wcwR ipentru orice ir u e L, exist o derivare S =*> u.

Verificare:Pentru irul a b a c a b a, se obine urmtoarea secven de derivri: S => a S a:= > a b a S b a b a = > a b a c a b a

Comentarii:G este o gramatic independent de context

a b S b a

problema 1.1-14

L = {we {a ,b}* w = wR}

Soluie:

Un ir w care respect condiia de mai sus poate s aib una din urmtoarele forme: vvR,vavR, vbvR unde v e { a, b }* este un ir oarecare. Pentru a genera aceste iruri, putem sutilizm gramatica G = ({ S }, { a, b }, P, S) cu P = { S -> aSa | bSb | a | b | X}.

Verificare:

F i e ir u l a b a a b a a b a . P e n tr u o b in e r e a a c e s tu i i r p u t e m s c o n s id e r m u r m t o a r e as e c v e n d e d e r i v r i : S = > a S a = > a b S b a = > a b a S a b a = > a b a a S a a b a = > a b a a

b a a b a.Comentarii: . , .


L=Soluie:

Orice ir nevid w e L conine la nceputul irului toate simbolurile a, dup care urmeaztoate simbolurile b i se termin cu simbolurile c. Pentru a genera toate a-urile se va folosineterminalul Si, pentru a genera toate b-urile se va folosi neterminalul S 2, iar pentru a generatoate c-urile se va folosi neterminalul S3. Prin urmare, gramatica G care genereaz limbajul Lpoate s fie: G = ({ S, S,, S 2, S3 }, { a, b, c }, P, S) unde: P = {S-> S,S 2S3, S, - a S, | a, S2- >bS 2 |b, S 3 - > c S 3 | c } .

] erificare:Fie irul aabbbcccc. Pentru obinerea acestui ir putem s considerm urmtoarea secven dederivri: S=> SiS2S3=> a SiS2S3 => a a S2S3 => a a b S2S3=> a a b b S2S3 => a a b b b S3=> a a ;

b b c S 3 = > a a b b c c S 3 = > a a b b c c c S 3 = > a a b b b c c c c :

Comentarii:

G este o gramatic independent de context ,

problema 1.1-16

L = {aVck\ i # j s a u j # c , i , j , k > 0 } i

Soluie:

Pot apare 4 cazuri:', 1. Dac i < j, notm p = j - I, rezult j = p + i, p > 0. Fie LI limbajul generat n acest caz. j: Atunci LI poate fi descris prin: LI = { aibibpck | p > 0, i, k > 0 }. Vom folosi jI netermmalul S1 pentru generarea subirului aibi, pentru a genera subirul bp se va folosi |: neterminalul S2, iar pentru a genera subirul ck se va folosi neterminalul S3. Prin urmare |: vor fi utilizate produciile S - SI S2 S3, SI - a SI b | a b, S2 - b S2 j b,.S3 -> c S3 '| j

c. i

: 2. Dac i > j, notm p = i - j, rezult i = p + j, p > 0. Fie L2 limbajul generat n acest caz. :: Atunci L2 poate fi descris prin: L2 = { a'VbV | p > 0, j, k > 0 }. Vom folosi neterminalul j; Si pentru generarea subirului ap, pentru a genera subirul a'b' se va folosi neterminalul ;i S2, iar pentru a genera subirul ck se va folosi neterminalul S3. Prin urmare vor fi utilizate j

produciile S ^ Si S2 S3, SI - a S, | a, S 2- aS 2 b | ab, S3 - > c S 3 |c . j

: 3. Dac j < k, notm p = k - j, adic k = j + p, p > 0. Fie L3 limbajul generat n acest caz. j; Atunci L3 poate fi descris prin: L3 = { aWc15 1 p > 0, i,j > 0 }. Vom folosi neterminalul j

Sj pentru generarea subirului a1, pentru a genera subirul bV se va folosi neterminalul jS2, iar pentru a genera subirul c

p se va folosi neterminalul S3. Prin urmare vor fi utilizate j... .produciile S- Si S 2S3, Si-ai |a, S 2 - b S 2 c |bc , S 3 - ^cS 3 |c. I

10 10 11


9/48


: 4. Dac j > k, notm p = j - k, i j = p + k, p > 0. Fie L4 limbajul generat n acest caz AtunciL4 poate fi descris prin: L4 = { a'b pbkck | p > 0, i, k > 0 }. Vom folosi neterminalul Sipentru generarea subirului a', pentru a genera subirul bp se va folosi neterminalul S2, iarpentru a genera subirul bkck se va folosi neterminalul S3. Prin urmare vor fi utilizate

i produciile S - S, S2 S3, S, -* a Si | a, S2 -> b S21 b, S3 - b S3 c | b c.

: Corespunztor celor 4 cazuri notm neterminalele Si, S2, S 3 cu Sia, S]b, Si c, S !d , S 2a, S 2b, S2c,: S2d, S 3a, S3b, S4c, S3d. Prin urmare gramatica ce genereaz limbajul este: G = ({ S, Si a, S2a,

S3a, S,b, S2b, S 3b , S,c> S2c, S 3c , Sid, S2d, S3d }, { a, b, c }, P, S) unde: P = { S- Si aS2aS3a |

SibS2bS3b | Si cS2c S3c j Si dS2dS3d, Sia > a Sja b | a b, S2a >b S2a | b, S3a c S3a | c , Sjb > aSib | a, S2b -> a S2b b | a b, S 3b -c S 3b | c, Sic -> a Sic | a , S 2c -> b S2c c | b c, S3c -c S 3c |c, Sid -> a Sid | a, S2d -> b S2d | b, S 3d H> b S3d c | b c }.


L={a ibjc k| i0}

Notm p = j - i, adic j = i + p, p > 0. Atunci L poate fi descris prin: L = { a'b'bp

ck

j p>0, i, k: > 0 }. Vom folosi neterminalul A pentru generarea subirului a'b1, pentru a genera subirul bp

se va folosi neterminalul B, iar pentru a genera subirul c k se va folosi neterminalul C. Prinurmare, gramatica G care genereaz limbajul L poate s fie: G = ({ S, A, B, C }, { a, b, c },

j P, S) unde: P = { S->ABC, A -> a A b | A,, B -> b B | b, C -> c C | A.}.

; G este o gramatic independent de context '

; L = { a ib i c k| i+ j= k , i , j , k >0 }

Dac k = i + j atunci L poate fi descris prin: L = { a'Wc'c' | i, j > 0 }. Orice ir w din limbajncepe cu simbolul a, i se termin cu simbolul c. Deci, w se poate scrie ca w = a u c unde u

; este un ir care fie este de tipul celui din mulimea L, fie este de forma Vd, j > 0 . Acesta dini urm se poate scrie sub forma b v c cu v de aceeai form sau v este irul bc. Prin urmare: gramatica G care genereaz limbajul L poate s fie: G = ({ S, A }, { a, b, c }, P, S) unde: P =

{ S n > a S c | a A c , A - > b A c | b c } .

; G este o gramatic independent de context

1.1-1")

I \\ I MI

Soluie:

Vom presupune c pai curgem .-.irul \\ de la ainga ia Jivapia considernd un prefix alacestuia: w = u a v unde u este prefixul, a este simbolul curent (a sau b), iar v este restulirului (u, v { a, b }*). Sunt posibile urmtoarele situaii:1. Numrul de simboli a din prefixul u este par

: 2. Numrul de simboli a din prefixul u este impar; Asociem neterminalul S primei stri (care este de altfel ceea corespunztoare generrii unui

ir din limbajul L), iar celeilalte stri neterminalul A. Din prima stare se trece n a doua dac: simbolul curent a fost un a i se rmne n starea S dac simbolul curent a fost un b. Din

starea A se trece n starea S dac simbolul curent a fost un a i se rmne n starea A dacsimbolul curent a fost un b. Deci gramatica care genereaz limbajul L este: G =.({ S, A }, { ia , b } , P , S ) u n d e P = { S - > a A | b S | / , A ^ b A | a S } .

Comentarii:

G este o gramatic regulat

j i i u i i l i i n . i 1 . 1 IU ; " - - "- -

L = { w e { a , b } * | # a (w) = 2*#b ( w) }Soluie:

Pentru a genera irurile din limbaj de cte ori apare un simbol b trebuie sa apar doi simbolia. Nu este important ordinea n care apar simbolii. Deci gramatica care genereaz limbajul Leste: G = ({ S }, { a, b }, P, S) unde P = {S -> aS aS bS |a Sb Sa S| bS aS aS | ,} .


Limbajul parantezelor bine formate

Soluie:

Gramatica care genereaz limbajul L este: G = ({ S },{(,)}, P, S) unde P = { S -> S S | (S )!()} sau G = ({ S },{(, )}, P, S) unde P = { S ^ S S | ( S ) | X } dac este acceptat irul vid.


12 12*13



10/48


problema 1.1-22

L={ wwjwe {0, 1 }* }

Soluie:

Analiznd forma general a irurilor ce fac parte din limbajul L se observ c n generarea: acestor iruri este necesar " memorarea " primei jumti a irurilor pe msur ce se face: aceast generare, pentru a putea utiliza apoi informaia memorat n generarea celei de-a

: doua jumti a irului. n mod evident, aceast "memorare" nu se poate realiza utilizndi mecanismele oferite de gramaticile regulate sau independente de context. Am vzut c se pot: genera iruri de form w / c u ajutorul unor gramatici independente de context.; Vom genera un ir n care unui simbol 1 din prima jumtate a irului i va corespunde un, simbol notat U n a doua jumtate a irului. n mod corespunztor, unui simbol 0 din prima; jumtate a irului i va corespunde un simbol notat Z n a doua jumtate a irului. Pentru a: marca sfritul irului vom utiliza un neterminal B. Se observ c n acest mod s-a memorat

j prima jumtate a irului ntr-o form inversat. n continuare, din modul n care se utilizeazurmtoarele derivri ar trebui s rezulte i restul irului. Astfel, transformrile pe care le vom

i opera asupra unui ir generat ca mai sus, pot s fie exprimate n termeni intuitivi astfel: orice, Z sau U se transform n 0, respectiv 1 dac sunt urmate de terminatorul B, iar orice simbol 0': sau 1 se deplaseaz ctre captul din stnga, respectiv orice simbol Z sau U se deplaseaz: ctre dreapta (pentru a ajunge la terminatorul B).I De exemplu: 001UZZB => 001UZ0B => 001UOZB => 001U00B =>0010U0B => 00100UB! => 001001B => 001001. Astfel, mulimea produciilor gramaticii va conine S ->A B cu| neterminalul A utilizat pentru crearea unui ir de forma w t w2 unde wi e { 0, 1 }*, w2 e { U,; Z}*, iar ntre wi i w 2 exist relaia: wi = w2

Rn care U = 1, Z = 0.; Acest ir este generat prin produciile: A -> 0 A Z | 1 A U | X. Pentru generarea limbajului L\ mai sunt necesare produciile care realizeaz nlocuirea neterminalelor U, Z cu 1, respectiv 0'. dac sunt urmate de neterminalul B i dubla deplasare a simbolilor: Z B -> 0 B, U B -> 1 B,: Z 0 -> 0 Z, U 0 - 0 U, Z 1 -> 1 Z, U 1 -> 1 U. De asemenea, este necesar producia B - A.pentru a elimina simbolul utilizat ca terminator. Deci o gramatic G care genereaz limbajul

; L este G = ( { S, A, B, U, Z }, { 0, 1 }, P, S) unde: P={S^AB,A->OAZ|1AU|A.,ZB - > 0 B , U B - > l B , Z 0 - 0 Z , U 0 - > 0 U , Z l - > l Z , U l - > l U , B - > A . } .

' criticare:

Pentru irul 0 1 0 1 se obine irul de derivri: S=>AB:ZB= >01 U0B =>0 10U B=> 01 0 1 B => 0101

0AZB=>0 1AUZB=>0

Comentarii: :Se observ c G este o gramatic de tip 0 (tar restricii).Dac se utilizeaz producia B -* l ntr-un ir de derivri naintea transformrii tuturorneterminalelor U i Z, se poate obine o form propoziional din care nu se mai poate obineun ir din limbajul L.

De exemplu: S => AB =>0AZB => 0AZ i nu mai exist nici o producie care s poat s fieaplicat. Din forma propoziional obinut nu se mai poate obine un ir care s aparinlimbajului L. Astfel de rezultate in de aspectul nedeterminist al gramaticii respective.

1.1-23

L={anbV|n>l}

Soluie:

Problema poate s fie abordat ntr-o manier similar cu cea anterioar adic sememoreaz" prima parte a irului (an), ns generarea nu poate continua verificnd c existun numr corespunztor de simboli b i de simboli c. Prin urmare, va trebui s memorm"prima parte a irului (a11) i apoi s generm acelai numr de perechi de forma (BC) unde B,C sunt neterminale asociate cu terminalele b, c. n continuare, din derivrile ulterioare, varezultatransformarea celei de-a doua pri a irului n irul bncn. Vom considera deci, irurile deforma an(BC)n unde B,C sunt neterminale prin intermediul crora se va face generareasubirului bncn. Pentru aceasta este necesar substituia oricrui subir de forma CB cu irulBC, respectiv nlocuirea neterminalelor B,C cu b, respectiv c. Astfel, o gramatic G caregenereaz limbajul L este G = ({ S, B, C }, { a, b, c }, P, S) unde: P = { S- aSBC | abC, CB-> BC , bB - bb, bC ->' bc, cB -> Bc, cC -> ce }.

Verificare:

Pentru irul a3b3c3 de exemplu, se obine irul de derivri: S= > a SB C = > a a S B C B C = >a a a b C B C B C = > a a a b B C C B C = > a a a b B C B C C = > a a a b B B C C C = > a a a b

b B C C C = > a a a b b b C C C = > a a a b b b c C C=> a a a b b b c c C=> a a a b b b c c c =a 3b 3c 3.

Comentarii:G este o gramatic fr restricii

1.1-24

! L = {a mb n c m d n |m,n>l}

Soluie:

Vom genera nti forme propoziionale de tipul ambnDnCm unde C, D sunt neterminaleasociate terminalelor c, d. ntr-adevr, o form propoziional ca mai sus poate fi generat deproduciile: S->aSCjaAC,A->bAD|bD.Urmtorul pas este deplasarea simultan a simbolilor C spre stnga i respectiv D spredreapta, nlocuirea cu terminalele corespunztoare c, d fcndu-se de la stnga la dreapta: DC-> CD, bC -> bc, cC - ce, cD -> cd, dC -> Cd, dD -> dd. Astfel, o gramatic G caregenereaz limbajul L este G = ({ S, A, C, D }, { a, b, c, d }, P, S) unde: P = { S H > a S C | a

AQ A -> b AD | b D, DC -> CD , bC -> bc, cC -> ce, cD-> cd, dC -> Cd, dD -> dd }.

14 1415

1


11/48

limbaje formale si translatoare Seminar LFA 1Verificare:

Pentru irul a2b3c2d3 se obine urmtoarea secven de derivri: S => aSC =?>a aA CC=> aa b A D C C = > a a b b A D D C C = * a a b b b D D D C C = > a a b b b D D C D C = > a a b b bD C D D C = > a a b b b C D D D C = > a a b b b c D D D C = > a a b b b c D D C D = ^ a a b b

b c d D C D = > a a b b b c d d C D = > a a b b b c d C d D = > a a b b b c C d d D = > a a b b b cc d d D = > a a b b b c c d d d = a2b 3 c 2 d 3 .

Comentarii: Aceast gramatic realizeaz abstractizarea corespondenei numrului de parametri cu care a

: fost definit o procedur i numrul de parametri cu care aceasta se apeleaz. Deoarece nprocesul de compilare analiza sintactic utilizeaz gramatici independente de context, aceastverificare (care comport o gramatic fr restricii) se va face n faza de analiz semantic inu n cea de analiz sintactic.

problem;! 1.1-25

L={aVcndn|n>l }

Soluie:

Vom considera deci, irurile de forma an(bCD)" unde C, D sunt ncterminale prin intermediulcrora se va face generarea subirului c"dn. Pentru aceasta este necesar substituia oricruisubir de forma DC cu irul CD, respectiv nlocuirea neterminalelor C, D cu c, respectiv d.

Astfel, o gramatic G care genereaz limbajul L este G = ({ S, C, D}, { a, b, c, d }, P, S)unde: P = { S-> aSbCD | abCD, DC - CD, Db ->bD. Cb -> bC, bC -> bc, cC H> CC, CD -cd,dD->dd}.

('oinenlarii:G este o gramatic fr restricii

1.1.2 Lema de pompare

Propoziie. Pentru orice limbaj L independent de context exist un numr natural kjcaracteristic limbajului, astfel nct dac z e L i |z| > k, atunci z poate fi scris sub forma

z = uvwxy ndeplinind urmtoarele condiii:

2. |vwx|0}

Soluie:

Presupunem prin absurd c L este independent de context, deci este aplicabil lema depompare. Fie n = k i fie irul: z = a kbkck. ntr-adevr, |z| > k, deci exist irurile u, v, w, x, yi astfel nct z = uvwxy cu vx 4 X i |vwx| < k.

; Deoarece |vwx| < k, rezult c vwx nu poate conine i a i c.1) Dac vwx nu conine a, atunci u trebuie s conin toi simbolii a din irul z (adic a k).

Pentru i = 0, rezult uwy e L, adic: uwy = akbkck i deci |uwy| = 3*k. Dar, [uvwxy| = jz| =i 3*k i deci |v| = |x| = 0, ceea ce contrazice condiia vx 4 X.. 2) Dac vwx nu conine c, atunci toi simbolii c trebuie coninui n irul y (adic c k). Pentru' i = 0, rezult uwy e L, adic: uwy = akbkck i |uwy| = 3*k. Cum |uvwxy| = 3*k, rezult c |v= |x| = 0 (contradicie). Prin urmare, L nu poate fi independent de context.

p i ' o b ' e i i t u 1 . 1 - 2 7

L={ai | i = 2j J>0}

Presupunem prin absurd c L este independent de context, i este aplicabil lema depompare. Fie k = n i fie irul: z = a1". ntr-adevr, |z| > n, atunci exist irurile u, v, w, x, y .

: astfel nct z = uvwxy cu vx4 X i |vwx| < n.: Considerm z = apaV a sa2"' p" q" r" s , p,q, r, s > 0. Rezult u = ap, v = aq, w = ar, x = as i y =; a p q"' "s de unde rezult |vwxj = q + r + s lceea ce nseamn vx4 h.i Dac i = 2 atunci uvW'y e L, adic a 2"+q+s e L, de unde rezult 2n + q + s = 2

n+j = 2"+(2* ;: - l)*2n adic q + s = (2j - 1)* 2" pentru j > 1=> q + s > 2" (deoarece 2 j - l > l ) = i > q + s > n |\=>contradicie (q + r + s < n). Prin urmare, L nu poate fi independent de context. . I

16 16 17


12/48


1.1.3 Transformri asupra GIC

Gramaticile independente de context (GIC) sunt utilizate pentru analiza sintactic n cadrul,]compilatoarelor. Pentru c procesul de analiza sintactic se simplific mult dac gramaticile 1utilizate satisfac anumite condiii, este. util s se fac transformri asupra acestui tip dejgramatici, transformri care s produc gramatici echivalente (care genereaz acelai limbaj).

1.1.3.1 Eliminare recursivitate stnga

Spunem c o gramatic este recursiv stnga dac exist un neterminal A astfel nct existaio derivare A =>+ Ax pentru A e N, x e (N UT)* . Dac pentru un neterminal A exist]produciile

AB2f... | ABm|y,| ... | yn

unde Yi nu ncepe cu A, 1 < i< n, se spune c avem recursivitate stnga imediat i]produciile anterioare se pot nlocui cu:

A-Y,A'|y2A'|...|ynA'

A ' -B iA ' |B 2A ' | . . . |BmA ' |X Aceast construcie elimin recursivitatea stng imediat. Dac gramatica nu permite i

derivri de tipul A =>+ A (nu are cicluri) i nu conine Xproducii poate s fie transformat n:vederea eliminrii recursivitii stnga utiliznd urmtorul algoritm.

Intrare: o gramatic fr cicluri i X produciiIeire; o gramatic echivalent fr recursivitate stnga.Se alege o ordine a neterminale lor, fie ea: Ai, Aj, ..., Apentru i = 2 .. n execut

pentru j = 1 .. i-1 execut nlocuiete fiecare producie de forma Ai -^ Ai- ->-.Ui r | u? r I ... | uk r unde A-, -> ui I u2

sunt toate produciile pentru Aj.' D

r cu produciile-.. | uk

elimin recursivitatea stng imediat ntre produciile Ai.

1.1.3.2 Eliminare A producii

O gramatic nu are Xproducii dac satisface una din-urmtoarele condiii: Nu exist nici o producie care s aib n partea dreapt irul vid sau Exist o singur producie care are n partea dreapt irul vid i anume producia S -> X.

Simbolul S nu apare n acest caz n partea dreapt a nici unei producii.Algoritmul de transformare este:

Intrare: o gramatic G =T eire: o gramatic G' =

i = 0

No= { A 1 A X6 P}

repet

Nl= { A I A - a e

pncnd Ni =

Nj-i

dac S e N fN' = N U {S'}P' = {S' -> A., S' ->

altfelN' = NS' = S"P' = O

(N, T, P, S)(N', T, P', S') care satisface condiiile L(G) = L(G')i G' nu are Xproducii

*

?, aaoB1a1...B

kak,k>O,B,eN

f,l'/eP, /?e(Nwur)*}u N^

Pn cnd Nt

= Nj-iN' =

N.

p' c: P i este format numai produciile din P care au

n partea stng simboli din N' . .

18 18 19

li b j f l i llimbaje formale si translatoare Seminar LFA


13/48


1.1.3.4 Eliminare simboli inaccesibili

Seminar LFAb j

Un simbol neterminal este inaccesibil dac nu poate apare ntr-o form propoziional. Algoritmul de transformare este:

Intrare

Ieire:

i = 0;

No= {S}

repet

N^+=

: o gramatic G

o gramatic G'

i VA eN'

= (N, T, P

= (N', T,

exist w

{ Ae N | A apare n parteadin Nj-j} UN ,

pn cnd Ni = N^

N' = Ni

P' c: P conine numai ;produciile

, S)

P', S) care

e (N U T ) *

dreapt a

satisface condiiile L(G) = L(G')

, s = >w i A apare n w.

produciilor pentru un neterminal

corespunztoare neterminalelor din N'

Probleme

problema 1.1-28

S s e e l i m i n e r e c u r s i v i t a t e a - s t n g p e n t r u u r m t o a r e a g r a m a t i c : G = ( { S , L } , { a , , , ( , ) } ,

P , S ) u n d e P = { S - > ( L ) | a , L - > L , S | a }

Soluie:

Se alege o ordine pentru neterminale, fie ea: S < L . Pentru producia S ->(L) | a nu se facenici o modificare. La fel pentru S - a.Pentru producia L L,S | a se elimin recursivitatea imediat i rezult:

L - aL'L'-> ,SL' | X

In final dup eliminarea recursivitii stnga gramatica este:G = ({ S, L, L'}, { a,,, G)}, P, S) unde: P = { S-> (L) | a, L,-> aL', L' ->,SL' \X}

pro bit mu 1.1-29

S se elimine recursivitatea stng pentru urmtoarea gramatic:G = ({ S, A, B }, { a, b }, P, S) unde P = {S -> A | B, A -> Sa | Bb, B -> Sb | Aa}

Soluie:Se alege o ordine pentru neterminale S < A < BPentru producia S >A | B nu se face nici o modificare.Pentru producia A -> Sa | Bb avem S < A deci se va folosi S -> A | B | Xi rezult

A->Aa | Ba | a |Bb din care se elimin recursivitatea imediat i rezult:A ~> BaA' | aA' | BbA', A ' -> aA' | XPentru producia B - Sb | Aa se substituie cu S -> Sb | Aa | Xi rezult B H> Ab | Bb | b| Aaiar apoi se nlocuiete A -> BaA' | aA' | BbA' i rezult B - BaA'b | aA'b j BbA'b | Bb | b |B a A' a | a A' a | B b A' a. Din care se elimin recursivitatea imediat i rezult:

; B _> a A' b B' | bB' | a A' aB', B' -> aA'b B' | b A' b B' | b B' | a A' a B' | b A'a B' | X n final dup eliminarea recursivitii stnga gramatica este:

; G = ({ S, A, A', B, B' }, { a, b }, P, S) unde: P = { S- A | B, A -> BaA' | aA' | BbA', A' ->aA' i X , B -> a A' b B' | bB' | a A' aB' ,B' - aA'b B' | b A' b B' | b B' | a A' a B' | b A'a B'

probli-Pia 1.1-30

S se elimine recursivitatea stng pentru urmtoarea gramatic: G = ({ A, B, C }, { a, b, c },P, A) unde P = {A -> BC | a, B - Ca | Ab, C -> Ab | cC | b}

Soluie:

Se alege o ordine pentru neterminale A < B < C. Pentru producia A - BC | a nu se face nicio modificare. Pentru producia B -> Ca ] Ab deoarece A < B se va folosi A - BC j a irezult B - Ca | BCb | ab din care se elimin recursivitatea imediat i rezult: B -> CaB' |

jabB', B'->CbB'|L Pentru producia C - AB j cC | b se substituie cu A - BC | a i rezult C - BCb | aB | cC |

b iar apoi se nlocuiete B -> CaB' | abB' i rezult C - CAB'CB | abB'Cb | aB | cC | b: Din care se elimin recursivitatea imediat i se obine: C -> abB'CbC | aBC | cCC | bC,

C -> AB'CBC [ X. n final dup eliminarea recursivitii stnga gramatica este:G = ({ A, B, B\ C, C }, { a, b, c }, P, A) unde: P = { A- BC | a, B -> CaB' | abB', B" -+CbB' | X, C -> abB'CbC | aBC j cCC | bC, C - AB'CBC j X}

1.1-31

s i -> elimine ' piiHluciiili.- Jiu y. nn iik\i li iv[ s. \. li. l ',. [ J. l1 ; I'. M unde P = {S -

ABC, A -> BB | X, B -> CC | a, C -> AA | b}

Soluie:

No = {A}, Ni = {A, C}, N2 = {A, B, C}, N 3 = {S, A, B, C} = N f: S e Nf deci se introduc produciile S' -> S i S' -> X\ Producia S ->ABC devine S '->ABC | AB | AC | BC | A |B | C, Producia A - BB devine A - BB | B: Producia B -> CC \ a devine B -> CC | C | a! Producia CC -> AA | b devine C -> AA | A | b

; Dup eliminarea Xproduciilor gramatica este G = ({ S', S, A, B, C }, { a, b }, P, S') unde: P= { S' -> S , S' -> X , S -> ' ABC | AB | AC | BC | A |B | C, A -> BB 1 B, B -> C | C | a, C ->

,AA|A|b} .

2 0 2 0

21

limbaje formale si translatoare Seminar LFA li b j f l i t l t


14/48


probleniii 1.1-32

S se elimine simbolii nefinalizai, iar apoi cei inaccesibili pentru gramatica G = ({ S, A, B }, {a, b}, P, S) unde P = {S-> A | a, A-> AB, B-> b}

Soluie:Eliminare simboli nefinalizati: No = {S, B}, Ni = {S, B}, N f=Ni.Rezult c A este simbol nefinalizat, se vor elimina produciile corespunztoare neterminalului A igramatica va deveni: G = ({S, B}, {a, b }, P, S) unde P = {S -> a, B -> b}.Eliminare simboli inaccesibili:No = {S},Ni = {S},Nf=NiB este inaccesibil, d rmne producia S a. Dup eliminarea simbolilor nefinalizati i inaccesibiliG = ({S}, {a},P,S)undeP={S->a}

Coaientati:Ordinea corect de aplicare a celor doi algoritmi este eliminare simboli nefinalizai i apoi eliminaresimboli inaccesibili.

problema 1.1-33

S se elimine simbolii nefinalizai, iar apoi cei inaccesibili pentru gramatica G = ({S, A, B, C, D}, {a, b, d}, P, S) unde P= {S - bA |a B, A- a |a C| aD |a S| bAA, B -> b | Cb | Db | bS | aBB, C -

Cb | Db, D -> Cb | Db, D - Cd | dAC}

Soluie:Eliminare simboli nefinalizati:N0={A,B},N, = {S,A,B},Nf=NiRezult c C, D Nf, adic sunt simboli nefinalizati, se vor elimina produciile corespunztoare lori gramatica va deveni: G = ({S, A, B }, {a, b, d}, P, S) unde P = {S -> bA | aB, A -* a | aS | bAA,B->b|bS|aBB}Eliminare simboi inaccesibili:No={S},N,= {S,A,B},Nf=N,Nu exist simboli inaccesibili.n final gramatica este: G = ({ S, A, B }, {a, b, d}, P, S) unde P = {S -> bA | aB, A - a | aS | bAA,

B-b|bS|aBB}problema 1.1-34

S se elimine recursivitatea stng, Xproduciile, simbolii neutilizai i inaccesibili pentru gramaticaG = ({S, B, C, D, E}, {a, b}, P, S) unde P = {S-> aBa, B -> Sb | bCC |DaB, C -> abb | DD, E ->aC, D -> aDB}


Soluie:Eliminare recursivitate stnga.Se alege ordinea neterminalelor S < B < C< E< DPornind de la B -> Sb | bCC | DaB, S -aBa. Rezult B -> aBab | bCC | DaB care nu este recursivstnga-Eliminare Xproducii. Gramatica nu are Xproducii.Eliminare simboli nefinalizai. No = {C}, Ni = {B, C, E}, N2 = {S, B, C, E} = NfD aBa, B -> Sb | bCC, C -> abb, E

22

22

Eliminare simboli inaccesibili.No = {S}, Ni = {S, B}, N2 = {S, B, C}

=N E Nf,

rezult E simbolinaccesibil.n final rezult: G = ({S, B, C}, {a, b}, P, S) undeP = {S -> aBa, B-> Sb [bCC, C ->abb}

problema 1.1-35

S se elimine recursivitatea stnga, Xproduciile, simbolii neutilizati i inaccesibili pentru gramaticaG = ({S, T}, {a, b, c}, P, S) unde P = {S-> TbT, T -> TAT |ca}

Soluie:

Eliminare recursivitate stnga. Alegem ordinea neterminalelor S < T. Se consider producia T ->TaT | se elimin recursivitatea stnga i rezult T - caT' i T' > aTT' | XRezultG = ({S, T, T'} , {a, b, c}, P, S) undeP = {S -> TbT, T ->caT', T' -> aTT' | X}Eliminare Xproducii. No = {T'}, Ni = {T'}, Nf=N i, Rezult G = ({S, T, T'}, {a, b, c}, P, S) unde

P={S->TbT, T-caT'|ca,T'->aTT'|aT}Eliminare simboli nefinalizai. No = {T}, Ni = {S, T, T'}. Nu exisist simboli nefinalizai.Eliminare simboli inaccesibili. No = {S}, Ni = {S, T}, N2 = {S, T, T'}, Nf = N2. Nu exist simboliinaccesibili.

n final se obine G = ({S, T, T'}, {a, b, c}, P, S) unde P = {S - TbT, T - caT' | ca, T' -> aTT' |aT}.

1.1 Mulimi regulate. Expresii regulate

Definiia 1.2.1. Fie T un alfabet finit. Se numete mulime regulat asupra alfabetului Tmulimea definit recursiv astfel:

1- 0 este o mulime regulat asupra alfabetului T.2. Dac a e T, atunci { a } este o mulime regulat asupra alfabetului T.3. Dac P, Q sunt mulimi regulate, atunci P u Q , PQ, P* sunt mulimi regulate asupra

alfabetului T.4. O mulime regulat asupra alfabetului T nu se poate obine dect aplicnd regulile 1-3.Am notat prin P u Q , PQ, respectiv P* reuniunea, concatenarea a dou mulimi, respectiv

nchiderea tranzitiv a unei mulimi.Definiia 1.2.2. O expresie regulat este definit recursiv n modul urmtor:1. Xeste o expresie regulat care genereaz mulimea 0.2. Dac a e T, atunci a este o expresie regulat care genereaz mulimea { a }.3. Dac p, q sunt expresii regulate care genereaz mulimile P, Q, atunci:(p + q) sau (p | q) este o expresie regulat care genereaz mulimea P u Q .

23



15/48


(pq) este o expresie regulat care genereaz mulimea PQ.(p)* este o expresie regulat care genereaz mulimea P*.4. O expresie regulat nu se poate obine dect prin aplicarea regulilor 1-3.

Proprieti ale expresiilor regulate:

Seminar LFA limbaje formale si translatoare Seminar LFA

l . a | P = B|oc2.a |(B|y) = (a | P) | y 3.ct(py) = (a p ) y4.a(P|y) = aP|ay 5 . ( a | P) y = a y | p y 6. a^. = A,a = a7. a*= a I a*

(comutativitate reuniune)(asociativitate reuniune)(asociativitate concatenare)(distributivitate la stnga a concatenrii fa de reuniune)(distributivitate la dreapta a concatenrii fa de reuniune)(element neutru pentru concatenare)

8. (a * ) * = a*9. a | a= a10.(a*p*)* = (a + P)*Utiliznd expresii regulate se pot construi ecuaii regulate. Soluia general a ecuaiei de

forma: X = a X + b unde a, b, X sunt expresii regulate, este: X = a* (b + y) unde y este oexpresie regulat oarecare. Soluia minimal (punctul fix al ecuaiei) este: X = a* b.

Propoziie Fie G o gramatic regulat. L(G) este o mulime regulat.Definiia 1.2.3. Dou expresii regulate se numesc echivalente dac descriu aceeai mulime

regulat.

Probleme

problema 1.12-1

S se rezolve sistemul de ecuaii:X= al X+ a2Y+ a3Y= bl X+ b2Y+ b3

Soluie:Pentru prima ecuaie, soluia este X = a l* (a2 Y + a3), nlocuind n cea de-a doua ecuaie, obinem Y= bl al* (a2 Y + b3) + b2 Y + b3 sau echivalent, folosind proprietile expresiilor regulate: Y = bl

al*a2 Y + bl al *b3 +b2 Y + b3 sauY = (bl al*a2+ b2) Y + (bl al* b3 +b3).Deci,pentruYseobine soluia Y = (bl al* a2 + b2)* (bl al* b3 + b3). n mod corespunztor, nlocuind n primaecuaie, se obine urmtoarea soluie pentru X: X = al* a2 Y + al* a3 sau X = al* a2 (bl al* a2 +

b2)*(blal*b3+b3) + al*a3.

problema 1.12-2

S se rezolve sistemul de ecuaii:X1=OX2+1X1+,X2 = OX3+ 1X2X3 = OX1 + 1X3

24

Soluie:

Din ultima ecuaie obinem X3 = 1* 0 XI. nlocuind n a doua ecuaie obinem X2 = 1 X2+0 1* 0xl, de unde rezult X2 = 1 * 0 1 * 0 XI. Dac se nlocuiete n prima ecuaie rezult XI = 0 1 * 0 1 * 0XI + 1 XI + X. Deci XI = (01*01*0 + 1)*. Dac se nlocuiete rezultatul obinut pentru XI nformulele corespunztoare lui X2 i X3 obinem X2 = 1* 0 1* 0 (0 1* 0 1* 0 + 1)* i X3 = 1* 0 (01*01*0+1)*.

Comentarii:

Se poate demonstra c n expresia regulat XI numrul de simboli 0 este divizibil cu 3. Prin urmare,

XI poate fi scris sub form echivalent: XI =(1*0 1*0 1*0)* 1*.problema 1.12-3

S se construiasc expresia regulat care genereaz mulimea regulat egal cu limbajul generat degramatica regulat cu produciile: P-> 0 Q11 P, Q- 0 R11 P, R- 0 R11 R10

Soluie:

Asociem fiecrui netcrminal o expresie regulat i fiecrei producii de forma A-> a | p, o ecuaie deforma A = a + p unde a i p sunt tot expresii regulate. Corespunztor setului de producii de maisus, se obine urmtorul sistem de ecuaii:

P=0Q+lP

Q=0R+lPR=0R+lR+0

Din ultima ecuaie, se obine folosind proprietatea de distributivitate a concatenrii fa de reuniuneR = (0 + 1) R + 0 care are soluia R = (0 + 1)* 0. nlocuind n a doua ecuaie, obinem: Q = 0 (0 +1)* 0 +1 P. nlocuind Q n prima ecuaie: P = 0 0( 0+ 1) *0 + 0 1 P + 1 P adic P = (01 + l )P + 00(0 + 1)* 0. Aceast ecuaie are soluia P = (0 1 + 1)* 0 0 (0 +1)* 0.

S se construiasc expresia regulat care genereaz mulimea regulat egal cu limbajulregulat generat de gramatica regulat:

S- 0 A[ 1 S | X A-0B|l AB->0S| lB

Soluie:

Corespunztor setului de producii de mai sus, se obine urmtorul sistem de ecuaii:S = 0 A + l S + X A = 0 B + l A B = 0 S + l B

24 25

I


16/48

limbaje formale si translatoare Seminar LFA I! Din ultima ecuaie, obinem B = 1 * 0 S. nlocu ind n a doua ecuaie, aceasta devine: A = 0 1 *: 0 S + I A care are soluia A = l * 0 1 * 0 S . Prima ecuaie devine n urma nlocuirii expresiei: regula te A, S = O 1 * O 1 * OS + 1 S + Xsau, folosind distributivitatea concatenrii fa de

reuniune. S = (0 1* 0 1* 0 + 1) S + Xcare are soluia S = (0 1* 0 1* 0 + 1)* X = (0 1* 0 1* 0

+ ! ) * '

problema 1.2-5

S se construiasc gramatica regulat care genereaz limbajul generat de expresia regulat:

(a I b)* a* b+ a*

Soluie:Notm S = (a | b)* a* b+ a* i A = a* b+ a*. Corespunztor, se poate scrie ecuaia ce aresoluia S: S = (a + b) S + A. De asemenea, dac notm B' = b+ a* i B = b* a*, putem scrieurmtoarea relaie B' = b B (deoarece b+ = b b*).Pe de alt parte, A = a* B' i deci se poate scrie relaia A = aA + B'sauA = aA + bB undeB = b* a*. Notnd C = a*, B devine B = b* C care este soluia ecuaiei B = b B + C. Deasemenea, C = a* este soluia ecuaiei C = a C + X. Prin urmare, corespunztor expresieiregulate de mai sus se obine urmtorul sistem de ecuaii:

S = a S + b S + A A = a A + b BB = b B + C

C = aC + A,i respectiv urmtorul set de producii:

S -> aS b S j A A - > a A | b BB - >bB

Gramatica G care genereaz limbajul descris de expresia de mai sus, este G = ({ S, A, B, C },{ a, b }, P, S) cu P mulimea de producii de mai sus.

problema 1.2-6

S se construiasc gramatica regulat care genereaz limbajul descris de expresia regulat:

: (a |b)* a (a |b)

Soluie:Notm S = (a | b)* a (a | b) i A' = a (a | b). Deci, S este soluia ecuaiei S = (a + b) S + A' iarA' poate fi scris sub forma A' = a A unde A = a + b. Deci, corespunztor expresiei regulate S,poate s fie scris urmtorul sistem de ecuaii: S = a S + b S + A', A' = a A, A = a + b sauS = aS + bS + aA, A = a + b. Gramatica ce genereaz limbajul generat de expresia S este G= ({ S, A }, { a, b }, P, S) unde P conine produciile: { S - a S | b S | a A, A-> a | b }.

26 26


problema 1.2-7

se construiasc gramatica care genereaz limbajul descris de expresia regulat:(a | b)* a (a | b) (a 1 b)

Soluie: .Notm S = (a | b)* a (a | b) (a | b) i respectiv A1 = a (a | b) (a | b). S este soluia ecuaiei: S =(a + b) S + A' care poate s fie scris echivalent S = a S + b S + A' (1). Dar A' = a A unde A= (a | b) (a S b). Prin urmare, relaia (1) devine S = aS + bS + aA (2). Dac notm B = (a | b),

atunci A devine - A = a B + b B (3) i B = a + b (4) Corespunztor relaiilor (2) - (4), setul deproducii al gramaticii G care genereaz limbajul descris de expresia regulat S este :

S - a S | b S | a A A-> a B | b BB-> a | b

Gramatica ce genereaz limbajul descris de expresia regulat dat este G = ({S, A, B}, {a,b}, P, S) unde P conine produciileJS- a S | b S [ a A, A-> a B | b B, B-> a | b}

1.3 Acceptoare

Spre deosebire de gramatici i expresii regulate care genereaz limbaje formale acceptparelesunt dispozitive care sunt n strare s recunoasc" dac un ir de simboli face parte dintr-unlimbaj pentru care mecanismul este acceptor.

1.3.1 Automate finite

Definiia 1.3.1. Se numete automat finit un obiect matematic AF = (Q, T, m, sO, F) unde: Q reprezint mulimea finit a strilor T este o mulime finit de elemente numit alfabet de intrare m este funcia parial a strii urmtoare m: Q x (T U { X}) - P(Q) unde prin P(Q) s-a

notat mulimea prilor lui Q sO e Q este o stare numit starea de start

F c Q este o mulime de stri numit mulimea strilor finale sau de acceptareDefiniia 1.3.2. Se numete graf de tranziie pentru automatul finit AF = (Q, T, m, sO, F) un

graf orientat cu arce etichetate G = (N, A) n care nodurile (mulimea N) reprezint strileautomatului finit, iar arcele (mulimea Ac N x N) sunt definite astfel: (s i; Sj) e A dac exist ae T astfel nct Sj e m(s i; a). n acest caz, arcul (SJ, sj) este etichetat cu simbolul a.

Definiia 1.3.3. Se spune c un ir w GT* este acceptat de automatul finit AF dac exist ocale n graful de tranziie ntre starea de start i o stare final, astfel nct irul simbolilor careeticheteaz arcele este irul w. Mulimea irurilor acceptate de un automat finit formeazlimbajul acceptat de automatul finit respectiv.

Definiia 1.3.4. Se numete automat finit determinist un automat finit AF = (Q, T, m, sO, F)pentru care funcia de tranziie m: Q x T-> Q. Se observ c n acest caz:

nu exist X-tranziii

27

limbaje formale si translatoare Seminar LFA 1 limbaje formale si transla toare Seminar LFA


17/48

1pentru orice s e Q i orice a e T exist o unic stare s' e S astfel nct m(s, a)=s'.Propoz iie. Pentru orice automat finit nedeterminist (AFN) exist un automat finit

determinist (AFD) care accept acelai limbaj.Propoziie Limbajele acceptate de automate finite sunt limbaje regulate (generate de

gramatici regulate). Avnd n vedere c limbajele regulate sunt generate i de expresii regulate, exist o

echivalen ca putere ntre gramatici regulate, expresii regulate i automate finite. Automatele;finite deterministe sunt utilizate pentru implementarea analizoarelor lexicale. Expresiile regulate 'sunt utilizate pentru specificare atomilor lexicali recunoscui de un analizor lexical n mod;corespunztor au fost elaborai algoritmi pentru construirea de automate finite deterministe

direct din expresii regulate.

Probleme

problema 1.3-1

i S se construiasc automatul finit care accepta limbajul generat de gramatica:; P->0 Q|1P

Q-> 0 R | 1 PR-> 0 R11 R | 1

S se reprezinte graful de tranziie corespunztor.

Soluie;Gramatica este n mod evident regulat, prin urmare exist un automat finit care acceptlimbajul generat de aceasta. Vom construi acest automat asociind fiecrui neterminal o starei fiecrei producii o tranziie. Rezult c putem construi urmtoarea funcie de tranziie:

m(P,0) = {Q},m(P, 1) = {P}m(Q,0) = {R},m(Q,l)={P}m(R,0 )={R} ,m(R, 1) = { R, U }

unde U este o stare nou introdus, n care se va produce acceptarea (deci va fi singura starefinal). Prin urmare, automatul finit care accept limbajul generat de gramatica de mai suseste: AF = ({ P, Q, R, U }, { 0, 1 }, m, P, { U }). Corespunztor, graful de tranziie asociateste:

problema 1.3-2

ga se construiasc automatul finit care accept limbajul generat de gramatica G:S-> 0 A | 1 S X, A- 0 B | 1 A, B-> 0 S | 1 BS se reprezinte graful de tranziie asociat.

Soluie: ' . - ' . " _ - . Fie urmtoarea mulime de stri Q = { qO, ql, q2 } astfel nct asociem fiecrui neterminal ostare din Q: lui S i se asociaz qO, lui A i se asociaz ql, lui B i se asociaz q2.Corespunztor construim funcia de tranziie n modul urmtor:m(qO, 0) = ql , m(qO, 1) = qO, m(ql, 0) = q2, m(ql, 1) = ql, m(q2, 0) = qO, m(q2, 1) = q2

Automatul finit este AF = ({ qO, ql, q2 }, { 0, 1 }, m, qO, { qO }). Se observ c AF estedeterminist. Graful de tranziie corespunztor este:

Comentam;

irurile acceptate conin un numr de simboli 0 divizibil Cu 3. Automatul obinut estedeterminist.

proMcma 1,3-1

\ S se construiasc gramatica regulat pentru limbajul L = { w e {a,b}* [ w = ubbab, u E {a, j b}* } construind mai nti graful de tranziie asociat. . , |

Soluie:Fie S starea iniial a automatului. Trebuie s accepte irurile care se termin cu bbab. Din

i starea S trecem n starea A n momentul n care apare un b (am recunoscut primul b dinsubirul bbab). Din starea A se trece n starea B dac s-a ntlnit un b (s-a recunoscut irul

bb) i se trece n starea S dac s-a primit un a (n continuare se ncearc s se identificei subirul bbab).

Din starea B se trece n starea C dac s-a ntlnit un a (s-a recunoscut bba) i se rmne n B

! pentru b. Din starea C se trece n starea D dac s-a ntlnit un a, adic n starea D arii gsit\ bbab, deci D este stare final. Din starea C se revine n S dac s-a ntlnit un a, se rencearci s se identifice subirul bbab. n starea S se poate rmne dac s-a ntlnit a sau b (pentru a; se putea accepta irul u).

Comentarii:

Se observ c n acest caz, automatul finit obinut este nedeterminist (pentru starea R isimbolul 1 exist dou stri succesoare posibile: R i U).

2829

limbaje formale si translatoare Seminar LFA limbaje formale si translatoa re Seminar LFA


18/48


Pentru a construi gramatica fiecrei stri i se asociaz un neterminal. Rezult gramatica G = '({ S, A, B, C}, { a, b }, P, S) unde: P = { S- a S | b S | b A, A -> b B | a S, B -> b B | a C, C '

! .3-4

S se construiasc gramatica regulat care genereaz limbajul L = { aia2 ... an | n > 3, a, e{x, y}, an.2 = y } construind mai nti graful de tranziie asociat.

Soluie:Fie S starea iniial a automatului. n starea S se accept x i y pentru a se genera oriceprefix. De asemenea din S se trece n starea A dac s-a ntlnit y (s-a recunoscut a n.2). Dinstarea A se trece n starea B dac s-a ntlnit x sau y. Din starea B se trece n starea C dac s-a ntlnit x sau y (C este i stare final).

; Pentru a construi gramatica, fiecrei stri i se asociaz un neterminal. Rezult gramatica G =i ({ S, A, B}, { x, y }, P, S)unde: P = { S-> x S | y S | y A, A -x B | y B, B - x j y).

problema !.3-5

i S se construiasc automatul finit care accept limbajul descris de expresia regulat:; (a | b)* a* b+ a*

S se reprezinte graful de tranziie corespunztor.

Soluie:

i Expresia regulat (a | b)* a* b+ a* genereaz limbajul generat i de gramatica G determinati- n Problema 1.2.5, adic: S- a S | b S | A, AH> a A | b B, B-> b B | C, C-> a C | X' Construim automatul finit care accept limbajul descris de expresia regulat de mai sus.: Funcia de tranziie parial pentru automatul finit care accept limbajul descris de gramaticai G este: m(S, a) = { S }, m(S, b) = { S }, m(S, X) = { A }, m(A, a) = { A }, m(A, b) = { B },| m(B, b) = { B }, m(B, X) = { C }, m(C, a) = { C }! Deoarece exist producia C - X, starea asociat neterminalului C este de acceptare (sau

final). Acelai lucru s-ar fi ntmplat pentru orice producie de forma A > a, cu a e T.: Automatul finit care accept limbajul descris de expresia (a | b)* a* b+ a* este AF = ({ S, A,; B, C }, { a, b, c }, m, S, { C }).

30 30

Comentarii:Automatul AF astfel construit este nedeterminist (are X-tranziii).

prolrfcnta 1,3-6

S se construiasc automatul finit care accept limbajul descris de expresia regulat:(a i b)* a (a I b)

Soluie:

Gramatica G care genereaz limbajul descris de expresia regulat (a | b)* a (a | b) este (veziProblema 1.2.6.): S - a S | b S | a A , A- a | b. Asociem fiecrui neterminal o stare ifiecrei producii o tranziie. Corespunztor, obinem urmtoarea funcie de tranziie parial:m(S, a) = { S, }, m(S, b) = { S }, m(A, a) = { B }, m(A, b) = { B } unde B este o stare deacceptare (finala) nou introdus. Se observ ca automatul finit este nedeterminist. Graful detranziie corespunztor este:

a,b

Dac dorim s construim automatul finit determinist care accept limbajul descris de (a | b)*a (a | b), putem s efectum transformri asupra gramaticii G astfel nct din mulimeaproduciilor s rezulte o funcie de tranziie de tipul: m: Q' x T-> Q'. Pentru aceasta,transformm gramatic G prin factorizare stnga (terminalul a ncepe i n producia S. a Si producia S- a A). Obinem: S- a C | b S, A- a | b, C-> S | A.Prin substituie de nceputuri(" corner substitution "), obinem: S-> a C | b S, A-> a | b,C-> a C b S a | b, unde observm c neterminalul A este neutilizat(deci l putem elimina).Aplicnd din nou factorizarea stnga urmat de substituie de nceputuri, obinem:SH> a C | b S, C-> a D | b E, D-> C | X, E-> S | X, respectiv, S-> a C | b S, C-> a D | bE, D-> a D | b E | X, E-> a C | b S | X. Se observ c n acest caz se poate construi o funciede tranziie total de forma: m(S, a) = C, m(S, b) = S, m(C, a) = D, m(C, b) = E, m(D, a) =

; D, m(D,'b) = E , m(E, a) = C, m(E, b) = S; Graful de tranziie pentru acest automat finit determinist este:

Strile asociate neterminalelor D, respectiv E sunt stri de acceptare datorit existeneiproduciilor: DH> Xi E -* X.

31

limbaje formale si translatoare Seminar LFA limbaje formale si translatoare


19/48

j Seminar LFA limbaje formale si translatoare Seminar LFA

Comentarii:Se poate construi automatul finit determinist care accept limbajul de mai sus pornind directde la.expresiaregulat.

proMwii i I '- "

S se construiasc automatul finit care accept limbajul generat de expresia regulat(a I b) * a (a \ b) (a | b)

Soluie.

Fie gramatica G care genereaz limbajul descris de expresia regulata (a | b)* a (a | b) (a | b)(vezi Problema 1.2.7.): S-> a S | b S | a A, A- a B | b B, B-> a | b. Construim pe bazamulimii de producii de mai sus urmtoarea funcie de tranziie: m(S, a) = { S, A }, m(S, b)= { S }, m(A, a) = { B }, m(A, b) = { B }, m(B, a) = { C }, m(B, b) = { C } unde C este ostare de acceptare nou introdus.

Se observ c automatul finit obinut: AF = ({ S, A, B, C }, { a, b }, m, S, { C }) estenedeterminist. Graful, corespunztor este:

problema ;3># ,

S se construiasc AFN (automatul finit nedeterminist) care genereaz acelai limbaj ca i; urmtoarea expresie regulat i apoi s se construiasc AFD-ul (automatul finit determinist)corespunztor. S se fac i construcia direct: expresie regulat-AFD(a |b)*a(a |b)

Soluie:

AFN corespunztor expresiei regulate (a | b)* a (a | b) este:

Pentru a obine automatul finit determinist care accept limbajul generat de gramatica G demai sus, se pot face transformri asupra gramaticii. Prin factorizare stnga (terminalul a

ncepe i producia S- a S i producia S-> a A) se obine: S - a D | b S , A - a B | b B, B-> a | b, D -> S | A. Prin substituie de nceputuri(" corner substitution "), obinem: S -> a D|b S, B -> a [ b, D - > a D [ b S | a B | b B , unde observm c neterminalul A este neutilizat(deci l putem elimina). Aplicnd din nou factorizarea stnga urmat de substituie de

nceputuri, obinem: S -> a D | b S, B ^ a | b, D - a E | b F, E -> D | B, F -> S | B,respectiv, S - a D | b S, D - a E | b F, E - > a E | b F | a | b , F- > a D | b S j a | b . Aplicnddin nou factorizarea stnga urmat de substituie de nceputuri, obinem: S - a D | b S, D ->a E | b F , E -> a G | b H, F -> a 11 b J, G - E | A,, H - F | A,, I - D | A,, J ->S | A., respectiv, S

- a D | b S , D - > a E | b F , E - a G | b H , F - > a I | b J , G - > a G | b H | X , H - > a I | b J | A . , I~ > a E | b F | A, , J -> a D| b S | A. .

Se observ c n acest caz se poate construi o funcie de tranziie total de forma:m(S, a) = D, m(S, b) = S, m(D, a) = E, m(D, b) = F, m(E, a) = G, m(E, b) = H , m(F, a) = I,m(F, b) = J, m(G, a) = G, m(G, b) = H, m(H, a) = I, m(H, b) = J, m(I, a) = E, m(I, b) = F, m(J,a) = D, m(J, b) = S. Graful de tranziie al automatului determinist este:

Construcia AFD se face pe baza algoritmului de construire a unui AFD echivalent unui AFNd a t (vezi curs pentru notaii i algoritm). Starea iniial a AFD va fi: qO = X inchidere({ 0 }) =i 0 1,2,3,7}.

n continuare, celelalte stri precum i tranziiile corespunztoare se vor determina astfel:( x) = qj unde qj = _inchidere(move(qi, x)), obinem:

q! = A._inchidere(move(qO, a)) = A,_inchidere({ 4, 8 }) = { 1,2, 3, 4, 6, 7, 8, 9, 10 }q2 = \_inchidere(move(qO, b)) = jnchidere({ 5 }) = { 1, 2, 3, 5, 6, 7 }q3 = Mnchidere(move(ql, a)) = A._inchidere({4, 8,11}) = {1,2, 3, 4, 6, 7, 8, 9, 10, 11,13 }(34 = Unchidere(move(ql, b)) = ljnchidere({ 5, 12 }) = { 1, 2, 3, 5, 6, 7,12, 13 }

32 321 33



20/48

Se obine urmtoarea tabel de tranziii:stare

qO

q lq2q3

q 4

stare urmtoarea

q iq3

q lq3

q l

bq2

q 4

q2q4

q2

i corespunztor, graful de tranziie:

Dac dorim acum s construim direct automatul finit determinist care accept expresia de maisus, trebuie s utilizm algoritmul de construire a AFD direct din expresia regulat (vezi curs).Considerm arborele corespunztor expresiei regulate, terminate cu terminatorul #:

(a | b)* a (a | b) #123456

Arborele este:{1,2,3} . {6}

/ \

/ \

{1,2,3} . {4,5} \

/ \{6}#{6}/ \ 6

/ \

/ \

{1,2,3} . {3} {4,5}[ {4,5}

/ \ / \

/ \ / \

/{3}a{3} / \* 3 / \

{1,2}|{1,2} / \/ \ {4}a{4} {5}b{5}/ \ 4 5

/ \

/ \

{1}a{1} {2}b{2}

1 2

, Am notat n stnga fiecrui nod firstpos(nod), iar n dreapta lastpos(nod). Calculnd pentrui fiecare nod frunz followpos(i) (i codul unui nod frunz), se obine:

nod

a 1b 2

a 3a 4

b 5

# 6

followpos{1, 2, 3}{1, 2, 3}

{ 4 , 5 }{ 6 }

{ 6 }

-

Corespunztor tabelei de mai sus, se obine automatul finit nedeterminist reprezentat prin: urmtorul graf de tranziie (vom asocia fiecrui nod frunz o stare n graful de tranziie), arcele; sunt stabilite dup urmtoarea regul: exist un arc ntre nodul i i nodul j dac j 6 followpos(i). Arcul se eticheteaz cu simbolul corespunztor codului j. De asemenea, se introduce o stare: iniial 0 din care exista .-tranziii n strile din firstpos(rad) (rad este rdcina arboreluicorespunztor expresiei regulate). Vom obine urmtorul graf de tranziie:

% '

Se observ c n strile 4, respectiv 5 este acceptat sufixul aa, respectiv ab. Automatul finitdeterminist corespunztor expresiei regulate se obine considernd c stare iniial firstpos(rad)= { 1, 2, 3}. Tranziiile se determin astfel:

m(qi, x) = U { followpos(i)} = qji = cod(x) i

Se obine urmtorul graf de tranziie pentru AFD: j

34 3435

li b j f l i t l t Seminar LFA


21/48


Am subliniat n fiecare mulime nodurile i pentru care este ndeplinit condiia i = cod (a).

Comentarii:Se observ c n starea { 1,2,3,4,5,6 } se accept sufixul aa, iar n starea {1,2,3,6} se accept!sufixul ab. Ambele sunt stri terminale deoarece conin codul pentru # (terminatorul expresiei]regulate).

S se construiasc AFN pentru urmtoarea expresie regulat i apoi s se construiasc AFD-ul corespunztor. S se fac i construcia direct: expresie regulat-AFD:

(a |b)* a (a |b) (a |b)

Soluie:AFN corespunztor expresiei regulate de mai sus este:

Pentru a obine AFD din AFN-ul de mai sus, starea iniial a noului automat determinist vafi: qO = A._inchidere({ 0 }) = { 0, 1, 2, 3, 7 } deoarece starea iniial a AFN este starea 0. ncontinuare, vom determina strile urmtoare si tranziiile utiliznd:m(qi, x) = _inchidere(move(qi, x))


Vom obine: m(qO, a) = A_inchidere(move(qO, a)) = X_inchidere({ 4, 8 }) = { 1, 2, 3, 4, 6, 7,8, 9, 10 } = ql, m(qO, b) = A,_inchidere(move(qO, b)) = A,_inchidere({ 5 }) = { 1, 2, 3, 5, 6, 7} = q2, m(ql, a) = X_inchidere(move(ql, a)) = X_jnchidere({ 4, 8, 11 }) = { 1, 2, 3, 4, 6, 7,8, 9, 10, 11, 13, 14, 15, 16 } = q3, m(ql, b) = \_inchidere (move(ql, b)) = Jnchidere ({ 5^

: 12 }) = { 1, 2, 3, 5, 6, 7, 12, 13, 14, 15, 16 } = q4, m(q2, a) = A._inchidere(move(q2, a)) =: X_inchidere({ 4, 8 }) = ql, m(q2, b) = A,_inchidere(move(q2, b)) = A._inchidere({ 1, 2, 3, 5,; 6, 7 }) = q2, m(q3, a) = X_inchidere(move(q3, a)) = X_inchidere({ 4, 8, 11, 17 } = { 1, 2, 3,4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19 } = q5, m(q3, b) = \._inchidere(move(q3, b)) =

X_mchidere({ 5, 12, 18 }) = { 1, 2, 3, 5, 6, 7, 12, 13, 14, 15, 16, 18, 19 } = q6, m(q4, a) =X_inchidere(move(q4,a)) = X_inchidere({ 4, 8, 17 })={ 1, 2, 3, 4, 6, 7, 8, 9, 10, 17, 19 } =: q7, m(q4, b) = A._mchidere(move(q4, b)) = A,_inchidere({ 5, 18 }) = { 1, 2, 3, 5, 6, 7, 18, 19 }= q8, m(q5, a) = A,_inchidere(move(q5, a)) = A,_inchidere({ 4, 8, 11, 17 } = { 1, 2, 3, 4, 6, 7,

: 8, 9, 10, 11, 13, 14, 15, 16, 17, 19 } = q5, m(q5, b) = X_inchidere(move(q5, b))' =; X_inchidere({ 5, 12, 18 }) = { 1, 2, 3, 5, 6, 7, 12, 13, 14, 15, 16, 18, 19 } = q6, m(q6, a) =X_inchidere(move(q6, a)) = \jnchidere({ 4, 8, 17 }) = { 1, 2, 3, 4, 6, 7, 8, 9, 10, 17, 19 } = \q7, m(q6, b) = ^_inchidere(move(q6, b)) = A,_inchidere({ 5, 18 }) = { 1, 2, 3, 5, 6, 7, 18, 19 } \= q8, m(q7, a) = X_inchidere(move(q7, a)) = ^_inchidere({ 4, 8, 11 }) = { 1, 2, 3, 4, 6, 7, 8, i

: 9, 10, 11,13, 14, 15, 16 } = q3, m(q7, b) = ;Wnchidere(move(q7, b)) = X_inchidere({ 5, 12 j}) = { 1, 2, 3, 5, 6, 7, 12, 13, 14, 15, 16 } = q4, m(q8, a) = X_inchidere(move(q8, a)) = i

; X,_inchidere({ 4, 8 }) = { 1, 2, 3, 4, 6, 7, 8, 9, 10 } = ql, m(q8, b) = A._inchidere(move(q8, b)) i

; = A,_inchidere({ 5 }) = { 1, 2, 3, 5, 6, 7 } = q2. j

' O alt soluie se obine pornind direct de la expresia regulat construind AFN, respectiv AFD !corespunztoare. n mod corespunztor funciei de tranziie de mai sus, obinem urmtorul igraf de tranziie asociat AFD. Strile finale vor fi toate strile care conin starea final 19 din i

i AFN iniial: i

36 36

limbaje formale si translatoareSeminar LFA limbaje formale si translatoare Seminar LFA


22/48

Arborele corespunztor expresiei regulate este: Procednd n mod analog problemei precedente obinem urmtorul AFN:

{1,2,3} . {8}

/ \

/{8}#{8}/ 8

{1,2,3} . {6,7}

/ \

/ \

/ \

{1,2,3} . {4,5} \

/ \ {6,7} | {6,7}/ \ A

/ \ / \/ \{6}a{6}{7}b{7}

/ \ 6 7/ \

{1,2,3} . {1,2,3}{4,5} 1 {4,5}/ \ / \

/ \ / \/ {3} a {3} / \

* 3 / \{1,2} | {1,2} / \

/ \ {4} a {4} {5} b {5}/ \ 4 5

/ \/ \/ \

{1} a {1} {2} b {2}1 2

n stnga fiecrui nod se afl firstpos(nod), iar n dreapta lastpos(nod). Calculnd pentrufiecare frunz followpos(i) (i este codul frunzei), obinem:

nod

a 1

b 2

a 3a 4

b 5

a 6

b 7

# 8

followpos

{ 1, 2, 3 }{ 1, 2, 3 }

{ 4 , 5 }{ 6 , 7 }{ 6 , 7 }

{ 8 }

{ 8 }

-

Dac dorim s obinem AFD corespunztor automatului de mai sus, considerm ca stareiniial firstpos(rad) = { 1, 2, 3 }. Tranziiile se obin astfel:

m(qi, x) = v followpos(j) = qkj = cod(x)

Obinem urmtorul automat finit determinist (n care sunt marcate ca fmale strile ce conincodul 8 corespunztor simbolului terminator #):

38

38 39

limbaje formale si translatoa re Seminar LFA limbaje formale si translatoareSeminar LFA


23/48

limbaje formale si translatoa re Seminar LFA

problem;! 1.3-10

S se construiasc automatul finit determinist pentru expresia regulat: (a|b)*.

Soluie; .Considerm expresia regulat terminat cu simbolul # i codificm n mod corespunztorsimbolii:

(a | b)* #123Pentru expresia regulat de mai sus, arborele corespunztor este:

{1,2,3} . {3}

/ \

/ \

{1,2}*{1,2}{3} #{3}

{1,2}|{1,2} 3

/ \

/ \

/ \

{1} a{1} {2} b{2}

1 2

Determinnd pentru fiecare cod i followpos(i) pe baza mulimilor firstpos(nod) (specificat n stnga nodurilor), respectiv lastpos(nod) (specificat n dreapta nodurilor), se obineurmtorul tabel:

nod

a 1b 2

# 3

followpos

{1, 2, 3}

{1, 2, 3}

-

Graful de tranziie corespunztor automatului finit se determin asociind fiecrui cod o stare,iar arcele se determin astfel: exist un arc ntre starea i i starea j dac j e followpos(i), iareticheta arcului este simbolul cu codul j. Obinem:

Am introdus o stare de start (0) din care exist ^-tranziii n strile corespunztoare elementelor din mulimea firstpos(rad) = { 1, 2, 3 }. De asemenea, starea 3 corespunztoare

simbolului terminal # este stare final. Automatul fmit obinut astfel este nedeterminist.Dac dorim s obinem automatul finit determinist, vom considera starea de startfirstpos(rad) = { 1, 2, 3 }, iar tranziiile se determin ca n problema anterioar. Obinemurmtorul automat finit determinist:

1,2,3

S se minimizeze automatele specificate prin graf urile de tranziie:

prolik'ma 1.3-11

b

Soluie;

Introducem o nou stare d astfel nct funcia de tranziie s fie total, adic pentru oricestare q pentru care m(q, x) nu este definit (x e{ a, b }), adugm m(q, x) = d. Noul graf detranziie devine:

40 40

41

limbaje formale si translatoare Seminar LFA limbaje formale si translatoan Seminar LFA


24/48

Fie partiia disjunct pe mulimea strilor: P = { { 0, 1, 2, 4 }, { 3, 5, 6, 7 }, { d } }undeprima mulime este mulimea strilor nefmale, iar a doua este mulimea strilor finale. ncontinuare, pentru fiecare mulime Q e P si toate strile q e Q pentru care: m(q, x) g Q1

astfel nct exist q' cu m(q', y) e Q' (1). Se construiete o nou partiie: P = (P \ { Q }) u {Q \ new, new } unde new este mulimea strilor care ndeplinesc condiia (1). ntr-adevr, ncazul nostru obinem. Pentru Q = { 0, 1, 2,4 }, tranziiile strilor componente sunt:m(0, a) = 1 e Q m(0, b) = 2 e Q, m(l, a) = 4 e Q m(l, b) = 5 g Q deci 1 e newm(2, a) = 3 Q deci 2 e new, m(4, a) = 4 e Q m(4, b) = 2 e Q

Prin urmare, noua partiie pe mulimea strilor este: P = {{0,4}, {1,2}, {3 ,5, 6,7}, {d}}.Pentru Q = { 0, 4 }, tranziiile strilor sunt: m(0, a) = 1 e { 1, 2 } m(0, b) = 2 e { 1, 2 },m(4, a) = 4 g { 1, 2 } deci 4 e new. Partiia obinut pe mulimea strilor devine: P = {{0 },{ 4 }, { 1, 2 }, { 3, 5, 6, 7 }, { d } }. Pentru Q = { 1, 2 } (este prima mulime din partiie careconine mai mult de un element) rezult: m(l, a) = 4 e {4 } m (l, b) = 5 e { 3, 5, 6, 7 },m(2, a) = 3


25/48

b

1.3.2 Automate cu stiv (push-down)

Definiia 1.3.5. Se numete automat cu stiv un obiect matematic definit n modul urmtor:P = (Q, T, Z, m, qO, zO, F) unde:

Q - este o mulime finit de simboli ce reprezint strile posibile pentru unitatea decontrol a automatului;

T - este mulimea finit a simbolilor de intrare; Z - este mulimea finit a simbolilor utilizai pentru stiv; m - este o funcie, m : Q x (T u {X}) x Z -> P(S x Z*) (prin P(Q) s-a notat mulimea

prilor lui Q) este funcia care descrie modul n care se obine starea urmtoare i j

informaia care se introduce n stiv pentru o combinaie (stare, intrare, coninut stiv) |dat; qO s Q este starea iniial a unitii de control; zO e Z este simbolul aflat n vrful stivei n starea iniial; F c Q reprezint mulimea finit a strilor finale.Definiia 1.3.6. O configuraie de stare a automatului este un triplet (q, w, a) e Q x T* x Z*

unde:

q - reprezint starea curent a unitii de control; w - reprezint partea din banda de intrare care nu a fost nc citit. Dac w = Xnseamn

c s-a ajuns la sfritul benzii de intrare; a - reprezint coninutul stivei.

automatului este relaia |- definit asupra mulimii

[ urmtor: (q, aw, za) |- (qF, w, Pa) unde (q1, P) e m(q, a,z ) , q e Q , a e T u { l } , w e T * , z e Z , a e Z * ,f i e Z * .

Dac a * X nseamn c, dac unitatea de control este n starea q, capul de citire este pesimbolul a iar simbolul din vrful stivei este z atunci automatul poate s i schimbeconfiguraia n modul urmtor: starea unitii de control devine q', capul de citire se deplaseazcu o poziie la dreapta iar simbolul din vrful stivei se nlocuiete cu p.

Dac a = X nseamn c avem o A.-tranziie pentru care simbolul aflat n dreptul capului decitire pe banda de intrare nu conteaz (capul de citire nu se va deplasa), ns starea unitii decontrol i coninutul memoriei se pot modifica. O astfel de tranziie poate s aib loc i dup ces-a parcurs ntreaga banda de intrare.

Dac se ajunge ntr-o configuraie pentru care stiva este goal nu se mai pot executa tranziii.44 44

Relaia j- se poate generaliza la |-\ |-*, |-*, ntr-o manier similar relaiei de derivare pentruforme prepoziionale.

Definiia 1.3.8. O configuraie iniial pentru un automat cu stiv este o configuraie deforma (qO, w, zO) unde w e T*. O configuraie final este o configuraie de forma (q, X, a) cu qe F, a e Z*.

Definiia 1.3.9. Spunem c un ir w este acceptat de un automat cu stiv prin stri finaledac (qO, w, zO) |-* (q, X, a) pentru q e F i a e Z * . Mulimea irurilor acceptate de un automatcu stiv se noteaz cu L(P).

Definiia 1.3.10. Spunem c un ir w este acceptat de un automat cu stiv prin stiv goaldac (qO, w, zO) |-* (q, X, X) pentru q e Q. Limbajul acceptat de un automat pushdown P n

acest mod se noteaz cu Le(P).Propoziie. Dac L(P) este limbajul acceptat de automatul P prin stri finale atunci se poate

construi un automat pushdown P' astfel nct L(P) = Le(P').Propoziie. Dac Le(P) este limbajul acceptat de automatul P prin stiv goal atunci se poate

construi un automat pushdown P' astfel nct Le(P) = L(P').Propoziie. Mulimea limbajelor acceptate de automate cu stiv este mulimea limbajelor

independente de context.

Probleme

S se determine limbajul acceptat de urmtorul automat cu stiv:PD = ({qO, ql , q2, q3}, {a, b, c}, {a, b, c, z}, m, qO, z, {q3 })m(qO, a, z) = { (qO, az) }m(qO, a, a) = {(qO, aa)}m(qO,c,a)={(ql,a)}

m(ql,b,a)={(ql,A.)}m(ql ,b,z)={(ql ,bz)}m(ql ,b,b)={(ql ,bb)}m(ql,c,b)={(q2,b)}m(q2,b,b)={(q2,X)}m(q2, X, z) = { (q3, X) }

S;

Soluie:

Evoluia automatului PD pentru un anumit ir de intrare poate fi caracterizat n modulurmtor: din starea iniial qO se poate face o tranziie dac irul ncepe fie cu simbolul a fiecu simbolul c. Se observ c simbolii a sunt introdui n stiv. Fie n numrul de simboli a dinprefixul irului de intrare, deci irul de intrare poate fi de forma: w = a" ev unde n > 0, iar veste un sufix al irului de intrare. n continuare, se trece n starea ql n care poate urma doarsimbolul b n irul de intrare i pentru fiecare simbol b de pe banda de intrare, se descarc unsimbol a din vrful stivei.

45



26/48

Deci, numrul de simboli b care poate urma dup c este tot n, iar w este de forma; w = a"cb n u, u esteun sufix al irului de intrare. Simbolul care poate urma pe banda de intrare n momentul n care stivaeste vid (s-au descrcat toi simbolii a din stiv) este tot b.

n continuare, pot apare doar simbolii b care se introduc n stiv. Fie m numrul acestora.Configuraia n acest moment a prefixului analizat din irul de intrare este: w = a" c b n bm x, unde xeste restul din ir rmas neanalizat. Se observ c din starea ql, dac pe banda de intrare nu urmeazun b, poate urma doar un c. Se trece n starea q2 n care sunt acceptai doar simboli b pe banda deintrare. Ori de cte ori apare un b pe banda de intrare, se descarc un b din vrful stivei. n momentul

n care stiva s-a golit, se trece n starea finala q3. Deci irurile acceptate de automat sunt de forma: w

= a n cb nbm cb m cum,n>0.Pentru irul de intrare aacbbbcb, micrile efectuate de automat sunt:(qO, aacbbbcb, z) |- (qO, acbbbcb, az) |- (qO, cbbbcb, aaz) |- (ql, bbbcb, aaz)

|- (ql, bbcb, az) |- (ql, bcb, z) |- (ql, cb, bz) |- (q2, b, bz)

Hq2,A,z)|-(q3,Aa)

deci irul este acceptat.

prohlcm 1.3-14

S se construiasc automatul cu stiv care accept urmtorul limbaj:L={wcwR|we {a,b}*}

Soluie:Vom folosi n construcia automatului PD care accept limbajul L faptul c irul de intrare estesimetric i are numr impar de simboli, simbolul din centru fiind c. Prin urmare, pentru a puteastabili dac irul de intrare poate fi acceptat sau nu, trebuie memorat prima jumtate a irului (pnse ntlnete simbolul c) n stiv i apoi comparat cu a doua jumtate a irului (vom comparasimbolul analizat n mod curent de pe banda de intrare cu simbolul din vrful stivei; dac sunt egali,se descarc stiva). Prin urmare, automatul cu stiv care accept limbajul L, este: PD = ({qO, ql, q2}, {a,b,c}, {a,b,c,z},m,qO,z, {q2})m(qO,d,e)={(qO,de)} V d e {a ,b} ,Ve e {a,b,z}m(qO,c,d)={(ql,d)}Vde{a,b,z}m(ql,d,d)={(ql,A)}Vde{a,b}m(qU,z)={(q2,A.)}

Comentarii:Se observ ca automatul este determinist i acceptarea este prin stri finale.

Soluie:]vfumrul de simboli 0 este mai mare sau egal dect numrul de simboli 1. Vom proceda n modanalog exemplului precedent introducnd iniial n stiv toi simbolii 0 din prima parte a irului iulterior descrcnd stiva pentru fiecare simbol 1 ntlnit pe banda de intrare. Condiia ca un ir s fieacceptat este ca stiva s nu se goleasc nainte de a ajunge la sfritul irului. Rezult deci automatul:

= ({q0 ,ql ,q2 }, { 0,1 }, { 0,z },m, qO,z, { q2

m(q0,0,a)={(q0,0a)}Vae {O,z}

m(q0,l,0)={(ql,X)}m(ql,l,O)={(ql,X)}m(ql,^a)={(q2,X)}Vae{0,z}

Verificare:Pentru irul de intrare 00011, evoluia automatului este:

(qO, 0001 l,z)i-(q0,0011, Oz)|-(q0,011,00z) j-(qO, ll,000z)|-(ql, l,00z)|-(ql,A,0z)

|-(q2,A,z)

prin urmare irul este acceptat. De asemenea, pentru irul de intrare 011, evoluia automatului este:

funcia de tranziie nu este definit n acest caz, prin urmare irul nu este acceptat (starea ql nu estede acceptare).

Comentarii:Automatul PD este nedeterminist deoarece exist dou tranziii din starea ql nedistinctibile:

S se construiasc automatul cu stiv care accept urmtorul limbaj:L={O i lj |Oc

4647


S l i Verificare:


27/48

Soluie:

Putem construi un automat cu stiv care accept limbajul generat de gramatic prin stiv goal: PD'= ({ qO }, { a, b, c }, { a, b, c, S, A }, m, qO, S, { }), m ( q O , X, S) = { (qO , a S b ) , (qO , a A b) }, m(qO,,A)={(qO,c)} ,m(qO,x,x)={(q(U)}Vxe {a,b ,c}O alt soluie

LFA - Aplicatii

Documents

Transcript of LFA - Aplicatii