Filehost_Limbaje Formale Si Automate- Grigore Albeanu

UNIVERSITATEA SPIRU HARET Facultatea de Matematică-Informatică Platforma BLACKBOARD Codul cursului:

Denumirea cursului: Limbaje formale si automate Tip curs: Obligatoriu Durata cursului / Nr. Credite: semestrul 1 / 4 credite Perioada de accesare a cursului: 1 oct 2006 - 1 oct 2007 Manualul recomandat:

G. Albeanu, Limbaje formale si automate, Editura FRM, 2005 Obiectivul principal al cursului: Dobandirea de cunostinte si competenţe privind generarea şi recunoaşterea limbajelor, operaţiile cu limbaje si analiza sintactica. Modul de stabilire a notei finale: 6u x 3p + 10m x 5p + 4d x 8p = 100p. In final se imparte numărul de puncte la 10 şi se rotujeşte la întreg. ZI - Verificare, se ia în considerare şi activitatea desfăsurată la seminar (50%) FR,ID - examen la calculator (6 întrebări uşoare, 10 întrebări de nivel mediu şi 4 întrebări dificile) cu ponderile de mai sus. Consultaţii pentru studenţi: Marţi, 7.30-16 Adrese e-mail responsabil pentru contactul cu studenţii: [email protected] Titularul/titularii cursului / serie: ZI, FR, ID Prof. Univ. Dr. Albeanu Grigore [email protected] Str. Ion Ghica, Facultatea de matematică-informatică 7.30-16

2. Conţinutul tematic al cursului 1. Limbaje şi expresii regulate 1.1 Alfabet. Cuvânt. Limbaj 1.2 Operaţii cu limbaje 1.3 Mulţimi regulate şi expresii regulate 2. Mecanisme generative fundamentale 2.1 Sisteme de rescriere 2.2 Gramatici formale 2.3 Clase de gramatici 2.4 Arbori de derivare, ambiguitate şi recursivitate 2.5 Complexitatea sintactică a gramaticilor şi limbajelor 3. Mecanisme pentru recunoaşterea automată a mulţimilor regulate 3.1 Automatul finit determinist (AFD) 3.2 Automatul finit nedeterminist (AFN) 3.3 Puterea de acceptare a sistemelor AFD şi AFN 3.4 Automate cu l-deplasări sau sisteme tranziţionale 3.5 Sistemele AFN şi expresiile regulate 4. Optimizarea automatelor finite 4.1 Stări accesibile. Stări utile 4.2 Congruenţe şi limbaje regulate 4.3 Lema de pompare pentru limbaje regulare. Aplicaţii 5. Transformări asupra gramaticilor formale 5.1 Transformări elementare 5.2 Redenumiri şi l-producţii

5.3 Simboluri utile 6. Forme normale. Lema Bar-Hillel 6.1 Forma normală Chomsky 6.2 Forma normală Greibach 6.3 Lema Bar-Hillel 7. Gramatici şi automate 7.1 Gramatici liniare şi limbaje regulate 7.2 Automate pushdown 7.3 Limbaje independente de context şi automate pushdown 7.4 Maşini Turing şi automate liniar mărginite 8. Proprietăţi de închidere 8.1 Familia limbajelor regulate 8.2 Familia limbajelor independente de context 9. Specificarea sintaxei limbajelor de programare 9.1 Limbajul C++ 9.2 Limbajul Prolog 9.3 Limbajul XML 10. Introducere în analiza sintactică 10.1 Problema recunoaşterii 10.2 Analiza sintactică descendentă 10.3 Analiza sintactică ascendentă 3. Bibliografie minimă obligatorie

1. G. Albeanu, Limbaje formale si automate, Editura FRM, 2005.

4. Bibliografie facultativă

2. Jucan Toader, Andrei Stefan, Limbaje formale şi teoria automatelor, Universitatea “Al. I. Cuza”, Iaşi, 2002. 3. Atanasiu A., Mateescu Al., Limbaje formale, Culegere de probleme, Universitatea din Bucureşti, 1990. 4.Hopcroft, J.E., Ullman, J.D., Introduction to Automata Theory, Languages and Computation, Addison Wesley Publishing Company, 1979. 5. Prezentarea lecţiei: Materialul este organizat în 10 capitole, conform programei 6. Aplicaţii: Secţiunea de aplicaţii este constituita din toate exemplele, observaţiile şi comentariile prezente în manual. 7. Exemple de teste de autoevaluare: Testele de autoevaluare conţin exerciţii şi probleme precum in LFA_teste_autoevaluare.pdf 8. Evaluarea computerizată sub forma de teste de tip grilă: Se vor include teste similare celor prezentate in cadrul secţiunilor de aplicaţii, teste de autoevaluare şi LFA_lista_probleme_propuse.pdf.

1. Limbaje şi expresii regulate

1.1 Alfabet. Cuvânt. Limbaj

Definiţia 1.1 [Alfabet] Un alfabet este o mulţime finită şi nevidă ale cărei elemente sunt numite simboluri (litere). Notaţie Alfabetele se vor nota prin semne precum: V, VN, VT, Σ etc. Definiţia 1.2 [Cuvânt] Fie Σ = a1, a2, ..., an un alfabet, unde n este un număr natural nenul (n ≥ 1). Orice secvenţă x = ai1ai2...air, aij ∈ Σ, 1 ≤ j ≤ r, se numeşte cuvânt (şir, frază) peste Σ. Lungimea cuvântului x se notează cu |x| şi este egală cu r. Convenim să considerăm şi cuvântul “format” cu zero simboluri pe care-l notăm cu λ şi îl numim cuvântul vid sau şirul nul. Notaţii Mulţimea tuturor cuvintelor peste Σ se notează cu Σ*, iar mulţimea tuturor cuvintelor nenule, Σ*-λ, se notează cu Σ+. Observaţia 1.1 Mulţimea Σ* este monoid în raport cu operaţia de concatenare a cuvintelor definită prin xy = ai1ai2...airaj1aj2...ajs, dacă x = ai1ai2...air, y = aj1aj2...,ajs, aip∈Σ (1 ≤ p ≤ r) şi ajq ∈Σ (1 ≤ q ≤ r). Observaţia 1.2 Dacă Σ0 = λ, Σ2 = ΣΣ (mulţimea cuvintelor de lungime 2), Σ3 = Σ2Σ (mulţimea cuvintelor de lungime 3), Σn = Σn-1Σ (mulţimea cuvintelor de lungime n; n>1), atunci

a) Σ* = ; U0≥

Σk

k

b) Σ+ = . U1≥

Σk

k

Definiţia 1.3 Orice submulţime L de cuvinte peste Σ, L ⊆ Σ*, se numeşte limbaj peste Σ.

1.2 Operaţii cu limbaje Limbajele fiind mulţimi, operaţiile obişnuite ale teoriei mulţimilor acţionează şi asupra acestora. Pentru alfabetul Σ fixat, au sens reuniunea, intersecţia, complementara (faţă de Σ*) şi diferenţa limbajelor. Aceste operaţii vor fi notate, în mod uzual, prin ∪, ∩, C şi -. Definiţia 1.4 [Concatenarea, Produsul] Fie L1 (peste Σ1) şi L2 (peste Σ2) limbaje . Atunci L1L2 = uv| u ∈L1, v ∈L2 se numeşte concatenarea sau produsul limbajelor L1 şi L2. Observaţia 1.3 Lλ=λL=L; L∅ = ∅L = ∅, pentru oricare limbaj L, unde ∅ este limbajul vid.

Definiţia 1.5 [Închiderea Kleene] Fie L ⊆ Σ*. Închiderea Kleene a limbajului L este limbajul

L* = , U0≥k

kL

unde L0 = λ, Ln+1 = Ln L, n≥0.

Notaţie [Închiderea pozitivă]

L+ = U . 1≥k

kL

Observaţia 1.4 Dacă L este un limbaj λ-liber (nu conţine cuvântul vid) atunci L+=L*-λ. Definiţia 1.6 [Subcuvânt, Prefix, Sufix, Răsturnat] Fie şirurile x, y ∈ Σ* şi x = ai1ai2...air. Dacă există u, v ∈Σ* astfel încât y = uxv, spunem că x este subcuvânt (subşir) al lui y. Dacă există v ∈Σ* astfel încât y = xv atunci x este prefix al lui y, iar dacă există u ∈Σ* astfel încât y = ux, atunci x este sufix al lui y. Şirul Răsturnat(x) = air...ai2ai1, se numeşte răsturnatul (oglinditul) lui x. Notaţii Pentru un şir y ∈Σ*, notăm prin Sub(y), Pref(y), Suf(y) mulţimea subcuvintelor, prefixelor şi, respectiv, a sufixelor cuvântului y. Definiţia 1.7 [Extinderea operaţiilor Sub, Pref şi Suf asupra limbajelor] Fie L ⊆Σ*. Atunci

Sub(L) = ; Pref(L) = ; Suf(L) = . ULx

x∈

)(Sub ULx

x∈

)(Pref ULx

x∈

)(Suf

Observaţia 1.5 În mod similar, se poate defini răsturnatul (oglinditul) limbajului L. Definiţia 1.8 [Substituţia] Fie ansamblul (U, V, s), unde U, V sunt alfabete, iar s : V → P(U*) este o aplicaţie oarecare. Aplicaţia s extinsă la V* prin s(λ)=λ, s(xy)=s(x)s(y), x, y ∈ V*, iar apoi la limbaje, se numeşte substituţie. Definiţia 1.9 [Substituţia finită. Homomorfismul] În condiţiile definiţiei 1.8,

a) dacă s(a) este o mulţime finită, pentru orice a ∈ V, atunci s se numeşte substituţie finită.

b) dacă s(a) are exact un element pentru fiecare a din V, atunci s este un homomorfism şi scriem s(a) = x, în loc de s(a) = x.

c) dacă s(a) nu conţine cuvântul vid, pentru orice a din V, atunci s este substituţie λ-liberă, sau homomorfism λ-liber (când este cazul).

Dacă h:V*→U* este un homomorfism, atunci aplicaţia g: U*→V*, definită prin g(y)=x∈V*|h(x)=y, pentru oricare y∈U*, este homomorfism invers pentru h. Propoziţia 1.1 [Levi] Fie Σ un alfabet şi x, y, u, v ∈ Σ*. Dacă xy = uv atunci

a) |x| > |u| ⇒ există w ∈ Σ*, x = uw şi v = wy; b) |x| = |u| ⇒ x = u şi y = v; c) |x| < |v| ⇒ există w ∈ Σ*, u = xw şi y = wv.

Propoziţia 1.2 [Σ* este mulţime numărabilă] Dacă Σ este un alfabet, atunci Σ* este mulţime numărabilă.

Definiţia 1.10 [Mulţimi închise la operaţii] Fie U o mulţime univers şi funcţia f : U → U. O mulţime A ⊆ U este închisă faţă de f, sau în raport cu f, dacă şi numai dacă pentru oricare x ∈ A rezultă f(x) ∈ A. Propoziţia 1.3 [Închiderea unei mulţimi B în raport cu o operaţie f – cea mai mică mulţime închisă la operaţia f şi care conţine mulţimea B]. Fie mulţimea univers U, funcţia f : U → U şi B ⊆ U . Construim, în mod inductiv, şirul de mulţimi:

A0 = B; Ak+1 = Ak ∪ f(x) | x ∈ Ak, k ∈ N şi A = . Atunci: UNk

kA∈

a) A este închisă faţă de f; b) Dacă mulţimea C este astfel încât B ⊂ C ⊆ U şi este închisă faţă de f atunci A⊆C.

1.3 Mulţimi regulate şi expresii regulate Definiţia 1.11 [Mulţimi regulate] Fie Σ un alfabet. Familia mulţimilor regulate peste Σ este definită recursiv astfel:

(1) (∀L) ((L⊆Σ* şi card L < ∞) ⇒ L este mulţime regulată peste Σ). Se includ aici mulţimea vidă şi mulţimea formată doar cu şirul nul λ.

(2) Dacă A şi B sunt mulţimi regulate peste Σ atunci A∪B (reuniunea) şi AB (produsul) sunt mulţimi regulate peste Σ.

(3) Dacă A este mulţime regulată peste Σ atunci A* este mulţime regulată peste Σ.

(4) Singurele mulţimi regulate peste Σ sunt cele obţinute prin aplicarea regulilor 1)-3).

Observaţia 1.6 [Familie închisă la operaţiile: reuniune, produs şi *] Familia mulţimilor regulate peste Σ este cea mai mică clasă care conţine toate mulţimile finite de cuvinte peste Σ şi este închisă la reuniune, produs şi *. Definiţia 1.12 [Mulţimea expresiilor regulate] Fie Σ un alfabet. Mulţimea expresiilor regulate peste Σ este (prin definire recursivă) compusă astfel:

a) ∅ şi λ sunt expresii regulate; b) a este o expresie regulată pentru oricare a ∈Σ; c) dacă r şi s sunt expresii regulate atunci (r+s), (rs) şi (r*) sunt expresii

regulate; d) singurele expresii regulate sunt cele obţinute prin regulile a-c.

Definiţia 1.13 [Limbajul unei expresii regulate numit şi limbaj regulat] Fie r o expresie regulată peste alfabetul Σ. Limbajul L(r), desemnat de expresia r, este obţinut astfel: L(∅) = ∅; L(λ)=λ, L(a) = a; L(r+s)=L(r)∪L(s); L(rs)=L(r)L(s) şi L(r*) =(L(r))*. Observaţia 1.7

a) Dacă presupunem că ordinea operaţiilor (pe baza priorităţii de aplicare) este *, ., + atunci se poate renunţa la paranteze.

b) Din definţia expresiilor regulate, rezultă că o mulţime este regulată peste Σ dacă şi numai dacă coincide cu limbajul unei expresii regulate peste Σ.

c) Pentru o mulţime regulată pot exista mai multe expresii regulate echivalente. Două expresii regulate r1 şi r2 sunt echivalente (scriem r1 ∼ r2) dacă şi numai dacă L(r1) = L(r2).

Propoziţia 1.4 [Identităţi cu expresii regulate] Fie r, s şi t expresii regulate peste Σ. Atunci:

a) r + s ∼ s + r, r + ∅ ∼ ∅ + r, r + r ∼ r, (r + s) + t ∼ r + (s + t); b) rλ ∼ λr ∼ r, r∅ ∼ ∅r ∼ ∅, (rs)t ∼ r(st); în general, comutativitatea produsului

nu are loc. c) r(s + t) ∼ rs + rt, (s + t)r ∼ sr + tr; d) r* ∼ r*r* ∼ (r*)* ∼ (λ+r)*, ∅* ∼ λ* ∼ λ; e) r* ∼ λ + r + r2 + r3 + … + rk + rk+1r*, pentru k ≥0. f) (r+s)* ∼ (r* +s*)* ∼ (r*s*)* ∼ (r*s)*r* ∼ r*(sr*)*. Expresiile (r+s)* şi r*+s*

nu sunt, în general, echivalente. g) r*r ∼ rr*, r(sr)* ∼ (rs)*r; h) (r*s)* ∼ λ + (r + s)*s, (rs*)* ∼ λ + r(r + s)*; i) Dacă λ∉L(s) atunci ((r ∼ sr + t) ⇔ r∼s*t ) şi ((r ∼ rs + t) ⇔ r ∼ ts*).

2. Mecanisme generative fundamentale

2.1 Sisteme de rescriere

Definitia 2.1 [Sistem de rescriere] Fie V un alfabet şi P⊂V* x V* o mulţime finită de perechi numite reguli de rescriere. Ansamblul SR = (V, P) se numeşte sistem de rescriere. Definiţia 2.2 [Generare (derivare) directă, lungimea unei derivări] Fie SR = (V, P), iar α şi β cuvinte peste V. Atunci:

a) α generează direct β (şi se notează α β) dacă şi numai dacă există şirurile u, v, x şi y astfel încât u ∈ Pref(α) ∩ Pref(β), v ∈ Suf(α) ∩ Suf(β), α = uxv, β = uyv, iar (x, y) ∈ P.

→

b) α generează1 β (şi se notează α β) dacă şi numai dacă există cuvintele peste V, α

→*

0 = α, α1, α2, …, αk-1, αk = β, k ≥ 0, iar αi generează direct αi+1, 0 ≤ i ≤ k-1.

Se spune că şirul α0, α1, α2, …, αk-1, αk formează o derivare pentru β pornind de la şirul α. Numărul k este lungimea derivării. Definiţia 2.3 [Metodă generativă] Fie V o mulţime de simboluri, Σ ⊂ V un alfabet, A ⊂ V* o mulţime de şiruri peste V, numite axiome. Structura Mg(L) se numeşte metodă generativă pentru limbajul L, peste Σ, dacă Mg(L) = (SR, A, Σ), unde SR = (V, P) este un sistem de rescriere, iar L = w ∈Σ* | există α ∈ A astfel încât α generează w.

2.2. Gramatici formale Definiţia 2.4 [Gramatică formală] Ansamblul G = (Ω, Σ, S, P) se numeşte gramatică formală dacă Ω este o mulţime nevidă şi finită de simboluri, numite neterminale, Σ este o mulţime nevidă şi finită de simboluri, numite terminale, astfel încât Ω ∩ Σ = ∅, S este un neterminal cu rol de axiomă, iar P este o mulţime de perechi2 (p, q), notate şi sub forma p ::= q, unde p ∈ (Ω∪Σ)*Ω(Ω∪Σ)* şi q ∈ (Ω∪Σ)*. Relaţiile → şi sunt valabile şi pentru cuvintele peste Ω ∪ Σ. Orice cuvânt peste Ω ∪ Σ care poate fi generat din S, se numeşte formă propoziţională în gramatica G. Fie FP(G) mulţimea formelor propoziţionale ale lui G. Limbajul generat de gramatica G este L(G) = w | w ∈ Σ*, S w, adică L(G) = FP(G) ∩ Σ*.

→*

→*

Notaţie Dacă sunt mai multe reguli cu acelaşi cuvânt în partea stângă: (p, q1), (p, q2), …, (p, qm), atunci convenim să notăm această submulţime de reguli (sau p-reguli) sub forma: p ::= q1 | q2 | … | qm. De asemenea, notăm prin V mulţimea tuturor simbolurilor gramaticii G, adică V = Ω ∪ Σ.

1 Prin s-a notat închiderea reflexivă şi tranzitivă a relaţiei binare →. →*

2 O pereche (p, q) se numeşte regulă de rescriere sau producţie; p reprezintă membrul stâng, iar q este membrul drept al producţiei (p, q).

Observaţia 2.1 Ansambul SR = (Ω ∪ Σ, P) este un sistem de rescriere pentru limbajul L(G) pornind de la şirul S. Metoda de generare pentru L(G) poate fi specificată prin structura (SR, S, Σ). Definiţia 2.5 [Gramatici echivalente] Fie Gi = (Ωi, Σ, Si, Pi), i = 1, 2. Spunem că G1 şi G2 sunt echivalente dacă L(G1) = L(G2).

2.3. Clase de gramatici Definiţia 2.6 [Ierarhia lui N. Chomsky] O gramatică G = (Ω, Σ, S, P) este de tip i, 0 ≤ i ≤ 3, dacă sunt verificate restricţiile (i) asupra regulilor din P:

(i) Caracterizarea regulilor de rescriere Denumire (0) Nici o restricţie. Conform definiţiei 2.4. Gramatici generale (1) Regulile sunt de forma uxv ::= uyv, u, v

∈V*, x ∈ Ω, y ∈ V+ sau de forma S ::= λ, astfel încât S nu apare în membrul drept al niciunei reguli.

Dependente de context (eng. Context-sensitive) sau monotone

(2) Regulile sunt de forma x ::= y, x ∈ Ω, y ∈ V*.

Independente de context (eng. Context-free)

Regulile sunt de forma x ::= wy sau x ::= w, unde x, y ∈ Ω, w ∈ Σ*.

Liniare la dreapta (eng. Right linear) (3)

Regulile sunt de forma x ::= yw sau x ::= w, unde x, y ∈ Ω, w ∈ Σ*.

Liniare la stânga (eng. Left linear)

Un limbaj L este de tipul i dacă există o gramatică G de tipul i astfel încât L= L(G). Observaţia 2.2 Fie £i familia limbajelor de tipul i. Se observă imediat că £0 ⊃ £1 şi £2 ⊃ £3. De asemenea este adevărat că £1 ⊃ £2, dar justificarea nu este imediată. Propoziţia 2.1 Pentru orice gramatică de tip 2, G = (Ω, Σ, S, P) , dacă AB w, atunci există w

→*

1, w2 ∈ V* astfel încât: 1) w = w1w2 şi 2) A w→*1, B w→*

2. Propoziţia 2.2 Pentru orice gramatică de tip 2, G = (Ω, Σ, S, P), există o gramatică echivalentă G’ = (Ω’, Σ, S, P’), de tip 2, în care toate producţiile lui P’ care conţin terminale sunt de forma A ::= a, a ∈ Σ. Propoziţia 2.3 Orice gramatică liniară la dreapta este echivalentă cu o gramatică de acelaşi tip, dar cu reguli de forma: A ::= aB sau A ::= a, unde A, B ∈ Ω, iar a ∈ Σ ∪ λ. Propoziţia 2.4 Fie G o gramatică liniară la stânga, există o gramatică liniară la stânga G’ astfel încât L(G’) = L(G), iar regulile gramaticii G’ sunt numai de forma A ::= Ba şi A ::= a, unde A, B ∈ Ω, iar a ∈ Σ ∪ λ. Propoziţia 2.5 Fie G o gramatică în care producţiile sunt de forma A ::= Ba şi A ::= a. Atunci există o gramatică G’ echivalentă cu G pentru care producţiile sunt de forma A ::= aB şi A ::= a.

Observaţia 2.3 Propoziţiile anterioare arată echivalenţa dintre gramaticile liniare la stânga şi cele liniare la dreapta. Nu trebuie crezut că dacă o gramatică are pe lângă reguli de tipul A ::= a, atât reguli de forma A ::= aB, cât şi reguli de forma C ::= Db, ea va fi echivalentă cu o gramatică liniară la stânga (sau la dreapta). De exemplu, gramatica cu regulile S ::= aA | aB; A ::= Sb; B ::= b generează un limbaj de tip 2 şi nu unul de tip 3 aşa cum ar părea la prima vedere.

2.4 Arbori de derivare, ambiguitate şi recursivitate Atât pentru gramatici independente de context cât şi pentru gramatici liniare (la stânga sau la dreapta) modul prin care o formă propozitională poate fi obţinută, prin derivare, poate fi reprezentat grafic cu ajutorul structurilor arborescente.

Fie D = (X, A) un digraf (graf orientat): dacă (x, y) ∈ A atunci x este predecesorul lui y, iar y este succesorul lui x. Arborii ordonaţi sunt digrafuri conexe şi fără circuite cu proprietăţile:

a) Există, în D, un unic nod, numit rădăcină care nu are predecesori şi de la care există un drum la fiecare nod al digrafului;

b) Orice nod, altul decât rădăcina, are exact un predecesor; c) Mulţimea succesorilor oricărui nod este ordonată.

Arborii orientaţi se desenează cu rădăcina în sus, iar ordinea succesorilor unui nod este de la stânga la dreapta. Se înţelege că sensul arcelor este de sus în jos; astfel nu mai este nevoie de săgeţi. Nodurile cu descendenţi din D sunt noduri interioare, iar celelalte se numesc noduri terminale sau frunze. Definiţia 2.7 [Arbore de derivare] Fie G = (Ω, Σ, S, P) o gramatică de tip cel puţin 2. Un arbore de derivare pentru G este un arbore ordonat D = (X, A) împreună cu o funcţie de etichetare f : X → Ω ∪ Σ ∪ λ cu proprietăţile:

1) f(r) = S, dacă r este rădăcina arborelui; 2) Dacă x ∈ X atunci f(x) ∈ Ω; 3) Dacă x are descendenţii x1, x2, …, xn, în această ordine, atunci P conţine

regula de rescriere f(x) ::= f(x1)f(x2)…f(xn). 4) Dacă f(x) = λ, x nu are descendenţi (este frunză).

Un subarbore al unui arbore de derivare, este un nod particular al arborelui (care devine rădăcină pentru subarbore) împreună cu toţi descendenţii lui. Dacă rădăcina subarborelui are eticheta A atunci acesta este numit A-arbore. Arborele de derivare pentru gramatica G este un S-arbore. Ordinea descendenţilor unui nod în arborele de derivare induce o ordine în mulţimea frunzelor arborelui de derivare. Cuvântul obţinut din etichetele frunzelor arborelui de dervare, în ordinea indusă, se numeşte frontiera arborelui. Frontiera unui arbore de derivare este o formă propoziţională a gramaticii G, mai mult, frontiera unui A-arbore este un cuvânt α peste Ω ∪ Σ astfel încât A

α. →*

Propoziţia 2.6 Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Oricare ar fi A ∈ Ω, α ∈ (Ω ∪ Σ)*, A α dacă şi numai dacă există un A-arbore cu frontiera α.

→*

Observaţia 2.4 Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Atunci α ∈ L(G), adică S α, dacă şi numai dacă există un arbore de derivare (S-arbore) cu frontiera α.

→*

Definiţia 2.8 [Derivare extrem stânga/dreapta] Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Dacă într-o derivare în gramatica G, la fiecare pas este aplicată o producţie celui mai din stânga (resp. dreapta) neterminal atunci derivarea se numeşte extrem3 stânga (resp. dreapta). Observaţia 2.5 Fie G = (Ω, Σ, S, P) o gramatică independentă de context şi w∈ L(G), deci există un arbore de derivare cu frontiera w.

a) Evident, se poate pune în evidenţă o derivare extrem stânga (resp. dreapta) pentru w din S. Totuşi, pentru un anumit cuvânt pot exista mai multe derivări extrem stânga (resp. dreapta), ceea ce denotă o ambiguitate în procesul de generare.

b) Pentru orice cuvânt w∈ L(G), numărul de derivări extrem stânga pentru w este egal cu numărul de derivări extrem dreapta.

Definiţia 2.9 [Gramatică ambiguă] Fie G = (Ω, Σ, S, P) o gramatică independentă de context. G se numeşte ambiguă dacă există w∈L(G) cu cel puţin două derivări extrem stânga (resp. dreapta) distincte. Un limbaj L nu este ambiguu dacă poate fi generat de o gramatică care nu este ambiguă. Dacă orice gramatică care generează L este ambiguă atunci se spune că L este inerent ambiguu. Observaţia 2.6 Orice gramatică independentă de context care conţine, printre regulile sale de rescriere, producţii de unul din tipurile (1)-(4), cu neterminalul A util in generarea de cuvinte peste Σ, este ambiguă: (1) A ::= AA; (2) A ::= AγA; (3) A ::= αA | Aβ; (4) A ::= αA | αAβA. Definiţia 2.10 [Recursivitate] Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Un neterminal A ∈ Ω este numit recursiv la stânga (resp. dreapta) dacă A

Aα, (resp. A αA), α ∈ (Ω∪Σ)*. O gramatică este recursivă la stânga (resp. la dreapta) dacă mulţimea simbolurilor neterminale conţine cel puţin un simbol recursiv la stânga (resp. la dreapta).

→* →*

Propoziţia 2.7 Fie G = (Ω, Σ, S, P) o gramatică independentă de context, iar A ∈ Ω cu proprietatea că există o producţie de forma A ::= Aα. Atunci există o gramatică G’ echivalentă cu G care pentru orice A-regulă A ::= β avem A ∉ Pref(β).

2.5 Complexitatea sintactică a gramaticilor şi limbajelor Un limbaj, în general, poate fi generat de către foarte multe gramatici distincte. Pentru aplicaţii practice trebuie utilizate gramatici cât mai simple. În cele ce urmează se consideră complexitatea statică a gramaticilor (mărimea şi structura gramaticilor.)

3 În unele publicaţii se omite cuvântul “extrem”, folosindu-se noţiunile de derivare stânga (resp. dreapta) în acepţiunea definiţiei 2.8.

Definiţia 2.11 [Măsurarea complexităţii sintactice] Fie G o clasă de gramatici şi fie L(G) familia limbajelor generate de gramaticile din clasa G. O măsură a complexităţii gramaticilor din clasa G este o aplicaţie ψ : G → N. Complexitatea sintactică a limbajelor din familia L(G) este

ψ(L) = min ψ(G) | L = L(G), G ∈ G, L ∈ L(G). Definiţia 2.12 [Măsurile Var, Prod şi Simb]

Fie G = (Ω, Σ, S, P) o gramatică independentă de context (G ∈ G2). Definim următoarele măsuri de complexitate statică:

a) Var : G2 → N, Var(G) = |Ω|, b) Prod : G2 → N, Prod(G) = |P|; c) Simb : G2 → N, Simb(G) = Σ Simb(r) | r ∈ P, unde Simb(r) = |x|+2, dacă r

este regula A ::= x. Definiţia 2.13 [Indexul limbajelor independente de context] Fie Fie G = (Ω, Σ, S, P) o gramatică independentă de context (G ∈ G2) şi derivarea D: S = w0 → w1 → … → wk. Fie N(wi) numărul de apariţii ale simbolurilor din Ω în şirul wi. Indexul derivării D, în gramatica G, este

Index(D, G) = N(wki≤≤1

max i).

Fie x ∈ L(G) şi D(x) mulţimea derivărilor lui x din S, în gramatica G. Indexul şirului x în raport cu gramatica G este

Index (x, G) = Index(D, G). )(

minxDD∈

Indexul gramaticii G este Index(G) = sup Index(x, G), x ∈ L(G).

Măsurile prezentate pot fi extinse şi la clase de limbaje. Asupra unei măsuri ψ a complexităţii sintactice statice a gramaticilor şi limbajelor, dintr-o anumită clasă G, se pun, în mod natural, următoarele probleme.

a) Pentru G oarecare din clasa G: P1: Se poate determina ψ(G)? P2: Se poate determina ψ(L(G))? P3: Se poate decide dacă ψ(G) = ψ(L(G))? P4: Se poate construi o gramatică echivalentă G’ astfel încât ψ(G’) = ψ(L(G))

b) P5: Pentru n arbitrar, dar nenul, se poate decide algoritmic dacă ψ(L(G)) = n ?

Evident, P1 are răspuns afirmativ, dar P2 – P5 au răspuns negativ (conform Păun(1984).) Propoziţia 2.8 [Gruska(1967)] Pentru oricare n ≥ 1, există Ln ⊆ a, b*, Ln limbaj de tip 3, astfel încât Var(Ln) = n. Definiţia 2.14 [Limbajul D1] Limbajul D1 este limbajul generat de gramatica4 G = (S, a, b, S, P) unde P = (S, SS); (S, λ), (S, aSb). Propoziţia 2.9 [Salomaa(1969)] Limbajul D1 are indexul infinit în raport cu gramaticile independente de context.

4 Această gramatică este echivalentă cu o gramatică G’ independentă de context (după eliminare λ-producţiilor).

3. Mecanisme pentru recunoaşterea automată a

mulţimilor regulate

3.1 Automatul finit determinist (AFD) Definiţia 3.1 [AFD] Un sistem AFD (automat finit determinist) este o structură M = (Q, Σ, δ, q0, F) unde: Q este o mulţime finită şi nevidă de elemente numite stări; Σ este un alfabet (numit, de intrare); δ : QxΣ → Q este o funcţie parţială (parţial definită), numită funcţie de tranziţie; q0 ∈ Q este starea iniţială a automatului M şi F ⊆ Q este o mulţime nevidă, numită mulţimea stărilor finale. Observaţia 3.1 [Diagrama de tranziţie] Unui sistem AFD i se poate asocia un digraf (o diagramă de tranziţie) astfel:

• nodurile digrafului sunt stările automatului (corespund elementelor mulţimii Q);

• dacă δ(q, a) = p atunci, în digraf, există un arc de la nodul q la nodul p, etichetat cu simbolul a;

• digraful nu conţine alte noduri şi alte arce în afara celor specificate mai sus. Definiţia 3.2 [Extinderea funcţiei δ ] Fie δ^ : QxΣ* → Q definită prin: δ^(q,λ) = q, pentru oricare q ∈ Q; δ^(q,a) = δ(q,a), pentru oricare q∈Q şi oricare a ∈ Σ; δ^(q, wa) = δ(δ^(q, w), a), pentru oricare q ∈ Q, a ∈ Σ şi w ∈ Σ*. Deoarece δ^(q, a) = δ(q, a), pentru oricare a ∈ Σ se poate nota δ^ tot cu δ, fără nici o confuzie. Propoziţia 3.1 Cu notaţiile de mai sus, δ(q, uv) = δ(δ(q,u), v), pentru oricare u, v ∈ Σ*. Definiţia 3.3 [Limbaj acceptat de sisteme AFD] Fie M =(Q, Σ, δ, q0, F) un AFD. Limbajul acceptat de M, notat L(M), este: L(M) = u | u ∈Σ*, δ(q0, u) ∈ F.

3.2 Automatul finit nedeterminist (AFN) Definiţia 3.4 [AFN] Un sistem AFN (automat finit nedeterminist) este o structură N = (Q, Σ, δ, q0, F), unde Q, Σ, q0 şi F au semnificaţia din definiţa 3.1, iar δ : QxΣ → P(Q), unde P(Q) reprezintă mulţimea submulţimilor lui Q (adesea notată prin 2Q). Observaţia 3.2 [Diagrama de tranziţie] Diagrama de tranziţie (digraful asociat) se obţine precum în observaţia 3.1. Definiţia 3.5 [Extinderea funcţiei de tranziţie] Fie δ^ : QxΣ* → P(Q) astfel:

δ^(q, λ) = q; δ^(q, wa) = p | există r ∈ δ^(q, w), p ∈ δ(r,a). Dacă w = λ, obţinem δ^(q, a) = δ(q, a), oricare a ∈ Σ. Astfel, se poate nota δ^ tot cu δ, fără nici o confuzie.

Observaţia 3.3 Pentru utilizarea sistemelor AFN în recunoaşterea limbajelor se extinde δ la nivelul mulţimii P(Q)xΣ*, astfel încât pentru orice u ∈ Σ* au loc relaţiile: δ(∅, u) = ∅; δ(P, u) = , oricare P ⊆ Q, P ≠ ∅. U

Pq

uq∈

),(δ

Definiţia 3.6 [Limbaj acceptat de sisteme AFN] Fie N un sistem AFN ca în definiţia 3.4. Limbajul acceptat de N este: L(N) = w | w ∈ Σ*, δ(q0, w) ∩ F ≠ ∅.

3.3 Puterea de acceptare a sistemelor AFD şi AFN Propoziţia 3.2 Orice limbaj acceptat de un AFD este acceptat de un AFN. Propoziţia 3.3 Fie L un limbaj acceptat de un AFN. Atunci există un AFD, notat cu M, astfel încât L(M) = L. Teorema 3.1 Automatele finite nedeterministe au aceeaşi putere de acceptare ca automatele finite deterministe. Sistemele AFN şi AFD sunt echivalente din punct de vedere al clasei limbajelor acceptate.

3.4 Automate cu λ-deplasări sau sisteme tranziţionale Definiţia 3.7 [Sistem tranziţional] Un automat cu λ-deplasări sau sistem tranziţional, este o structură λN = (Q, Σ, δ, q0, F) în care Q, Σ, q0 şi F au semnificaţia din definiţia 3.4, iar funcţia de tranziţie este definită astfel: δ : Qx(Σ ∪ λ) → P(Q), adică maşina finită permite λ-deplasări. Diagrama de tranziţie are arcele etichetate cu elemente din Σ ∪ λ. Notaţie Dacă p ∈ δ(q, λ) scriem q → [λ]p. Fie , închiderea reflexivă şi tranzitivă a relaţiei →[λ]. Notăm prin λ(q) mulţimea stărilor în care ajunge maşina efectuând λ-deplasări, pornind din q. Mai precis, λ(q) = p ∈ Q| q p şi extindem notaţia pentru mulţimi de stări adică λ(P)= , oricare P ⊆ Q.

][* λ→

UPq

q∈

)(λ][* λ→

Observaţia 3.4 Fie λN = (Q, Σ, δ, q0, F) un sistem tranziţional. Funcţia δ poate fi extinsă la cuvinte peste Σ, prin funcţia δ^ astfel:

a) δ^(s, λ) = λ(s), oricare s∈Q; b) Dacă α ∈ Σ* şi a ∈ Σ atunci δ^(s, αa) = λ(P), unde P = p | există r ∈ δ^(s, α),

p ∈ δ(r,a). c) δ(P, a)= ; δ^(P, α) = , P ⊆ Q, a ∈ Σ, α ∈ Σ* U

Pq

aq∈

),(δ UPq

q∈

),( αδ

d) δ^(s, αa)=λ(δ(δ^(q,α), a), deci este necesară distincţia între δ şi δ^. Definiţia 3.8 [Limbaj acceptat de un sistem tranziţional] Fie λN = (Q, Σ, δ, q0, F) un sistem tranziţional. Limbajul acceptat de λN este L(λN) = α | α ∈ Σ*, δ^(q0, α) ∩ F ≠ ∅. Propoziţia 3.4 Fie L un limbaj peste Σ acceptat de un sistem tranziţional, notat cu λN. Atunci există un AFN, notat cu N, astfel încât L(N) = L (= L(λN)). Reciproca este, în mod banal, adevărată.

3.5 Sistemele AFN şi expresiile regulate Propoziţia 3.5 Fie r o expresie regulată. Atunci există un AFN care recunoaşte limbajul L(r). Propoziţia 3.6 Dacă L este un limbaj acceptat de un AFD atunci L este o mulţime regulată. Teorema 3.2 Un limbaj este regulat dacă şi numai dacă este recunoscut de un AFN (deci şi de un AFD). Teorema 3.3 [Kleene] Familia limbajelor regulate este cea mai mică familie de limbaje care conţine limbajele finite şi este închisă la reuniune, produs (concatenare) şi la operaţia * (închiderea Kleene).

4. Optimizarea automatelor finite

4.1 Stări accesibile. Stări utile

Definiţia 4.1 [Stări accesibile, stări utile] Fie M = (Q, Σ, δ, q0, F) un AFD. O stare q ∈ Q este accesibilă din q0 dacă există un cuvânt w ∈Σ* astfel încât δ(q0, w) = q. O stare se numeşte inaccesibilă dacă nu este accesibilă. O stare q este utilă dacă există un cuvânt w ∈ Σ* astfel încât δ(q, w) ∈ F. O stare este inutilă dacă nu este utilă. Algoritmul 4.1 [Determinarea stărilor accesibile1] Prin aplicarea strategiei greedy, putem obţine un şir ascendent de mulţimi cu stări accesibile, majorat în sensul relaţiei de incluziune de mulţimea stărilor automatului considerat. Fie S0 = q0. Pentru i ≥ 0, formăm Si+1 = Si ∪ q ∈ Q - Si| există s ∈ Si şi a ∈ Σ astfel încât δ(s, a) = q. O altă modalitate de construire a şirului ascendent utilizează relaţia de recurenţă: Si+1 = Si ∪ δ(s, a) | s ∈ Si, a ∈ Σ.

Este clar că trebuie să existe k0, k0 ≤ |Q| astfel încât Sk0 = Sk0+1, k0 fiind cel mai mic număr natural cu această proprietate; în aceste condiţii Sk0+j = Sk0, oricare j ≥ 1. Mulţimea stărilor accesibile este Sk0.

Intrare: Q, Σ, q0, δ, F Ieşire: Q’ – mulţimea stărilor accesibile SEQ

1. i := 0; S0 := q0; 2. do Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i+1; while(Si – Si-1 ≠ ∅); 3. Q’ = Si.

END. Propoziţia 4.1

Cu notaţiile de mai sus, următoarele afirmaţii sunt adevărate: a) q este stare accesibilă dacă şi numai dacă q ∈ Q’; b) Dacă |Q| = m, iar |Σ| = n, atunci complexitatea algoritmului 4.1 este O(mn).

Algoritmul 4.2 [Determinarea stărilor utile2] Prin aplicarea strategiei greedy, putem obţine un şir ascendent de mulţimi cu stări utile, majorat în sensul relaţiei de incluziune de mulţimea stărilor automatului considerat.

Fie U0 = F. Pentru i ≥ 0, formăm Ui+1 = Ui ∪ q ∈ Q - Ui| există a ∈ Σ astfel încât δ(q, a) ∈ Ui.

Este clar că trebuie să existe k0, k0 ≤ |Q| astfel încât Uk0 = Uk0+1, k0 fiind cel mai mic număr natural cu această proprietate; în aceste condiţii Uk0+j = Uk0, oricare j≥1. Mulţimea stărilor utile este Uk0.

1 Problema determinării stărilor accesibile este echivalentă cu problema determinării vârfurilor unui digraf care sunt legate prin cel puţin un drum de vârful care corespunde stării q0. Dacă se determină matricea existenţei drumurilor sau, echivalent, închiderea tranzitivă a relaţiei binare asociată diagramei de tranziţie (de exemplu, folosind algoritmul Roy-Warshal) atunci stările accesibile corespund valorii 1 în linia stării q0 din matricea existenţei drumurilor. 2 În unele lucrări, stările utile sunt denumite stări observabile.

Intrare: Q, Σ, q0, δ, F Ieşire: U’ – mulţimea stărilor utile

SEQ 1. i := 0; U0:= F; 2. do

for a ∈ Σ do for q ∈ Q - Ui do if δ(q, a) ∈ Ui then Ui+1 = Ui ∪ q; i = i +1; while(Ui – Ui-1 ≠ ∅);

3. U’ = Ui. END.

Propoziţia 4.2

Cu notaţiile de mai sus, următoarele afirmaţii sunt adevărate: a) q este stare utilă dacă şi numai dacă q ∈ U’; b) Dacă |Q| = m, iar |Σ| = n, atunci complexitatea algoritmului 4.2 este O(mn).

4.2 Congruenţe şi limbaje regulate

Definiţia 4.2 [Relaţie de echivalenţă. Invarianţă. Congruenţă] Fie Σ un alfabet şi ≡ o relaţie binară pe Σ*. Relaţia ≡ se numeşte de echivalenţă dacă este reflexivă (α ≡ α, oricare α ∈ Σ*), simetrică ( α ≡ β ⇒ β ≡ α, oricare α ∈ Σ* şi β ∈ Σ*) şi tranzitivă (α ≡ β şi β ≡ γ ⇒ α ≡ γ, oricare α ∈ Σ*, β ∈ Σ* şi γ ∈ Σ*). Relaţia de echivalenţă ≡, pe Σ*, este invariantă la stânga dacă α ≡ β ⇒ γα ≡ γβ oricare γ ∈ Σ*. Relaţia de echivalenţă ≡, pe Σ*, este invariantă la dreapta dacă α ≡ β ⇒ αγ ≡ βγ oricare γ ∈ Σ*. O relaţie de echivalenţă este numită congruenţă dacă este invariantă atât la stânga cât şi la dreapta.

Relaţia de echivalenţă ≡ este de indice finit dacă numărul claselor de echivalenţă3 ale relaţiei ≡ este finit. Teorema 4.1 [Myhill-Nerode] Fie L ⊆ Σ* un limbaj. Următoarele afirmaţii sunt echivalente:

1) L este un limbaj regulat; 2) L este reuniunea unor clase de echivalenţă ale unei relaţii de echivalenţă

invariantă la dreapta, de rang finit; 3) Relaţia ρL ⊆ Σ*xΣ* definită prin:

u ρL v dacă şi numai dacă oricare w ∈ Σ* astfel încât uw ∈ L ⇔ vw ∈ L este o relaţie de echivalenţă invariantă la dreapta, de rang finit.

Demonstraţie. 1 ⇒ 2. Dacă L este limbaj regulat, atunci există un automat finit determinist M = (Q, Σ, δ, q0, F) astfel încât L(M) = L (vezi capitolul 3). Relaţia ρM ⊆ Σ*xΣ* definită prin u ρM v dacă şi numai dacă δ(q0, u) = δ(q0, v), este o relaţie de echivalenţă, chiar invariantă la dreapta de rang finit (u ρM v şi w ∈Σ* ⇒ uw ρM vw) ale cărei clase de echivalenţă sunt în număr cel mult egal cu numărul stărilor automatului M.

Deducem că L este reuniunea claselor de echivalenţă corespunzătoare stărilor finale ale automatului M.

3 Clasa de echivalenţă a unui element x este formată din totalitatea elementelor echivalente cu x.

2 ⇒ 3. Se verifică uşor că ρL este o relaţie de echivalenţă invariantă la dreapta, de rang finit. 3 ⇒ 1. Se construieşte automatul M’ = (Q’, Σ, δ’, q’0, F’), unde Q’ este mulţimea (finită) a claselor de echivalenţă a relaţiei ρL, q’0 este clasa de echivalenţă a cuvântului vid λ, F’ este mulţimea claselor de echivalenţă a cuvintelor limbajului L, iar δ’ este definită astfel: fie [w] clasa de echivalenţă a cuvântului w, atunci, orice [w] ∈ Q’ şi orice a ∈Σ, δ’([w], a)= [wa] (definire consistentă).

Fie w ∈Σ*. Atunci w ∈ L(M’) dacă şi numai dacă δ’(q’0, w) ∈ F’, dacă şi numai dacă δ’([λ], w) ∈ F’, dacă şi numai dacă [w] ∈ F’, dacă şi numai dacă w ∈ L. Deci L(M’)=L. Teorema 4.2 Automatul M’ construit anterior (în demonstraţia teoremei 4.1) este automatul minimal care acceptă limbajul L şi el este unic până la o redenumire a stărilor (un izomorfism). Definiţia 4.3 [Relaţia ≡] Fie M = (Q, Σ, δ, q0, F) un AFD. Definim, pe mulţimea stărilor, o relaţie de echivalenţă, notată ≡, astfel: Dacă p, q ∈Q atunci p ≡ q dacă şi numai dacă pentru oricare w ∈ Σ* avem echivalenţa: δ(p, w) ∈ F ⇔ δ(q, w) ∈ F. Observaţia 4.1 Există o corespondenţă biunivocă între clasele de echivalenţă ale relaţiei ≡ şi stările automatului M’ construit prin teorema Myhill-Nerode.

Pentru a determina stările automatului minimal care acceptă limbajul L(M) este suficient să găsim clasele de echivalenţă ale relaţiei ≡. Algoritmul 4.3 [Determinarea stărilor echivalente] Intrare: AFD M = (Q, Σ, δ, q0, F) Ieşire: Mulţimea perechilor de stări echivalente, mulţimea perechilor de stări neechivalente. Paşii:

1. Se marchează toate perechile (p, q), p ∈ F, q ∈ Q - F; S1 = F, S2 = Q - F. 2. Pentru fiecare pereche (p, q) ∈ SxS, unde S = S1 sau S = S2, p ≠ q, execută

A. Dacă există a ∈ Σ astfel încât (δ(p, a), δ(q, a)) este marcată atunci : i) se marchează (p, q); ii) se marchează, recursiv, toate perechile din lista lui (p, q) şi din

listele altor perechi marcate la acest pas. B. Dacă pentru oricare a ∈ Σ, perechea (δ(p, a), δ(q, a)) nu este marcată

atunci, pentru oricare a ∈ Σ, se adaugă (p, q) în lista perechii (δ(p, a), δ(q, a)) ori de câte ori δ(p, a) ≠ δ(q, a).

Observaţia 4.2 Orice p, q ∈ Q, p nu este echivalent cu q (relativ la ≡) dacă şi numai dacă în urma aplicării algoritmului 4.3 perechea (p, q) este marcată. Observaţia 4.3 Odată găsite perechile de stări echivalente se poate construi automatul minimal care acceptă limbajul supus discuţiei.

Fie M’=(Q’, Σ, δ’, [q0], F’) unde prin [q] notăm clasa de echivalenţă relativ la relaţia ≡ care are ca reprezentant starea q. Celelalte elemente sunt: Q’ = [q] | q este

stare accesibilă din q0, F’ = [q] | q ∈ F, δ’([q], a)= [δ(q, a)], oricare [q] ∈ Q’şi oricare a ∈ Σ.

4.3 Lema de pompare pentru limbaje regulate. Aplicaţii Teorema 4.3 [Lema de pompare] Fie L un limbaj regulat. Există atunci un număr natural n astfel încât pentru orice cuvânt w ∈ L, |w| ≥ n, w = xyz cu proprietăţile:

a) |xy| ≤ n; b) |y| ≥ 1; c) xyiz ∈ L pentru oricare i ≥ 0.

Propoziţia 4.3 Fie L un limbaj acceptat de un AFD cu n stări. Atunci L ≠ ∅ ⇔ există w ∈ L astfel încât |w| < n; Propoziţia 4.4 Fie L un limbaj acceptat de un AFD cu n stări. Atunci L este infinit ⇔ există w ∈ L, n ≤ |w| < 2n. Algoritmul 4.4 Fie L un limbaj acceptat de un AFD cu n stări. Pentru a verifica dacă L ≠ ∅, se poate aplica următorul algoritm, cu complexitatea mult mai mică decât metoda furnizată prin propoziţia 4.3.

Intrare: Q, Σ, q0, δ, F Ieşire: “DA” dacă L este nevid; “NU” în caz contrar.

SEQ

1. i := 0; S0:= q0; 2. do Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i + 1; while(Si – Si-1 ≠ ∅); 3. if Si ∩ F = ∅ then write “NU”; else write “DA”.

END. Se observă că mulţimea Si, de la pasul 3, conţine stările accesibile. Este clar că dacă nici o stare finală nu este accesibilă atunci limbajul L este vid. Algoritmul 4.5 Fie L un limbaj acceptat de un AFD cu n stări. Pentru a verifica dacă L ≠ ∅, se poate aplica următorul algoritm, cu complexitatea mult mai mică decât metoda furnizată prin propoziţia 4.4.

Intrare: Q, Σ, q0, δ, F Ieşire: “DA” dacă L este infinit; “NU” în caz contrar.

SEQ

1. i := 0; S0:= q0; 2. do Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i + 1; while(i < n); 3. do

if Si ∩ F ≠ ∅ then write “DA”; stop. Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i + 1; while(i < 2n);

4. write “NU”. END.

5. Transformări asupra gramaticilor formale

5.1 Transformări elementare

Propoziţia 5.1 [Transformare privind simbolul de start] Fie G = (Ω, Σ, S, P) o gramatică de tipul i (i = 1, 2, 3). Există o gramatică G1 de acelaşi tip cu G, echivalentă cu G, astfel încât simbolul iniţial S1 al gramaticii G1 să nu apară în nici unul din cuvintele aflate în membrul al doilea al producţiilor gramaticii G1. Corolarul 5.1 [Generarea limbajelor L ∪ λ, unde λ ∉ L]

Dacă L este un limbaj de tipul i (i = 1, 2, 3), atunci există o gramatică G = (Ω, Σ, S, P) care generează limbajul L ∪ λ astfel încât:

1) Simbolul iniţial S să nu apară în membrul al doilea în nici una din producţiile gramaticii G.

2) În mulţimea P să existe regula S ::= λ. 3) Gramatica G1 = (Ω, Σ, S, P1), unde P1 := P – S ::= λ să fie de tipul i (i = 1,

2, 3) şi să genereze limbajul L. Astfel putem defini limbajele de tip i (i = 1, 2, 3), precum în definiţia 5.1. Definiţia 5.1 [Limbaj de tip i (i = 1, 2, 3)] Limbajul L este de tip i (i = 1, 2, 3), dacă limbajul L – λ este generat de o gramatică de tipul i (i = 1, 2, 3). Lema 5.1 [Existenţa derivărilor stângi] Fie G = (Ω, Σ, S, P) o gramatică de tipul 2. Atunci pentru orice A ∈ Ω şi w ∈ Σ* cu A w, există o derivare stângă a lui w din A.

→*

5.2 Redenumiri şi λ-producţii

Propoziţia 5.3 [Eliminarea redenumirilor] Fie G = (Ω, Σ, S, P) o gramatică de tipul 2 sau 3. Există o gramatică G1 = (Ω, Σ, S, P1) de acelaşi tip cu G, echivalentă cu G şi fără redenumiri. Definiţia 5.2 [Gramatici cu λ-producţii] Fie G = (Ω, Σ, S, P) o gramatică cu producţiile de forma (p, q) ∈ Ωx(Ω∪Σ)*. Se numeşte λ-producţie orice producţie de forma (X, λ) şi scriem X ::= λ (X ∈ Ω). Propoziţia 5.4 [Determinarea simbolurilor neterminale care “generează” cuvântul vid] Fie G = (Ω, Σ, S, P) o gramatică cu producţiile de forma (p, q) ∈ Ωx(Ω∪Σ)*. Şirul de mulţimi generat prin:

U0 = ∅; Um+1 = Um ∪ X | X ∈ Ω, există w, w ∈ Um*, X ::= w ∈ P

are următoarele proprietăţi:

a) U0 ⊆ U1 ⊆ … Um ⊆ … ⊆ Ω şi există k, număr natural, astfe încât Uk = Uk+1. b) Dacă Uk = Uk+1, atunci Uk = Uk+i, pentru oricare i > 0. c) Fie k* cel mai mic număr natural pentru care Uk* = Uk* +1. Atunci

Uk* = X | X ∈ Ω şi X λ. →*

Corolarul 5.2 [Limbaje independente de context generate de gramatici cu λ - producţii] Fie G = (Ω, Σ, S, P) o gramatică cu producţiile de forma (p, q) ∈ Ωx(Ω∪Σ)*. Atunci L(G) este un limbaj independent de context.

5.3 Simboluri utile Propoziţia 5.5 [Simboluri care generează cuvinte peste Σ] Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Există o gramatică G1 = (Ω1, Σ, S, P1) independentă de context, echivalentă cu G, astfel încât pentru oricare X ∈ Ω1, mulţimea w ∈ Σ* | X w este nevidă. →*

Corolarul 5.3 [Decidabilitatea problemei L(G) ≠ ∅] Există un algoritm care pentru o gramatică independentă de context stabileşte dacă L(G) = ∅ sau L(G) ≠ ∅. Definiţia 5.3 [Simboluri inaccesibile] Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. A ∈ Ω ∪ Σ este un simbol inaccesibil dacă nu există nici o derivare S uAv cu u, v ∈ (Ω∪Σ)*. Altfel simbolul A este accesibil. →*

Propoziţia 5.6 [Determinarea simbolurilor accesibile] Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Există G1 = (Ω1, Σ1, S, P1) echivalentă cu G care nu are simboluri inaccesibile. Propoziţia 5.7 Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Atunci G este echivalentă cu o gramatică G1 fără simboluri neutilizabile. Definiţia 5.4 [Gramatică proprie] Fie G = (Ω, Σ, S, P) o gramatică independentă de context. G se numeşte gramatică proprie dacă conţine numai simboluri utilizabile (accesibile şi productive), nu conţine λ-producţii şi nu are redenumiri într-unul sau mai mulţi paşi. Teorema 5.1 Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Există G1 = (Ω1, Σ1, S, P1) echivalentă cu G care este gramatică proprie.

6. Forme normale. Lema Bar-Hillel

6.1 Forma normală Chomsky

Definiţia 6.1 [FNC]

O gramatică G = (Ω, Σ, S, P) de tipul 2, fără λ-producţii şi fără redenumiri, este în forma normală Chomsky (FNC) dacă producţiile sale sunt de una din formele A ::= BC, A ::= a, pentru A, B, C ∈ Ω, a ∈ Σ. Observaţia 6.1 Conform teoremei 5.1 este suficient să se lucreze cu mecanisme generative echivalente cu gramaticile proprii (obţinute după transformările necesare). Teorema 6.1 Fie G = (Ω, Σ, S, P) o gramatică proprie. Atunci există G1 gramatică în forma normală Chomsky echivalentă cu G. Teorema 6.2 Fie G = (Ω, Σ, S, P) o gramatică de tip 2 în forma normală Chomsky. Dacă derivarea A → w1 → … → wn, n ≥ 1, wn ∈ Σ*, are proprietatea că cel mai lung lanţ de la rădăcină la vârfurile terminale în arborele de derivare asociat ei în gramatica GA = (Ω, Σ, A, P) are k noduri, atunci |wn| ≤ 2k-1.

6.2 Forma normală Greibach Definiţia 6.2 [FNG] O gramatică G = (Ω, Σ, S, P), fără λ-producţii şi fără redenumiri, este în forma normală Greibach (FNG) dacă P conţine producţii numai de forma A ::= aW, pentru A ∈ Ω, a ∈ Σ şi W ∈ (Ω∪Σ)*. Lema 6.1 Fie gramatica proprie G = (Ω, Σ, S, P) şi A ::= α1Bα2 o A-producţie şi B ::= β1 | β2 | … βk toate B-producţiile din mulţimea P. Considerăm G1 = (Ω, Σ, S, P1) unde P1 = (P – A ::= α1Bα2) ∪ A ::= α1β1α2 | α1β2α2 |… | α1βkα2 . Atunci G şi G1 sunt gramatici echivalente. Lema 6.2 Fie gramatica fără λ-producţii şi numai cu simboluri utilizabile, G = (Ω, Σ, S, P) şi A ::= Aα1 | Aα2 … | Aαk toate A-producţiile recursive la stânga şi A ::= β1 | β2 | … βm restul A-producţiilor din mulţimea P. Fie X un simbol nou, X ∉ Ω ∪ Σ, Ω1 = Ω ∪ X şi gramatica G1 = (Ω1, Σ, S, P1), unde P1 se obţine din P prin înlocuirea tuturor A-producţiilor cu regulile: A ::= β1 | β2 | … βm, A ::= β1X | β2X | … βmX şi X ::= α1 | α2 … | αk, X ::= α1X | α2X … | αkX.

Atunci G şi G1 sunt echivalente. Teorema 6.3 Fie G = (Ω, Σ, S, P) o gramatică proprie. Atunci există gramatica G*, în forma normală Greibach, echivalentă cu G. Demonstraţie. Asupra gramaticii G se pot aplica metodele descrise în cadrul lemelor 6.1 şi 6.2. Se poate aduce ultima gramatică obţinută la forma normală Chomsky. Notăm această gramatică cu G1. Presupunem că neterminalele gramaticii G1 sunt numerotate şi scriem regulile în ordine crescătoare a indicilor simbolurilor

neterminale. Aplicăm un algoritm simplu prin care se obţine G*, cu mulţimea regulilor P*, în forma normală Greibach: Intrare: Gramatica G1 în forma normală Chomsky, nerecursivă la stânga, fără λ-producţii, Ω1 = A1, A2, …., Am, S1 ≡ A1. Ieşire: Gramatica G* în forma normală Greibach.

SEQ 1. P* := P1; i := m; 2. while i > 1 do

SEQ i := i - 1; while (există j, i < j ≤ m, Ai ::= Ajα în P*) do

P* := (P* - Ai ::= Ajα) ∪ Ai ::= βα | Aj ::= β ∈ P* END

3. for indici i ai simbolurilor Y do while (există j, 1 ≤ j ≤ m, Yi ::= Ajα ∈ P*) do P* := (P* - Yi ::= Ajα ) ∪ Yi ::= βα | Aj ::= β ∈ P*

END. Trebuie observat că, în general, procesul de normalizare, conduce la creşterea numărului neterminalelor dar şi a regulilor. Astfel cresc măsurile Var şi Prod.

6.3 Lema Bar-Hillel Teorema 6.4 [Lema Bar-Hillel] Fie L un limbaj independent de context oarecare. Atunci există numerele naturale p = p(L) şi q = q(L) astfel încât orice cuvânt w ∈ L cu |w| > p se poate descompune sub forma w = uvxyz, unde |vxy| ≤ q, vy ≠ λ şi pentru oricare număr natural i, uvixyiz ∈ L. Propoziţia 6.1 Fie G o gramatică independentă de context. Atunci L(G) este infinit dacă şi numai dacă există w ∈ L(G) astfel încât p < |w| ≤ p + q, unde p şi q sunt numerele furnizate de teorema 6.4.

7. Gramatici şi automate

7.1 Gramatici liniare şi limbaje regulate

Teorema 7.1 Fie G = (Ω, Σ, S, P) o gramatică liniară la dreapta1. Atunci există un automat finit nedeterminist (deci şi unul determinist) M astfel încât L(M) = L(G). Teorema 7.2 Orice limbaj generat de o gramatică liniară2 este regulat. Teorema 7.3 Pentru orice limbaj regulat L există o gramatică liniară G astfel încât L=L(G).

7.2 Automate pushdown Un automat pushdown (cu memorie locală gestionată prin disciplina LIFO [eng. Last In First Out] – numită memorie pushdown) citeşte banda de intrare (de la stânga la dreapta) folosind un număr de stări interne (ca şi un AFD sau AFN), dar tranziţia, în general nedeterministă, se face nu numai în raport cu starea anterioară şi informaţia curentă de pe banda de intrare, ci şi în funcţie de cea mai recentă informaţie stocată în memoria auxiliară (prelucrată ca o stivă de capacitate infinită). Definiţia 7.1 [APD] Un automat pushdown (APD) este un sistem M = (Q, Σ, Γ, δ, q0, Z0, F) unde Q, Σ, q0, şi F au semnificaţiile cunoscute, Γ este o mulţime finită şi nevidă de simboluri care formează alfabetul pushdown, Z0 ∈ Γ este simbolul pushdown iniţial, iar δ este funcţia de tranziţie δ : Qx(Σ ∪ λ)xΓ → P(QxΓ*). Definiţia 7.2 [Configuraţie] Fie M = (Q, Σ, Γ, δ, q0, Z0, F) un APD. Orice triplet (q, w, α) ∈ QxΣ*xΓ* se numeşte configuraţie a automatului M. Elementele configuraţiei au următoarea semnificaţie: q este starea curentă a unităţii de comandă a automatului; w este un cuvânt peste alfabetul de intrare Σ, inclusiv λ, care reprezintă partea necitită de pe banda de intrare3; α reprezintă conţinutul memoriei stivă. Dacă α = λ atunci memoria stivă este vidă. Definiţia 7.3 [Mişcarea automatului] Fie q, s ∈ Q, a ∈ Σ ∪ λ, Z ∈ Γ, w ∈ Σ* şi α, γ ∈ Γ*. Configuraţia (q, aw, Zα) se află în relaţia |- cu configuraţia (s, w, γα) şi se scrie (q, aw, Zα) |- (s, w, γα) dacă şi numai dacă (s, γ) ∈ δ(q, a, Z). Observaţia 7.1 Mişcarea automatului este posibilă numai dacă memoria stivă este nevidă.

1 A se vedea şi propoziţia 2.5. 2 Din acest motiv gramaticile liniare se mai numesc şi gramatici regulate. Rezultă, de aici, că familia limbajelor de tip 3 conţine limbajele finite şi este închisă la operaţiile de reuniune, produs şi stelare (*). Astfel, limbajele de tip 3 sunt descriptibile cu ajutorul expresiilor regulate, generabile de gramatici liniare şi recunoscute de sisteme tranziţionale şi deci de automate finite. 3 Capul de citire se găseşte în dreptul primului simbol al cuvântului w. Se presupune că, la dreapta, după ultimul caracter al cuvânului w se află şirul vid λ.

Definiţia 7.4 [Închiderea reflexivă şi tranzitivă a relaţiei |-] Închiderea reflexivă şi tranzitivă a relaţiei |-, notată prin →* , se defineşte astfel:

(q1, w1, α1) →* (q2, w2, α2) dacă (q1, w1, α1) = (q2, w2, α2)

sau există k configuraţii (pi, ui, βi), i = 1, 2, …, k, astfel încât (q1, w1, α1) = (p1, u1, β1), (q2, w2, α2) = (pk, uk, βk) şi (pi, ui, βi) |- (pi+1, ui+1, βi+1), i = 1, 2, …, k-1. Definiţia 7.5 [Cuvânt acceptat prin stare finală] Fie M = (Q, Σ, Γ, δ, q0, Z0, F) un APD şi w ∈ Σ* un cuvânt. Atunci w este acceptat (recunoscut) de automatul M dacă există q ∈ F şi α ∈ Γ* astfel încât (q0, w, Z0) →* (q, λ, α). Definiţia 7.6 [Limbaj acceptat prin stări finale] Fie M = (Q, Σ, Γ, δ, q0, Z0, F) un APD. Limbajul acceptat (recunoscut) de automatul M, notat L(M), este mulţimea tuturor cuvintelor acceptate de M prin atingerea unei stări finale. Definiţia 7.7 [Cuvânt acceptat cu memoria pushdown vidă] Fie M = (Q, Σ, Γ, δ, q0, Z0, F) un APD şi w ∈ Σ* un cuvânt. Atunci w este acceptat (recunoscut) de automatul M cu memoria pushdown vidă4 dacă există q ∈ Q astfel încât (q0, w, Z0) →* (q, λ,

λ). Mulţimea tuturor cuvintelor acceptate de M cu memoria pushdown vidă se va nota cu Lλ(M) şi este limbajul recunoscut de M cu memoria pushdown vidă. Teorema 7.4 [Un limbaj recunoscut de un APD cu stări finale poate fi recunoscut şi de un APD cu memoria pushdown vidă] Fie L(M) limbajul recunoscut de automatul pushdown M = (Q, Σ, Γ, δ, q0, Z0, F). Atunci există un APD, notat M’=(Q’, Σ, Γ’, δ’, qinit, X, ∅), care recunoaşte L(M) cu memoria pushdown vidă, adică Lλ(M’) = L(M). Teorema 7.5 [Un limbaj recunoscut de un APD cu memoria pushdown vidă poate fi recunoscut şi de un APD cu stări finale] Fie Lλ(M) limbajul recunoscut de automatul pushdown M = (Q, Σ, Γ, δ, q0, Z0, ∅). Atunci există un APD, notat M’ = (Q’, Σ, Γ’, δ’, qinit, X, qf), care recunoaşte Lλ(M) cu starea finală qf, adică Lλ(M) = L(M’).

7.3 Limbaje independente de context şi automate pushdown

Teorema 7.6 Pentru orice gramatică independentă de context G = (Ω, Σ, S, P) care generează limbajul L = L(G) există un sistem APD care recunoaşte L. Teorema 7.7 Pentru orice sistem APD care recunoaşte limbajul L cu memoria pushdown vidă, există o gramatică independentă de context care generează limbajul L.

7.4 Maşini Turing şi automate liniar mărginite Definiţia 7.8 [MT] O maşină Turing sau sistem MT este o structură M = (Q, Σ, Γ, δ, q0, B, F) unde Q, Σ, q0 şi F au semnificaţia uzuală (vezi, de exemplu, sistemele AFD, AFN sau APD), Γ este o mulţime finită şi nevidă care conţine Σ, simbolul B (cu rol special, numit şi blanc) şi alte simboluri - întreaga mulţime Γ numindu-se alfabetul de 4 Se observă că putem alege F = ∅.

lucru, iar δ este funcţia de tranziţie definită astfel: δ : QxΓ → QxΓxS, D unde S, D înseamnă stânga, respectiv dreapta. Definiţia 7.9 [Configuraţie] Fie M = (Q, Σ, Γ, δ, q0, B, F) un sistem MT. Se numeşte configuraţie un cuvânt de forma αqβ unde α, β ∈ Γ*, iar q ∈ Q. Semnificaţia elementelor este următoarea: α este cuvântul de la început până la capul de citire-scriere, q este starea unităţii de control şi β este cuvântul de la simbolul vizat (imediat din dreapta lui s) până la ultimul simbol (diferit de blanc). Definiţia 7.10 [Transformarea configuraţiilor] Fie M = (Q, Σ, Γ, δ, q0, B, F) un sistem MT. Considerăm simbolul |- pentru a descrie relaţia binară definită pe mulţimea configuraţiilor. Fie configuraţia x1x2…xi-1qxixi+1…xn, cu i = 1, 2, …, n. Dacă δ(q, xi) = (q’, y, S) atunci:

a) sufixele de blancuri dispar (se pot şterge secvenţe de tipul BB); b) dacă i = 1 atunci nu există deplasare la stânga; c) dacă i = 2, …, n atunci x1x2…xi-1 q xixi+1…xn |- x1x2…xi-2 q’ xi-1yxi+1…xn.

Dacă δ(q, xi) = (q’, y, D) atunci x1x2…xi-1 q xixi+1…xn |- x1x2…xi-1 y q’ xi+1…xn. Considerăm, de asemenea, simbolul →* pentru a descrie închiderea reflexivă

şi tranzitivă a relaţiei |-. Definiţia 7.11 [Limbajul acceptat de un sistem MT] Fie M = (Q, Σ, Γ, δ, q0, B, F) un sistem MT. Limbajul acceptat de M, notat L(M), este definit prin:

L(M) = w | w ∈ Σ*, există r ∈ F şi α, β ∈ Γ* astfel încât q0w →* αrβ. Observaţia 7.2 Fie M = (Q, Σ, Γ, δ, q0, B, ∅) un sistem MT. Atunci L(M) = ∅. Observaţia 7.3 Fie M = (Q, Σ, Γ, δ, q0, B, Q) un sistem MT. Atunci L(M) = Σ*. Observaţia 7.4 Introducerea nedeterminismului asupra sistemelor MT nu creşte puterea de acceptare. Mai precis, are loc teorema 7.8. Teorema 7.8 Pentru orice maşină Turing M există o gramatică G, de tip 0, astfel încât L(M) = L(G). Definiţia 7.12 [LBA] Un automat liniar mărginit sau sistem LBA (eng. Linear Bounded Automata) este un sistem MT, nedeterminist care satisface, în plus, următoarele două condiţii:

a) Mulţimea Σ conţine două simboluri distincte cu semnificaţie specială, notate prin # şi $.

b) Sistemul MT nu se poate deplasa nici la stânga simbolului #, nici la dreapta simbolului $. Mai precis: δ(q, #) = (q’, #, D) şi δ(q, $) = (q’, $, S).

Definiţia 7.13 [Limbajul acceptat de un sistem LBA] Fie M = (Q, Σ, Γ, δ, q0, B, F) un sistem LBA. Limbajul acceptat de M, notat L(M), este definit prin:

L(M) = w | w ∈ Σ*, există r ∈ F şi α, β ∈ Γ* astfel încât q0#w$ →* αrβ. Definiţia 7.14 [Gramatică monotonă] O gramatică (formală) se numeşte monotonă dacă regulile sale u ::= v au proprietatea că |u| ≤ |v|.

Teorema 7.9 Următoarele afirmaţiile (a) şi (b) sunt adevărate: (a) Pentru orice gramatică dependentă de context (de tip 1) G = (Ω, Σ, S, P) există o gramatică monotonă G’ = (Ω, Σ, S, P’) astfel încât L(G’) = L(G) – λ; (b) Pentru orice automat liniar mărginit M există o gramatică monotonă G astfel încât L(M) = L(G).

8. Proprietăţi de închidere

8.1 Reuniunea limbajelor Definiţia 8.1 Fie L o familie oarecare de limbaje. Spunem că familia L este închisă la operaţia # dacă ∀L1, ∀L2 ( L1 ∈ L şi L2 ∈ L ⇒ L1 # L2 ∈ L ). În continuare se presupun cunoscute notaţiile introduse în §1.2 referitor la operaţiile cu limbaje. Prin Li vom desemna familia limbajelor de tipul i, în sensul definiţiei 5.1. Evident L0 este familia limbajelor generate de gramatici de tip 0 (fără restricţii) şi recunoscute de maşini Turing. Teorema 8.1 Familia limbajelor dependente de context este închisă faţă de reuniune. Observaţa 8.1 Enunţul şi demonstraţia de mai sus pot fi refăcute pentru a arăta închiderea la reuniune a familiilor L2 şi L3.

8.2 Familia limbajelor regulate

Conform teoremei 3.3, familia limbajelor regulate este cea mai mică familie de limbaje care conţine limbajele finite şi este închisă la reuniune, produs (concatenare) şi la operaţia * (închiderea Kleene). Trebuie remarcat că familia L 3 include strict familia limbajelor finite. Teorema 8.2 Fie Σ un alfabet şi L ⊆ Σ* un limbaj regulat. Atunci Σ* - L este un limbaj regulat Teorema 8.3 Familia limbajelor regulate este închisă la operaţia de intersecţie. Observaţia 8.2 Familia limbajelor regulate peste un alfabet Σ, fiind închisă la reuniune, intersecţie şi complementară, formează o algebră booleană în care suma booleană este reuniunea, produsul boolean este intersecţia, iar complementul unui element este obţinut prin formarea limbajului complementar (diferenţa până la Σ*.)

8.3 Familia limbajelor independente de context

Teorema 8.4 Familia L 2 este închisă la reuniune. Teorema 8.5 Familia L 2 este închisă la concatenare (produs). Teorema 8.6 Familia L 2 este închisă la operaţia * (stelare). Observaţia 8.3 Dacă L este un limbaj de tip i (i = 2 sau 3) atunci L+ este de tip i. Teorema 8.7 Familia L2 nu este închisă la intersecţie şi complementară. Teorema 8.8 Fie L ∈ L2 şi R ∈ L3, L1 = L ∩ R şi L2 = L – R. Atunci Li ∈ L2 (i = 1, 2).

Teorema 8.9 Considerăm transformarea de substituire definită asupra limbajelor ca în definiţia 1.8. Familia limbajelor independente de context este închisă la substituţii. Observaţia 8.4 Familia limbajelor independente de context este închisă la homomorfisme. Definiţia 8.2 O maşină secvenţială generalizată (eng. gsm: generalized sequential machine) sau traducător secvenţial generalizat este sistemul M = (Q, Σ, ∆, δ, q0, F) unde Q, Σ, q0 şi F au semnificaţia cunoscută, ∆ este o mulţime finită şi nevidă, reprezentând alfabetul de ieşire, iar δ : Q x Σ → P(Q x ∆*) este funcţia de tranziţie. Observaţia 8.5 Un sistem gsm este un sistem AFN care, în plus, faţă de banda de intrare (cuvinte peste Σ) conţine şi o bandă de ieşire (pentru manipularea cuvintelor peste ∆). Faptul că (q2, u) ∈ δ(q1, a) arată trecerea din starea q1 in starea q2, când capul de citire a întâlnit simbolul a, dar şi emiterea cuvântului u ∈ ∆* la ieşire. Funcţia δ se extinde la Σ*, în mod obişnuit. Definiţia 8.3 Fie M = (Q, Σ, ∆, δ, q0, F) un sistem gsm. Transformarea gsm definită de M este funcţia gM : Σ* → P(∆*) definită după cum urmează. Fie u ∈ Σ* oarecare. Atunci gM(u) = w | w ∈ ∆*, există q ∈ F astfel încât (q, w) ∈ δ(q0, u).

Dacă L ⊆ Σ* atunci gM(L) = . Transformarea gsm inversă este : ∆*

→ P(Σ*) dată de (u) = v | u ∈ g

ULu

M ug∈

)( 1−Mg

1−Mg M(v). Dacă L ⊆ ∆* atunci (L) = v | există u

∈ L astfel încât u ∈ g

1−Mg

M(v). Teorema 8.10 Orice clasă de limbaje peste alfabetul Σ închisă la substituţii finite şi intersecţie cu limbaje regulate este închisă la transformări gsm. Observaţia 8.6 Deoarece familiile Li ( i = 2, 3) satisfac condiţille teoremei 8.10 rezultă că acestea sunt închise la transformări gsm.

9. Specificarea sintaxei limbajelor de programare şi marcare

Specificarea sintaxei unui limbaj de programare contribuie alături de specificarea semanticii acestuia la ceea ce, global, se numeşte specificarea limbajului. Sintaxa limbajului permite determinarea şirurilor de simboluri (cuvintelor) care reprezintă programe sau texte corect construite (din punct de vedere al regulilor sintactice) în limbajul respectiv. Semantica limbajului descrie înţelesul asociat unui text/program pornind de la conceptele de bază ale limbajului.

De obicei, specificarea sintaxei unui limbaj artificial, în special un limbaj de programare, se face cu ajutorul unui mecanism de descriere BNF sau EBNF (Backus/Extended Backus Naur Form) care este echivalent ca putere generativă cu gramaticile independente de context.

9.1 Limbajului C++

Limbajul C++ a fost dezvoltat la începutul anilor ’80 de către Bjarne Stroustrup de la laboratoarele AT&T Bell. Este un supraset al limbajului C, cel care a fost creat în 1972 de către Dennis Ritchie. C++ păstrează viteza, eficienţa şi simplitatea limbajului C pe care-l îmbunătăţeşte şi îl completează cu support pentru abstractizarea datelor şi proiectarea orientată obiectual. Definiţiile formale, de mai jos, definesc, parţial, sintaxa instrucţiunilor limbajului C++ (AT&T 1997).

Doi termeni: declarare şi definire (prin definire se înţelege declarare + iniţializare) joacă un rol important în specificarea programelor C/C++. În cazul definiţiilor fără iniţializator, variabilele primesc valori implicite, echivalente lui 0 (0 pentru tipuri numerice, cuvântul vid (λ) pentru şiruri de caractere, valoarea NULL pentru pointeri). Declaraţiile introduc nume în unităţile de program (blocuri/ unităţi de translatare).

În general declaraţiile nu sunt şi definiţii. Următoarele situaţii nu constituie definiţii: (1) Se declară o funcţie fără a-i specifica şi corpul; (2) Declaraţia conţine specificatorul extern şi nu are iniţializare sau corp de

funcţie; (3) Se declară un membru static într-o declaraţie de clasă; (4) Se declară un nume de clasă; (5) Se descrie o declaraţie typedef.

Declaraţiile pentru variabile pot specifica şi tipul legării: intern sau extern

(introdus prin intermediul clasei de memorare). De asemenea, declaraţiile sau definiţiile pot conţine calificatori cv (const sau volatile) care definesc modificabilitatea obiectelor precizate. Modul de aplicabilitate al calificatorilor cv asupra pointerilor prezintă o importantă particularitate: atributul const sau volatile prefixat cu operatorul * (dereferenţiere) se aplică pointerului şi nu obiectului punctat de acesta.

Programele C++ sunt organizate în unităţi de translatare ce pot fi compilate separat, urmând ca procesul editării legăturilor (eng. bind, make, link etc.), prin care se obţine executabilul, să fie realizat ulterior. Notaţie Simbolurile neterminale încep cu literă mare. Unele neterminale se termină cu –opţional. Aceasta înseamnă că regula care conţine o astfel de construcţie este o meta-regulă, adică este posibilă şi înlocuirea neterminalului cu λ (cuvântul vid). Se obţin, practic, mai multe producţii ale gramaticii limbajului.

Instrucţiuni Secvenţă-instrucţiuni ::= Instrucţiune | Secvenţă-instrucţiuni Instrucţiune Instrucţiune ::= Instrucţiune-etichetată | Instrucţiune-expresie |

Instrucţiune-compusă | Selecţia | Iteraţia | Instrucţiune-salt | Instrucţiune-declaraţie | Bloc-try

Instrucţiune-etichetată ::= Identificator : Instrucţiune | case Expresie-const : Instrucţiune | default : Instrucţiune

Instrucţiune-expresie ::= Expresie-opţional Instrucţiune-compusă ::= Secvenţă-instrucţiuni-opţional Selecţia ::= if ( Condiţie ) Instrucţiune |

if ( Condiţie ) Instrucţiune else Instrucţiune | switch ( Condiţie ) Instrucţiune

Condiţie ::= Expresie | Specificator-tip Declarator = Expresie-atribuire Iteraţia ::= while ( Condiţie ) Instrucţiune | do Instrucţiune while ( Expresie ) ; | for ( Iniţializare-for-opţional ; Condiţie-opţional ; Expresie-opţional ) Instrucţiune Iniţializare-for ::= Instrucţiune-expresie | Declaraţie-simplă Instrucţiune-salt ::= break; | continue; | return Expresie-opţional; | goto Identificator;

9.2 Limbajul Prolog Limbajul Prolog diferă de limbajul C++ foarte mult. Prolog este un limbaj declarativ pentru programare logică. Face parte din clasa limbajelor de generaţia a cincea şi a fost dezvoltat în perioada 1974-1979, la Universitatea din Marsilia. Este utilizat cu predilecţie în inteligenţa artificială şi lingvistica computaţională1. În cele ce urmează descriem elementele de sintaxă ale dialectului SICStus2. Mai întâi descriem câteva elemente ale acestui dialect.

Obiectele limbajului se numesc termeni. Un termen este fie o constantă, o variabilă sau un termen compus. Constantele includ întregii, numerele în virgulă mobilă (Floating point) şi atomii. Variabilele sunt specificate prin identificatori care încep cu literă mare sau _ (pentru variabilele anonime). Termenii compuşi se referă la construcţii definite printr-un functor şi o secvenţă de argumente, între paranteze rotunde. Un atom este un functor cu aritatea zero (fără argumente).

Listele sunt structuri speciale. O listă nevidă are un prim element (capul listei) şi lista elementelor rămase şi, se notează prin [ primul-element | Lista-elementelor-rămase ]. O listă de întregi, care reprezintă coduri ASCII, defineşte un string (şir de caractere).

Unitatea de bază a unui program logic o reprezintă scopul sau apelul procedural. Un program Prolog constă dintr-o secvenţă de construcţii numite fraze. O frază conţine, în general, două părţi: capul şi coada. Capul frazei joacă rolul concluziei, iar coada frazei pe cel al ipotezei. Dacă capul este nevid avem de-a face cu o clauză:

P :- A, B, C. Aceasta se poate citi astfel: P este proprietate adevărată dacă sunt adevărate simultan A, B şi C. 1 Pentru procesarea limbajului natural, folosind limbajul Prolog, se poate parcurge Hristea (2000). 2 SICStus Prolog – The Prolog Language, http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_9.html

Dacă corpul clauzei este vid atunci clauza se numeşte atomică (sau clauză unitate). Clauza atomică este de forma P. şi se citeşte: P este o propoziţie validă (satisfăcută).

O frază cu capul vid este o directivă. O categorie specială de directive o reprezintă întrebările. O întrebare este de forma

?- P, Q. şi se poate citi interogativ: “Sunt P şi Q adevărate?” sau, procedural, “Satisfacerea scopurilor P şi Q”.

Frazele, în general, conţin variabile. Variabilele aflate în fraze diferite sunt complet independente. Domeniul lexical al unei variabile se reduce la fraza în care apare. Variabilele disticte dintr-o frază reprezintă entităţi sau valori arbitrare.

Predicatul unui functor F este dat de secvenţa de clauze care au în partea de concluzie functorul F. Pentru predicatele în care apar atât clauze de bază cât şi clauze recursive, se recomandă (chiar trebuie) scrierea clauzelor de bază mai întâi şi apoi scrierea celor recursive. Mai multe predicate pot avea acelaşi nume, dar arităţi diferite. Unele predicate sunt furnizate de sistemul Prolog (se spune că sunt predicate built-in). Cele mai multe predicate traduc cunoaşterea umană în fapte, reguli şi întrebări (sau scopuri).

O subgramatică formală a limbajului Prolog (dialectul SICStus) cuprinde reguli precum: Entitate-lexicală ::= Nume | Număr-natural | Flotant-fără-semn | Variabilă

| String | Semn-de-punctuaţie | Text-format | Punct Cifră ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Caracter ::= Caracter-format | Alfa-numeric | Caracter-simbol

| Caracter-solo | Semn-de-punctuaţie | Caracter-citare Secvenţă-de-cifre ::= Cifră | Cifră Secvenţă-de-cifre Punct ::= .

Text-format ::= Secvenţă-componente-formatare Secvenţă-componente-formatare ::= Componentă-formatare | Componentă-formatare Secvenţă-componente-formatare

Componentă-formatare ::= Caracter-format | Comentariu Caracter-format ::=

caracterele cu codurile ASCII: 0..32 şi 127..159 (ISO 8859/1) sau 0..32, 127 în Extended Unix Code.

Caracter-solo ::= ! | ; (codurile ASCII 33 şi 59) Semn-de-punctuaţie ::=

caracterele cu codurile ASCII: 37, 40, 41, 44, 91, 93 şi 123..125. Caracter-citare ::= " | ' Caracter-simbol ::= caracterele cu codurile ASCII: 35, 36, 38, 42, 43, 45..47, 58, 60..64, 92, 94, 96, 126, 160..191, 215 şi 247. Comentariu ::= Comentariu-bloc | Comentariu-rând Comentariu-bloc ::= /* Secvenţă-de-caractere */ Comentariu-rând ::= % Secvenţă-de-caractere Nume ::= Nume-citat | Cuvânt | Simbol | Caracter-solo

| [ Format-text-opţional ] Nume-citat ::= Apostrof Şir-fără-apostrof Apostrof Şir-fără-apostrof ::= zero, unul sau mai multe caractere diferite de Apostrof |

Ghilimele Apostrof ::= ' Ghilimele ::= "

Modul ::= Atom Constantă ::= Atom | Număr Număr ::= Întreg | Flotant Atom ::= Nume Întreg ::= Număr-natural | - Număr-natural Flotant ::= Flotant-fără-semn | - Flotant-fără-semn Functor ::= Nume Observaţia 9.1 În Prolog se comunică cunoştinţe. Determinarea efectivă a soluţiei este realizată de către nucleul Prolog prin metode specifice: unificare, backtracking etc. Observaţia 9.2 Limbajul Prolog permite atât codificarea algoritmilor recursivi, cât şi a celor nerecursivi. Observaţia 9.3 [Gramatici în Prolog] Limbajul Prolog are mecanismul de derivare3 implementat. Cuvintele sunt liste. Gramatica G = (S, a, b, S, (S, aSb), (S, ab)) poate fi descrisă în prolog astfel (folosind --> în loc de ::= ):

s --> [a],[b]. s --> [a],s,[b].

Pentru a vedea dacă un cuvânt aparţine sau nu limbajului generat de gramatica dată, formulăm o întrebare privitoare la simbolul de start. De exemplu ?- s([a,a,a,b,b,b], X). X = [] ?- s([a,a,b,b,x,y],Y). Y = [x, y] Dacă dorim generarea tuturor cuvintelor limbajului atunci formulăm întrebarea: ?- s(Y, []).

9.3 Limbajul XML Metalimbajul XML (eXtensible Markup Language – apărut în anul 1996) a fost definit pentru a descrie limbaje de marcare. Se bazează pe SGML (Standard Generalized Markup Language – apărut în anul 1980) şi este un set de reguli, specificaţii şi convenţii pentru structurarea datelor în fişiere text. Similar cu HTML şi XHTML, metalimbajul XML utilizează tag-uri (cuprinse între caracterele "<" şi ">") şi atribute (de forma nume = "valoare") care apar în interiorul tag-urilor.

Spre deosebire de HTML care indică modul de vizualizare a informaţiei de către navigatoarele Web, limbajul XML foloseşte tag-uri doar pentru a delimita datele, iar interpretarea este dată de aplicaţia care utilizează descrierea. Astfel, se specifică doar structura documentului, nu şi semantica acestuia.

Din punct de vedere formal, un document XML constă din următoarele construcţii:

a) comentarii – ignorate de procesoarele XML; b) referinţe de entităţi – predefinite (amp, lt, gt, apos, quot – închise între & şi ;)

şi altele; c) referinţe de caractere;

3 în sensul gramaticilor formale

d) instrucţiuni de procesare (PI -– Processing Instruction – informaţii de transmis interpretoarelor XML şi altor programe);

e) secţiuni CDATA (o secţiune CDATA este utilă atunci când se stochează text formatat, dar care nu trebuie interpretat, de exemplu, specificarea unui titlu: <![CDATA[<TITLE>Acesta este un titlu !</TITLE>]]>

f) STag - tag-uri de început, de forma <numetag>; g) ETag - tag-uri de sfârşit, de forma </numetag>; h) TagVid - elemente vide, de exemplu: <IMG SRC="image.jpg" />; i) declaraţii pentru tipul documentului.

Folosind notaţia EBNF4, gramatica limbajului XML, Versiunea 1.0, este dată prin producţiile: Caracter ::= #x09 | #x0A | #x0D | [#x20-#xD7FF] |

[#xE000-#xFFFD] | [#x10000-#x10FFFF] Comentariu ::= '' Referinţă ::= Referinţă-entitate | Referinţă-caracter Referinţă-entitate ::= '&' Nume ';' Referinţă-caracter ::= '&#' [0-9]+ ';' | '&#x' [0-9a-fA-F]+ ';' S ::= (#x0020 | #x0009 | #x0000D | #x000A)+ Nume ::= (Literă | '_' | ':') (Caracter-pt-nume)* PI ::= '<?' NumePI (S (Caracter* - (Caracter* '?>' Caracter*)))? '?>' NumePI ::= Nume - (('X' | 'x') ('M' | 'm') ('L' | 'l')) CDSect ::= CDStart CData CDEnd CDStart ::= '<![CDATA[' CData ::= (Car* - (Car* ']]>' Car*)) CDEnd ::= ']]>' TagVid ::= '<' Nume (S Atribut)* S? '/>' DocumentXML ::= Parte_1 Element Diverse* Parte_1 ::= XMLDecl? Diverse* (Decl-tipdoc Diverse*)? XMLDecl ::= '<?xml' VerInfo Decl-codificare? SDDecl? S? '?>' VerInfo ::= S 'version' Eq ("'" VerNum "'" | '"' VerNum '"') Eq ::= S? '=' S? 4 Notaţia Backus-Naur extinsă constă din construcţii de forma simbol ::= expresie (notaţie utilizată, în acest document, pentru specificarea regulilor de rescriere). Pentru XML sunt utilizate următoarele notaţii: • #xNNNN - NNNN este un întreg hexazecimal, iar expresia reprezintă caracterul în formatul ISO

10646 pentru care şirul de biţi (UCS-4), interpretaţi ca un număr întreg fără semn au valoarea indicată.

• [a-zA-Z], [#xNNNN-#xNNNN] - orice caracter din domeniul specificat. • [^a-z], [^#xNNNN-#xNNNN] - orice caracter din afara domeniului precizat. • [^abc], [^#xNNNN#xNNNN#xNNNN] - orice caracter care nu este printre caracterele date. • "şir" - un literal şir de caractere între ghilimele. • 'şir' - un literal şir de caractere între apostrofuri. • a b - a urmat de b. • a | b - a sau b, dar nu ambele. • a ñ b - mulţimea de şiruri reprezentate prin a, dar nu reprezentate prin b. • a? - a sau nimic. • a+ - una sau mai multe apariţii ale lui a. • a* - zero sau mai multe apariţii ale lui a. • %a - un parametru poate apărea în text acolo unde poate apărea a. • (expresie) - scrierea unei expresii între paranteze impune tratarea expresiei ca o unitate şi aceasta

poate conţine operatorul prefix % sau operatorii sufix: ?, * sau +. • /* ... */ - un comentariu.

VerNum ::= '1.0' Diverse ::= Comentariu | PI | S Decl-tipdoc ::= '<!DOCTYPE' S Nume (S ExternID)? S? ('[' IntSubset ']' S?)? '>' Element ::= TagVid | STag Conţinut ETag STag ::= '<' Nume (S Atribut)* S? '>' Atribut ::= Nume Eq Valoare-atribut ETag ::= '</' Nume S? '>' Se-ignoră ::= [#x200C-#x200F] | [#x202A-#x202E] | [#x206A-#x206F] | #xFEFF Caracter-pt-nume ::= Literă | Cifră | '.' | '-' | '_' | ':' |

Caracter-combinat | Se-ignoră | Extensie Literă ::= Caracter-de-bază | Caracter-ideografic PCData::= [^<&]* Hexa ::= [0-9a-fA-F] Şir-nume ::= Nume (S Nume)* Nmtoken ::= (Caracter-pt-nume)+ Şir-Nmtoken ::= Nmtoken (S Nmtoken)* Valoare-entitate ::= '"' ([^%&"] | Referinţă-PE | Referinţă)* '"'|

"'" ([^%&'] | Referinţă-PE | Referinţă)* "'" Valoare-atribut ::= '"' ([^<&"] | Referinţă)* '"' |

"'" ([^<&'] | Referinţă)* "'" LiteralSalt ::= ('"' [^"]* '"') | ("'" [^']* "'") URLcar::= /* Conform W3C RFC 1738 */ Literal-sistem::= '"' URLcar* '"' | "'" (URLcar - "'")* "'" PubidLiteral ::= '"' PubidCar* '"' | "'" (PubidCar - "'")* "'" PubidCar ::= #x20 | #xD | #xA | [a-zA-Z0-9] | [-'()+,./:=?;!*#@$_%] CarData ::= [^<&]* - ([^<&]* ']]>' [^<&]*) Separator-declarare ::= Referinţă-PE | S IntSubset ::= (Declarare-markup | Separator-declarare)* Declarare-markup ::= Declarare-element | Declarare-atribut | Declarare-entitate |

Declarare-notaţie | PI | Comentariu ExtSubset ::= Declarare-text? Declarare-extSubset Declarare-extSubset ::= (Declarare-markup | conditionalSect |

Separator-declarare)* SDDecl ::= S 'standalone' Eq (("'" ('yes' | 'no') "'") | ('"' ('yes' | 'no') '"')) Conţinut ::=

CarData? ((Element | Referinţă | CDSect | PI | Comentariu) CarData?)* Declarare-element ::= '<!ELEMENT' S Nume S Specificare-conţinut S? '>' Specificare-conţinut ::= 'EMPTY' | 'ANY' | Mixt | Fiu Fiu ::= (Alternativă | Secvenţă) ('?' | '*' | '+')? Cp ::= (Nume | Alternativă | Secvenţă) ('?' | '*' | '+')? Alternativă ::= '(' S? Cp ( S? '|' S? Cp )+ S? ')' Secvenţă ::= '(' S? Cp ( S? ',' S? Cp )* S? ')' Mixt ::= '(' S? '#PCDATA' (S? '|' S? Nume)* S? ')*' | '(' S? '#PCDATA' S? ')' Declarare - atribut ::= '<!ATTLIST' S Nume Definire-atribut* S? '>' Definire -atribut ::= S Nume S Tip-atribut S Declarare-implicită Tip-atribut ::= TipString | TipLexical | TipEnumerativ TipString ::= 'CDATA' TipLexical ::= 'ID' | 'IDREF' | 'IDREFS' | 'ENTITY' | 'ENTITIES' |

'NMTOKEN' | 'NMTOKENS'

TipEnumerativ ::=TipNotaţie | Enumerare TipNotatie ::= 'NOTATION' S '(' S? Nume (S? '|' S? Nume)* S? ')' Enumerare ::= '(' S? Nmtoken (S? '|' S? Nmtoken)* S? ')' Declarare-implicită ::= '#REQUIRED' | '#IMPLIED' |

(('#FIXED' S)? Valoare-atribut) ConditionalSect ::= IncludeSect | IgnorăSect IncludeSect ::= '<![' S? 'INCLUDE' S? '[' Declarare-extSubset ']]>' IgnorăSect ::= '<![' S? 'IGNORE' S? '[' IgnorăSectConţinut* ']]>' IgnorăSectConţinut ::= Ignoră ('<![' IgnorăSectConţinut ']]>' Ignoră)* Ignoră ::= Car* - (Car* ('<![' | ']]>') Car*) Referinţă-PE ::= '%' Nume ';' Declarare-entitate ::= GEDecl | PEDecl GEDecl ::= '<!ENTITY' S Nume S Definire-entitate S? '>' PEDecl ::= '<!ENTITY' S '%' S Nume S PEDef S? '>' Definire-entitate ::= Valoare-entitate | (ExternID Declarare-NData?) PEDef ::= Valoare-entitate | ExternID ExternID ::= 'SYSTEM' S Literal-sistem |

'PUBLIC' S PubidLiteral S Literal-sistem Declarare-NData ::= S 'NDATA' S Nume Declarare-text ::= '<?xml' VerInfo? Decl-codificare S? '?>' ExtTradEnt ::= Declarare-text? Conţinut Decl-codificare ::= S 'encoding' Eq ('"' Nume-cod '"' | "'" Nume-cod "'" ) Nume-cod ::= [A-Za-z] ([A-Za-z0-9._] | '-')* Declarare-notaţie ::= '<!NOTATION' S Nume S (ExternID | PublicID) S? '>' PublicID ::= 'PUBLIC' S PubidLiteral NumeDiverse::= '.' | '-' | '_' | Car-combinat | Ignorabil | Extindere Ignorabil::= [#x200C-#x200F] | [#x202A-#x202E] | [#x206A-#x206F] | #xFEFF Exemplu: Secvenţa XML următoare ilustrează definirea înregistrărilor tip bază de date:

<?XML version = "1.0" ?> <!DOCTYPE DOCUMENT [

<!ELEMENT DOCUMENT (CLIENT)*> <!ELEMENT CLIENT (NUMESIPRENUME, DATA, COMENZI)> <!ELEMENT NUMESIPRENUME (NUME, PRENUME)> <!ELEMENT NUME (#PCDATA)> <!ELEMENT PRENUME (#PCDATA)> <!ELEMENT DATA (#PCDATA)> <!ELEMENT COMENZI (POZITIE)*> <!ELEMENT POZITIE (PRODUS, NUMAR, PRET)> <!ELEMENT PRODUS (#PCDATA)> <!ELEMENT NUMAR (#PCDATA)> <!ELEMENT PRET (#PCDATA)> ]>

<DOCUMENT> <!—Date despre clienti--> <CLIENT> <NUMESIPRENUME> <NUME>Ionescu</NUME>

<PRENUME>Marian</PRENUME> </NUMESIPRENUME> <DATA>Februarie 23, 2005</DATA> <COMENZI> <POZITIE> <PRODUS>CAIET DICTANDO</PRODUS> <NUMAR>15</NUMAR> <PRET>25000</PRET> </POZITIE> <POZITIE> <PRODUS>CRETA</PRODUS> <NUMAR>10</NUMAR> <PRET>15000</PRET> </POZITIE> </COMENZI> </CLIENT> <CLIENT> <NUMESIPRENUME> <NUME>Popescu</NUME> <PRENUME>Alexandru</PRENUME> </NUMESIPRENUME> <DATA>Februarie 24, 2005</DATA> <COMENZI> <POZITIE> <PRODUS>CARTE</PRODUS> <NUMAR>1</NUMAR> <PRET>500000</PRET> </POZITIE> <POZITIE> <PRODUS>CD AUDIO</PRODUS> <NUMAR>10</NUMAR> <PRET>150000</PRET> </POZITIE> </COMENZI> </CLIENT> </DOCUMENT>

10. Introducere în analiza sintactică

10.1 Problema recunoaşterii

Fără a face apel la sisteme LBA, putem justifica, direct, decidabilitatea problemei apartenenţei pentru gramatici dependente de context. Propoziţia 10.1 [Gramaticile dependente de context sunt recursive1.] Există un algoritm care pentru orice G = (Ω, Σ, S, P) - gramatică dependentă de context – şi orice w ∈ Σ+ decide dacă afirmaţia “w ∈ L(G)” este adevărată. Propoziţia 10.2 Există un algoritm care să determine, pentru o gramatică independentă de context G = (Ω, Σ, S, P) şi un cuvânt w ∈ Σ*, dacă w ∈ L(G) sau w ∉ L(G). Algoritmul Cocke-Younger-Kasami (CYK)

În sprijinul demonstraţiei propoziţiei 10.2 se poate utiliza gramatica G = (Ω, Σ, S, P) în forma normală Chomsky şi se obţine un algoritm cu complexitate O(m3). Fie w ∈ Σ+, w = a1a2…am (|w| = m). Algoritmul CYK propus de Cocke, Younger şi Kasami, în 1967, generează submulţimile Vi,j = X | X ∈ Ω, X → aiai+1…ai+j-2ai+j-1, j = 1, 2, …, m, i = 1, 2, …, m – j + 1. Acestea se pot obţine, inductiv, astfel:

Vi,1 = X | X ∈Ω, X ::= ai ∈ P, i = 1, 2, ..., m Vi,j = X | X ∈Ω, X → YZ, Y a→*

iai+1…ai+k-1, Z a→*

i+k…ai+j-1; k = 1, 2, …, j-1 = = X | X ∈ Ω, X → YZ ∈ P, Y ∈ Vi,k, Z ∈ Vi+k, j-k; k = 1, 2, …, j - 1,

j = 1, 2, …, m, i = 1, 2, …, m – j + 1. Această scriere rezultă din proprietatea de localizare (propoziţia 2.1) şi din faptul că dacă k < j şi j - k < j atunci mulţimile Vi,k şi Vi+k, j-k sunt deja calculate.

1 În teoria algoritmilor, o gramatică formală G se numeşte recursivă dacă există un algoritm care acceptă, la intrare, orice cuvânt w peste vocabularul terminal şi produce, la ieşire, răspunsul la întrebarea: “w ∈ L(G)? “ Nu trebuie să confundăm această noţiune cu cea referitoare la recursivitatea la stânga (resp. dreapta) a gramaticilor, introdusă prin definiţia 2.10.

Obiectivul final constă în obţinerea muţimii V1,m. Într-adevăr w ∈ L(G) dacă şi numai dacă S w, dacă şi numai dacă S ∈ V→*

1,m. Cele descrise mai sus pot fi organizate algoritmic astfel:

1. Pentru fiecare i de la 1 la m execută Vi,1 := X | X ∈ Ω, X ::= ai ∈ P; 2. Pentru fiecare j de a 1 la m şi pentru fiecare i de la 1 la m – j + 1 execută:

a) Vi,j := ∅; b) Pentru fiecare k de la 1 la j-1 execută

Vi,j := Vi,j ∪X | X → YZ ∈ P, Y ∈ Vi,k, Z ∈ Vi+k, j-k; 3. Dacă S ∈ V1,m atunci w ∈ L(G).

Propoziţia 10.3 Algoritmul CYK (Cocke, Younger şi Kasami) calculează mulţimile Vi,j (j = 1, 2, …, m; i = 1, 2, …, m – j + 1) folosind O(m3) operaţii de reuniune. Definiţia 10.1 [Analiza sintactică] Fie G = (Ω, Σ, S, P) o gramatică independentă de cotext şi w ∈ L(G) . Presupunem că regulile (producţiile) gramaticii G sunt numerotate2. O analiză sintactică stânga a cuvântului w ∈ L(G) este şirul de numere χ = p1p2…ph, unde h este lungimea derivării stângi a cuvântului w din simbolul de start S, iar pi ( i = 1, 2, …, h) este numărul de ordine al producţiei aplicate la pasul i. Pentru obţinerea analizei stângi a unui cuvânt w generat de gramatica G se poate utiliza o procedură recursivă inspirată de schema algoritmului CYK. Se presupune, în continuare, că G este în forma normală Chomsky. Urmând descrierea algoritmilor recursivi din Albeanu(2000), procedura ANALIZA, care furnizează analiza stângă, are următorul cod (în limbaj algoritmic):

Integer n(100); Integer h; Procedure Analiza (i, j, A) Integer i, j; Neterminal A; SEQ if (j = 1) then SEQ h := h + 1; n[h] := #(A ::= ai); END else SEQ If (există k astfel încât

2 De obicei se utilizează simbolul # pentru a indica indexul unui obiect. Prin urmare indexul producţiei A ::= α ∈ P, va fi #(A ::= α).

k = mins | s = 1, 2, …, j-1, A ::= BC ∈ P, B ∈ Vis , C ∈ Vi+s, j-

s) then SEQ h := h+1; n[h] := #(A ::= BC); if (k < j-k) then SEQ Analiza(i, k, B); Analiza(i+k, j-k, C); END else SEQ Analiza(i+k, j-k, C); Analiza(i, k, B); END; END END END

Procedura este apelată prin Analiza(1, |w|, S) numai dacă algoritmul CYK a furnizat rezultatul “w ∈L(G)”. Valoarea variabilei h va fi majorată de valoarea [log2|w|].

Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Definiţia 10.1 poate fi prelungită pentru toate formele propoziţionale (vezi definiţia 2.4) γ ∈ (Ω ∪ Σ)*. Se va defini analiza sintactică parţial stângă. Definiţia 10.2. [Analiza sintactică parţial stângă (resp. dreaptă)] Fie G = (Ω, Σ, S, P) o gramatică independentă de context şi γ ∈ (Ω ∪ Σ)* o formă propoziţională. O analiză sintactică parţial stângă (resp. dreaptă) pentru γ este şirul de numere de producţii χ astfel încât S γ (stânga→χ

→χ

3) (resp. S γ (dreapta4)).

Prin analiza sintactică se memorează chiar arborele de derivare al cuvântului w sau al formei propoziţionale γ. Practic arborele de derivare se poate obţine, sistematic, în două moduri: descendent (eng. Top-down) prin utilizarea unei derivări extrem stângi, respectiv ascendent (eng. Bottom-up) prin utilizarea unei derivări extrem drepte.

10.2 Analiza sintactică descendentă Procesarea sintactică top-down cere ca gramatica în raport cu care se face analiza să nu fie recursivă la stânga. Aceasta face ca lungimea oricărei analize sintactice să fie finită. Mai precis se poate formula:

3 Producţiile se aplică într-o derivare extrem stânga (definiţia 2.8). 4 Producţiile se aplică într-o derivare extrem dreapta (definiţia 2.8).

Propoziţia 10.4 Fie G = (Ω, Σ, S, P) o gramatică independentă de context, nerecursivă la stânga şi A wXu (stânga). Atunci există o constantă reală pozitivă, c, astfel încât

→χ

|χ| ≤ c|w|+2.

Algoritmul general de analiză sintactică descendentă este de tip backtracking (încearcă să treci mai departe; dacă nu se poate atunci vei reveni). Pentru descrierea acestuia, introducem câteva notaţii şi convenţii similare celor din Atanasiu(1987):

• Pentru fiecare A ∈ Ω, alternativele lui A vor fi indexate astfel: A ::= γ1 | γ2 |… | γk(A), iar indexul lui γi va fi Ai, i = 1, 2, …, k(A).

• Structura (s, i, α, β) se numeşte configuraţie a algoritmului de analiză sintactică descendentă dacă s ∈ q, r, t, e şi reprezintă starea algoritmului (q – starea curentă, r – starea de revenire, t – starea de terminare şi e – starea de eroare), i este poziţia simbolului analizat (se consideră că al n+1-lea symbol de intrare este $ şi diferă de toate simbolurile alfabetului de intrare), α este o listă gestionată ca o stivă cu vârful la dreapta, iar β este o listă gestionată ca o stivă cu vârful la stânga.

• Configuraţia iniţială a algoritmului este (q, 1, λ, S$). Algoritmul are la bază evoluţia configuraţiilor. Regulile evolutive sunt:

• R1 [Prima alternativă] Fie A ::= γ1 ∈ P prima alternativă în cazul listei A-producţiilor. Atunci:

(q, i, α, Aβ) |- (q, i, αA1, γ1β). • R2 [Potrivire şi înainte] Dacă a = ai (i ≤ n) atunci

(q, i, α, aβ) |- (q, i+1, αa, β). • R3 [Nepotrivire şi prima revenire] Dacă a ≠ ai (i ≤ n) atunci

(q, i, α, aβ) |- (r, i, α, aβ). • R4 [Acceptare] Se ajunge la configuraţia de acceptare prin tranziţia:

(q, n+1, α, $) |- (t, n+1, α, λ). • R5 [Înapoi] Pentru oricare a ∈ Σ,

(r, i, αa, β) |- (r, i-1, α, aβ). • R6 [Ramificare] Celelalte situaţii sunt cuprinse în următoarea

procedură decizională:

(r, i, αAj, γj β) |-

===+

≤+++

altfel.),,,,(][,,1),,,1,(

][1),,,,( 11

βαλα

βγα

AirSkjSAiAne

AkjAiq

j

jj

• R7 [Obţinerea analizei stângi] Analiza stângă a cuvântului w se obţine prin aplicarea homomorfismului g(a) = λ, a ∈ Σ; g(Ai) = m unde m este indexul producţiei A ::= γi ∈ P.

Paşii algoritmului sunt:

1. Folosind regulile R1-R6, se efectuează tranziţia (q, 1, λ, S$) | (p, n+1, α, $). →*

2. Dacă p = t atunci obţine g(w) – Regula R7 - analiza stângă a cuvântului w, STOP.

3. Dacă p = e atunci EROARE şi STOP.

10.3 Analiza sintactică ascendentă

În contextul analizei sintactice ascendente se doreşte obţinerea unei derivări extrem dreapta pornind de la cuvântul analizat w, înapoi spre simbolul de start. La fiecare pas se încearcă identificarea porţiunii (cea mai din dreapta) din forma propoziţională curentă care reprezintă membrul drept al unei producţii a gramaticii. Prin înlocuirea acesteia cu membrul stâng al producţiei, are loc un proces de reducere şi se obţine forma propoziţională precedentă. Dacă, în final, se ajunge la S atunci cuvântul w este acceptat (a se vedea şi modul de prelucrare al algoritmului CYK). Nu pentru orice gramatică independentă de context se poate face acest lucru. Trebuie ca gramatica în raport cu care se face analiza să fie aciclică5 şi fără λ-producţii. Propoziţia 10.5 Fie G = (Ω, Σ, S, P) o gramatică independentă de context, fără λ-producţii şi aciclică, w ∈ Σ*, iar A uXw (dreapta). Atunci există o constantă reală pozitivă, c, astfel încât

→χ

|χ| ≤ c|w|. Algoritmul general de analiză sintactică ascendentă este de tip deplasare-reducere. Pentru descrierea acestuia, introducem câteva notaţii şi convenţii similare celor din descrierea algoritmului de analiză descendentă.

• Se presupune că fiecare producţie are un index. • Fie D – un simbol care semnifică acţiunea de deplasare cu o poziţie

la dreapta în timpul parcurgerii cuvântului w (= a1a2...an) a cărui analiză se doreşte.

→*5 O gramatică este aciclică dacă nu conţine reguli astfel încât să fie posibile derivări de forma A A.

• Structura (s, i, α, β) se numeşte configuraţie a algoritmului de analiză sintactică ascendentă dacă s ∈ q, r, t, e şi reprezintă starea algoritmului (q – starea curentă, r – starea de revenire, t – starea de terminare şi e – starea de eroare), i este poziţia simbolului analizat, α este o listă gestionată ca o stivă cu vârful la dreapta, iniţial conţinând un simbol special, notat $ şi apoi cuvinte peste Ω ∪ Σ ∪ $, numită şi lista pushdown, iar β este o listă gestionată ca o stivă cu vârful la stânga şi care conţine cuvinte peste D ∪ i | i = 1, 2, ..., |P|.

• Configuraţia iniţială a algoritmului este (q, 1, $, λ). Algoritmul are la bază evoluţia configuraţiilor. Regulile evolutive sunt:

• R1 [Deplasare] Când nu se pot face reduceri, atunci se fac deplasări conform schemei: (q, i, α, β) |- (q, i + 1, αai, Dβ).

• R2 [Reducere] Dacă X ::= α este producţia cu indexul p (cel mai mic) pentru care în lista pushdown se află un obiect al derivării, atunci

(q, i, uα, β) |- (q, i, uX, pβ). • R3 [Eroare] (q, n + 1, α, Dn) |- (e, n + 1, α, Dn). • R4 [Acceptare] Se ajunge la configuraţia de acceptare prin tranziţia:

(q, n +1, $S, α) |- (t, n+1, λ, α). Analiza lui w este χ = h(α) unde h este homomorfismul dat de h(p) = p, p = 1, 2, .., |P|, h(D) = λ.

• R5 [Revenire] Dacă nu se mai poate face nici o reducere, iar lista pushdown conţine altceva decât $S,

(q, n + 1, α, β) |- (r, n + 1, α, β). • R6 [Revenire] Celelalte situaţii necesită revenirea în procesul de

analiză şi sunt cuprinse în următoarea listă: 1. (r, n+1, uX, pv) |- (r, n+1, uβ, v) dacă X ::= β este producţia

cu indexul p şi împiedică reducerile. 2. (r, i, uX, pv) |- (q, i, u’X’, p’v) dacă X ::= β este producţia cu

indexul p şi X’ ::= β’ are indexul p’, p’ > p şi poate conduce la reduceri. Trebuie ca uβ = u’β’, iar p’ este cel mai mic cu această proprietate.

3. (r, i, ua, Dv) |- (r, i-1, u, v), a ∈ Σ. 4. (r, i, X, pv) |- (q, i + 1, uβai, Dv) dacă i ≤ n, X ::= β este a p-a

alternativă şi ultima posibilă pentru a se încerca reduceri. Paşii algoritmului sunt:

1. Folosind regulile R1-R6, se efectuează tranziţia (q, 1, $, λ) | (p, n+1, α, β). →*

2. Dacă p = t atunci obţine h(β) – analiza dreaptă a cuvântului w, STOP.

3. Dacă p = e atunci EROARE şi STOP. Comentariu. Creşterea performanţelor algoritmilor de analiză sintactică se obţine prin introducerea unor restricţii asupra regulilor gramaticilor. Doar informativ, enumerăm aici clasele speciale de gramatici LL(k) LR(k), de precedenţă etc. Algoritmi speciali pentru analiză sintactică sunt trataţi în domeniul tehnicilor de compilare.

Limbaje formale şi automate Lista problemelor propuse 1. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L = anbn | n ≥ 0. a) Ω = S, Σ= a, b, P = aSb ::= S, λ ::= S b) Ω = S, Σ= a, b, P = S ::= aSb, S ::= λ c) Ω = S, Σ= a, b, P = S ::= aSb, S ::= ab d) Ω = S, Σ= a, b, P = aSb ::= S, ab ::= S 2. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L = anbn | n > 0. a) Ω = S, Σ= a, b, P = aSb ::= S, λ ::= S b) Ω = S, Σ= a, b, P = S ::= aSb, S ::= λ c) Ω = S, Σ= a, b, P = S ::= aSb, S ::= ab d) Ω = S, Σ= a, b, P = aSb ::= S, ab ::= S 3. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L = anbncmdm | n > 0, m > 0. a) Ω = S, A, B, Σ= a, b, c, d, P = aAb ::= A, ab ::= A, cBd ::= B, cd ::= B, AB ::= S, λ ::= S b) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, A ::= λ, B ::= cBd, B ::= cd, B ::= λ c) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd, S ::= λ d) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd 4. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L = anbncmdm | n ≥ 0 , m ≥ 0. a) Ω = S, A, B, Σ= a, b, c, d, P = aAb ::= A, ab ::= A, cBd ::= B, cd ::= B, AB ::= S, λ ::= S b) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, A ::= λ, B ::= cBd, B ::= cd, B ::= λ c) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd, S ::= λ d) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd 5. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L = anbncmdm | n ≥ 1 , m ≥ 1 ∪ λ. a) Ω = S, A, B, Σ= a, b, c, d, P = aAb ::= A, ab ::= A, cBd ::= B, cd ::= B, AB ::= S, λ ::= S b) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, A ::= λ, B ::= cBd, B ::= cd, B ::= λ

c) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd, S ::= λ d) Ω = S, A, B, Σ= a, b, c, d, P = S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd 6. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L = anbmcmdn | n ≥ 1 , m ≥ 1. a) Ω = S, X, Σ= a, b, c, d, P = bXc ::= X, bc ::= X, aSd ::= S, ad ::= S, λ ::= S b) Ω = S, A, Σ= a, b, c, d, P = S ::= aSd, S ::= aAd, A ::= bAc, A ::= bc c) Ω = S, X, Y, Σ= a, b, c, d, P = S ::= XY, X ::= aXb, X ::= ab, Y ::= cYd, Y ::= cd, S ::= λ d) Ω = S, X, T, Σ= a, b, c, d, P = S ::= XT, X ::= aXb, X ::= ab, T ::= cTd, T ::= cd 7. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă pentru a genera limbajul L format din şiruri de biţi (literele 0 şi 1 a căror lungime este multiplu de trei. a) Ω = S, A, B, Σ= 0, 1, P = S ::= 0A, S ::= 1A, S ::= λ, A ::= 0B, A ::= 1B, B ::= 0S, B :: = 1S b) Ω = S, A, B, Σ= 0, 1, P = S ::= 0A, S ::= 1A, A ::= λ, A ::= 0B, A ::= 1B, B ::= 0S, B :: = 1S, B ::= λ c) Ω = S, A, B, Σ= 0, 1, P = S ::= 0A, S ::= 1A, S ::= λ, A ::= λ, A ::= 0B, A ::= 1B, B ::= 0S, B :: = 1S, B ::= λ d) Ω = S, X, T, Σ= 0, 1, P = S ::= XT, X ::= 0X1, X ::= 01, T ::= 0T1, T ::= 01 8. Alegeţi gramatica formală G = (Ω, Σ, P, S) corectă, dar cu număr minim de simboluri neterminale, pentru a genera limbajul L format din şiruri de biţi (literele 0 şi 1 a căror lungime este multiplu de trei. a) Ω = S, Σ= 0, 1, P = S ::= S000, S ::= S001, S ::= S010, S ::= 011S, S ::= 100S, S ::= S101, S :: = 110S, S ::= 111S, S ::= λ b) Ω = S, Σ= 0, 1, P = S ::= 000S, S ::= 001S, S ::= 010S, S ::= 011S, S ::= 100S, S ::= 101S, S :: = 110S, S ::= 111S, S ::= λ c) Ω = S, A, B, Σ= 0, 1, P = S ::= 0A, S ::= 1A, S ::= λ, A ::= λ, A ::= 0B, A ::= 1B, B ::= 0S, B :: = 1S, B ::= λ d) Ω = S, X, T, Σ= 0, 1, P = S ::= XT, X ::= 0X1, X ::= 01, T ::= 0T1, T ::= 01 9. Se consideră variantele a) regulat b) independent de context c) dependent de context 1[]. Alegeţi tipul limbajului L = anbn | n ≥ 1 2[]. Alegeţi tipul limbajului L = an| n ≥ 1 3[]. Alegeţi tipul limbajului L = anbmcmdn | n ≥ 1, m ≥ 1 4[]. Alegeţi tipul limbajului L = ab, aabb, aaabbb 5[]. Alegeţi tipul limbajului L = w | w∈0, 1*, w conţine un număr egal de simboluri 0 şi 1, adică N0(w) = N1(w). 6[]. Alegeţi tipul limbajului L = w | w∈0, 1*, w nu conţine subşirul 011. 7[]. Alegeţi tipul limbajului L = xmyn| n<m sau 2*m<n, n, m>0

8[]. Alegeţi tipul limbajului L = ambncpdq | m+n = p+q, m, n, p, q ≥ 0 9[]. Alegeţi tipul limbajului L = ambn | n < m< 2*n, n, m > 1 10[]. Alegeţi tipul limbajului L = w ∈ a, b* | w = Răsturnat(w) 11.[] Alegeţi tipul limbajului L = w ∈ a, b* | simbolul a apare de un număr par de ori 12[]. Alegeţi tipul limbajului L = w ∈ a, b* | simbolul a apare de două ori mai des decât simbolul b 13[] Alegeţi tipul limbajului L = anbncn | n ≥ 1 14[] Alegeţi tipul limbajului L = ambncmdn | m, n ≥ 1 15[] Alegeţi tipul limbajului L = anbncnd | n ≥ 1 10. Răspunsul cerinţei următoare poate fi ‘adevărat’ sau ‘fals’. 16[]. Să se verifice dacă limbajul L = anbncn| n > 0 este independent de context. 17[]. Să se verifice dacă limbajul L = an | n = 2k, k>0 este independent de context. 18[]. Să se verifice dacă limbajul L = anbncm | n ≤ n ≤ 2*n, n ≥ 0 este independent de context. 19[]. Să se verifice dacă limbajul L = an | n = 10k, k ≥ 0 este independent de context. 20[]. Să se verifice dacă limbajul L = an | n = k2, k ≥ 0 este independent de context. 21[]. Să se verifice dacă limbajul L = an(bc)n | n ≥ 1 este independent de context. 22[]. Să se verifice dacă limbajul L = w c Răsturnat(w) | w ∈ a, b+, iar c ∉ a, b este independent de context. 23[] Să se verifice dacă limbajul L = an | n = 10k, k ≥ 0 este de tip 3 (regulat). 24[] Să se verifice dacă limbajul L = an | n = k2, k ≥ 0 este de tip 3 (regulat). 25[] Să se verifice dacă limbajul L = an | n ≥ 0 este de tip 3 (regulat). 26[] Să se verifice dacă limbajul L = ap | p număr prim nu este de tip 3 (regulat). 27[] Să se verifice dacă limbajul L = ambn | m şi n relativ prime, adică cmmdc(m, n) =1 nu este de tip 3 (regulat). 11. Fie expresiile regulate a) (a+b)*(aa+bb)(a+b)* b) (a+b)* c) a*ba*ba* d) ba* 28[]. Se consideră limbajul format din toate cuvintele peste a, b care încep cu b şi după care urmează 0, 1, 2 sau mai multe simboluri a. Alegeţi expresia regulată corespunzătoare. 29[]. Se consideră limbajul format din toate cuvintele peste a, b care conţin simbolul b exact de două ori. Alegeţi expresia regulată corespunzătoare. 30 []. Se consideră limbajul format din toate cuvintele peste a, b. Alegeţi expresia regulată corespunzătoare. 31[]. Se consideră limbajul format din toate cuvintele peste a, b care conţin consecutiv două simboluri a sau două simboluri b. Alegeţi expresia regulată corespunzătoare. 12. Se consideră gramatica G = (S, A, B, a, b, S, P), unde P = S ::= bA | aB, A ::= bAA | aS | a, B::= aBB | bS | b. G este în forma normală a) Chomsky b) Greibach

c) Nici una din formele menţionate 13. Unui automat pushdown îi corespunde o gramatică a) liniară la stânga b) liniară la dreapta c) independentă de context 14. Răspunsul cerinţei următoare poate fi ‘adevărat’ sau ‘fals’. 32[] Există un algoritm care verifică dacă limbajul recunoscut de un automat finit determinist este infinit. 33[] Familia limbajelor regulate nu este închisă la reuniune. 34[] Familia limbajelor independente de context este închisă la intersecţie. 35[] Familia limbajelor regulate este închisă la intersecţie. 36[] Un limbaj recunoscut de un sistem AFN este recunoscut şi de un sistem AFD. 37[] Un limbaj recunoscut de un automat pushdown cu stiva vidă este recunoscut şi de un automat pushdown cu stări finale. 38[] Un limbaj recunoscut de un automat pushdown cu stări finale nu poate fi recunoscut de nici un automat pushdown cu stiva vidă. 39[] Pentru orice gramatică independentă de context care generează un limbaj L, se poate construi un automat pushdown care recunoaşte limbajul L. 40[] Există limbaje recunoscute de automate pushdown care nu pot fi generate de gramatici independente de context. 15[]. Adevărat sau fals? Există clase de limbaje peste alfabetul Σ închise la substituţii finite şi intersecţie cu limbaje regulate, dar care nu sunt închise la transformări gsm. 16. Considerăm fraza C++ realizată pe baza specificaţiilor sintactice: class Sistem_AFD private: int numar_stari; int cardinal_sigma; int q0; int **delta; int *stari_accesibile; int n_accesibile; public: Sistem_AFD(); ~Sistem_AFD(); Determina_starile_accesibile(); Afisare_informatii(); Câte câmpuri de date va avea fiecare obiect al clasei Sistem_AFD? 17. Fie declaraţiile Prolog: delta(s1, a, s2). delta(s1, b, s3). delta(s2, a, s1). delta(s2, b, s4). delta(s3, a, s4).

delta(s3, b, s1). delta(s4, a, s3). delta(s4, b, s2). stare_initiala(s1). stare_finala(s1). Limbajul recunoscut de automatul specificat este format din: a) toate cuvintele cu un număr par de a şi un număr par de b b) toate cuvintele cu un număr impar de a şi un număr impar de b a) toate cuvintele cu un număr par de a şi un număr impar de b a) toate cuvintele cu un număr impar de a şi un număr par de b 18. Regulile evolutive ale algoritmului de analiză sintactica descendentă sunt: a) prima alternativă, b) potrivire şi înainte c) nepotrivire şi prima revenire d) acceptare e) inapoi f) ramificare g) obţinerea analizei stângi. Următoarea descriere reprezintă: 1[]. Se aplică tranziţia: (q, n+1, α, $) |- (t, n+1, α, λ). 2[]. Pentru oricare a ∈ Σ, (r, i, αa, β) |- (r, i-1, α, aβ). 3[]. Se utilizează procedura decizională:

(r, i, αAj, γj β) |-

===+

≤+++

altfel.),,,,(][,,1),,,1,(

][1),,,,( 11

βαλαβγα

AirSkjSAiAne

AkjAiq

j

jj

4[]. Se aplică homomorfismul g(a) = λ, a ∈ Σ; g(Ai) = m unde m este indexul producţiei A ::= γi ∈ P. 5[]. Dacă a ≠ ai (i ≤ n) atunci (q, i, α, aβ) |- (r, i, α, aβ). 6[]. Fie A ::= γ1 ∈ P prima regulă din lista A-producţiilor. Atunci:

(q, i, α, Aβ) |- (q, i, αA1, γ1β). 7[]. Dacă a = ai (i ≤ n) atunci (q, i, α, aβ) |- (q, i+1, αa, β). 19. Fie gramatica G = (S, A, a, b, S, (S, AA), (S, AS), (S, b), (A, SA), (A, AS), (A, a)) si w = abaab (|w| = 5). Algorimul CYK (Cocke, Younger, Kasami), la pasul al treilea produce: a. V[3][3]=A, S, V[3][2]=A, S, V[3][1]=A, S c. V[3][3]=A, S, V[3][2]=A, S, V[3][1]=S b. V[3][3]=A, S, V[3][2]=A, S, V[3][1]=A d. V[3][3]=A, S, V[3][2]=S, V[3][1]=A 20. Fie gramatica G = (S, a, b, S, S ::= aSB (1) | ab (2) şi cuvântul w = aaabbb. Analiza sintactică a cuvântului w este (între paranteze se află numărul producţiei): a) 112 b) 121 c) 211 21. Regulile evolutive ale algoritmului de analiză sintactica ascendentă sunt:

a) Deplasare b) Reducere c) Eroare d) Acceptare e) Revenire din motiv de reducere f) Revenire din alt motiv 8[]. (q, i, α, β) |- (q, i + 1, αai, Dβ). 9[]. Dacă X ::= α este producţia cu indexul p (cel mai mic) pentru care în lista pushdown se află un obiect al derivării, atunci (q, i, uα, β) |- (q, i, uX, pβ). 10[]. (q, n + 1, α, Dn) |- (e, n + 1, α, Dn). 11[]. (q, n +1, $S, α) |- (t, n+1, λ, α). 12[]. (q, n + 1, α, β) |- (r, n + 1, α, β). 13[]. (r, n+1, uX, pv) |- (r, n+1, uβ, v) dacă X ::= β este producţia cu indexul p şi împiedică reducerile. 14[]. (r, i, uX, pv) |- (q, i, u’X’, p’v) dacă X ::= β este producţia cu indexul p şi X’ ::= β’ are indexul p’, p’ > p şi poate conduce la reduceri. Trebuie ca uβ = u’β’, iar p’ este cel mai mic cu această proprietate. 15[]. (r, i, ua, Dv) |- (r, i-1, u, v), a ∈ Σ. 16[]. (r, i, X, pv) |- (q, i + 1, uβai, Dv) dacă i ≤ n, X ::= β este a p-a alternativă şi ultima posibilă pentru a se încerca reduceri. 22. Limbajul (ab)na | n>0 nu este ambiguu. 23. Gramatica ce contine reguli de forma S ::= if c then S else S | if c then S | a nu este ambigua 24. Un automat liniar mărginit nu recunoaşte limbaje independente de context 25. O maşină Turing nu recunoaşte limbaje regulate

1. Limbaje şi expresii regulate

Exemplul 1.1

Mulţimile V = a, b, c; Σ = 0, 1; VT = a1, a2, ..., an etc. sunt alfabete. Observaţia 1.1

Mulţimea Σ* este monoid în raport cu operaţia de concatenare a cuvintelor definită prin

xy = ai1ai2...airaj1aj2...ajs, dacă

x = ai1ai2...air, y = aj1aj2...,ajs, aip∈Σ (1 ≤ p ≤ r) şi ajq ∈Σ (1 ≤ q ≤ r),

deoarece operaţia de concatenare este asociativă, iar λ este element neutru. Observaţia 1.2

Dacă Σ0 = λ, Σ2 = ΣΣ (mulţimea cuvintelor de lungime 2), Σ3 = Σ2Σ (mulţimea cuvintelor de lungime 3), Σn = Σn-1Σ (mulţimea cuvintelor de lungime n; n>1), atunci

a) Σ* = U ; 0

Σ k

1≥

Σ k≥k

b) Σ+ = U . k

Exemplul 1.2 Următoarele construcţii descriu limbaje: 1) Σ = a, b, c, L1 = anbncn | n ≥ 1,

L2 = ap | p ∈ N*, p număr prim, L3 = xx | x∈Σ*.

2) Σ = 0, 1, L = x∈Σ* | x este scrierea binară a unui număr natural divizibil prin 5.

3) L = a3, a5. Observaţia 1.3

Lλ=λL=L; L∅ = ∅L = ∅,

pentru oricare limbaj L, unde ∅ este limbajul vid. Observaţia 1.4

Dacă L este un limbaj λ-liber (nu conţine cuvântul vid) atunci L+ = L* - λ. Cerinta 1.1 Dacă Σ este un alfabet, atunci Σ* este mulţime numărabilă. Demonstraţie. Presupunem card(Σ) = n şi Σ = x1, x2, …, xn. Construim funcţia bijectivă f pentru domeniul Σ* şi codomeniul N (mulţimea numerelor naturale). Fie w ∈ Σ*, atunci f(w) poate fi ales astfel:

≤≤≤≤==+++=

= − .1,1|,|,,,0

)(21

121 ksniwkxxxwninii

wwf

siiik

k kLL

λ

Cerinta 1.2. Fie mulţimea univers U, funcţia f : U → U şi B ⊆ U . Construim, în mod inductiv, şirul de mulţimi:

A0 = B; Ak+1 = Ak ∪ f(x) | x ∈ Ak, k ∈ N şi A = . Atunci: UNk∈

kA

kA

a) A este închisă faţă de f; b) Dacă mulţimea C este astfel încât B ⊂ C ⊆ U şi este închisă faţă de f atunci A⊆C. Demonstraţie. Fie x ∈ A. Există k ∈ N astfel încât x ∈ Ak. Prin urmare f(x) ∈ Ak+1⊂ A. Fie mulţimea C astfel încât B ⊂ C ⊆ U şi C închisă faţă de f. Evident A0 ⊂ C. Presupunem, prin inducţie că Ak ⊂ C. Fie y ∈ Ak+1 Cum Ak+1 = Ak ∪f(x) | x ∈ Ak, atunci fie y ∈ Ak (deci şi lui C), fie y = f(x) cu x ∈ Ak ⊆ C. Din închiderea lui C în raport cu f, rezultă y ∈ C.

Prin urmare ⊆C. UNk∈

Exemplul 1.3 a) L(0*1*2*)=0i1j2k | i, j, k ≥ 0. b) Expresiile b(ab)* şi (ba)*b sunt echivalente. c) L(ba*) este mulţimea cuvintelor, peste a, b, care încep cu b şi după

care urmează 0, 1, 2, … etc. simboluri a, adică L(ba*) = ban | n ≥ 0. d) L(a*ba*ba*) este mulţimea cuvintelor, peste a, b, care conţin simbolul

b exact de două ori. e) L((a+b)*) reprezintă mulţimea tuturor cuvintelor peste alfabetul a, b. f) L((a+b)*(aa+bb)(a+b)*) este mulţimea tuturor cuvintelor, peste a, b,

conţinând, consecutive, doua litere a sau b. Exemplul 1.4

Următoarele limbaje sunt mulţimi regulate: L1=an| n≥1; L2 = (ab)nc| n≥0; L3 = a,b*, etc.

Cerinta 1.3 [Identităţi cu expresii regulate]

Fie r, s şi t expresii regulate peste Σ. Atunci: a) r + s ∼ s + r, r + ∅ ∼ ∅ + r, r + r ∼ r, (r + s) + t ∼ r + (s + t); b) rλ ∼ λr ∼ r, r∅ ∼ ∅r ∼ ∅, (rs)t ∼ r(st); în general, comutativitatea

produsului nu are loc. c) r(s + t) ∼ rs + rt, (s + t)r ∼ sr + tr; d) r* ∼ r*r* ∼ (r*)* ∼ (λ+r)*, ∅* ∼ λ* ∼ λ; e) r* ∼ λ + r + r2 + r3 + … + rk + rk+1r*, pentru k ≥0. f) (r+s)* ∼ (r* +s*)* ∼ (r*s*)* ∼ (r*s)*r* ∼ r*(sr*)*. Expresiile (r+s)* şi

r*+s* nu sunt, în general, echivalente. g) r*r ∼ rr*, r(sr)* ∼ (rs)*r; h) (r*s)* ∼ λ + (r + s)*s, (rs*)* ∼ λ + r(r + s)*; i) Dacă λ∉L(s) atunci ((r ∼ sr + t) ⇔ r∼s*t ) şi ((r ∼ rs + t) ⇔ r ∼ ts*).

Demonstraţie. Folosind unele dintre identităţile a-h, demonstrăm afirmaţia i). Din r ∼ s*t rezultă r ∼ (λ + ss*)t ∼ λt + ss*t ∼ t + sr ∼ sr + t. Presupunem că λ ∉ L(s) şi că

r ∼ sr + t . Obţinem, succesiv, r ∼ sr + t ∼ s(sr + t) +t ∼ s2r + (st + t) ∼ s3r + (s2t + st + t) ∼ … ∼ sk+1r + (skt + sk-1t + … + st + t), pentru k ≥ 0. Arătăm că r ∼ s*t prin dublă incluziune. Fie x ∈ L(r) de lungime k := |x|. Deoarece r∼ sk+1r + (skt + sk-1t + … + st + t) şi λ ∉ L(s) rezultă că x ∉ sk+1r (este clar că L(sk+1) conţine cuvinte cu cel puţin k + 1 simboluri). Prin urmare x ∈ L(skt + sk-1t + … + st + t ) ⊂ L(s*t). Reciproc, fie x ∈ L(s*t), deci există i ≥ 0 astfel încât x ∈ L(sit). Dar, identitatea r∼ si+1r + (sit + si-1t + … + st + t) arată că L(r) ⊃ L(sit). Deci x ∈ L(r). Partea a doua a afirmaţiei se demonstrează similar.

2. Mecanisme generative fundamentale Exemplul 2.1

Fie V = S, A, B, C, a, * şi P = (S, BAB), (BA, BC), (CA, AAC), (CB, AAB), (A, a), (B, *). În cadrul sistemului de rescriere (V, P) sunt posibile generări de cuvinte precum:

a) B B B B; k

A2 →* 1+

→* k2

→* 1+

n

a 2

2na

→*

→*

→*

2k

Ab) B B * a *;

k

A2 c) B B * *;

k

A2 2k

ad) S * *. →*

Observaţia 2.1

Ansambul SR = (Ω ∪ Σ, P) este un sistem de rescriere pentru limbajul L(G) pornind de la şirul S. Metoda de generare pentru L(G) poate fi specificată prin structura (SR, S, Σ). = Exemplul 2.2 [akbk]

O gramatică care generează limbajul anbn | n≥1. este G=(S, a, b, S, (S, aSb), (S, ab). Se demonstrează, prin inducţie, că

FP(G) = akSbk | k ≥ 1 ∪ akbk | k ≥ 1. Prin urmare L(G) = akbk | k≥1. Exemplul 2.3 [Pătrate]

Fie Ω=S, A, B, X, Σ=a, % şi P = S ::= %% | %B% | %AABB%, %A ::= %XA, XA ::= AX, XB ::= AABX, X% ::= B%, A ::= a, B ::= a.

Gramatica G=(Ω, Σ, S, P) generează limbajul L = % % | n ≥ 0. Cerinta 2.1

Pentru orice gramatică de tip 2, G = (Ω, Σ, S, P) , dacă AB w, atunci există w1, w2 ∈ V* astfel încât: 1) w = w1w2 şi 2) A w→*

1, B w2. Demonstraţie. Fie n lungimea derivării AB w. Aplicăm metoda inducţiei după n. Pentru n = 0 (AB AB), luăm w

→*

→*

→*

→*

→*

1 = A şi w2 = B, iar afirmaţia este evidentă. Să presupunem că propoziţia este adevărată pentru orice derivare de lungime n. Fie AB w o derivare de lungime n + 1. Punem în evidenţă ultimul pas al derivării: AB α → w. Fie C ::= β a n + 1 producţie aplicată. Din ipoteza de inducţie rezultă: α = α

1α2, A α1, B α2. Neterminalul

C se află fie în α1, fie în α2. Să presupunem că C se află în α1, adică α1 = γ1Cγ2. Prin urmare AB γ→* →*

→* 1Cγ2α2 → γ1βγ2α2 = w. Luăm A γ1Cγ2 → γ1βγ2 =

α1 şi B α2. În general α1 şi α2 nu sunt determinate în mod unic. Cerinta 2.2

Pentru orice gramatică de tip 2, G = (Ω, Σ, S, P), există o gramatică echivalentă G’ = (Ω’, Σ, S, P’), de tip 2, în care toate producţiile lui P’ care conţin terminale sunt de forma A ::= a, a ∈ Σ. Demonstraţie. Pentru fiecare simbol terminal a ∈ Σ, se introduce un neterminal nou Xa. Se consideră: Ω’ = Ω ∪ Xa | a ∈ Σ, iar P’ se obţine din P înlocuind toate terminalele a cu neterminalul Xa şi adăugând, în final, producţiile Xa ::= a, a ∈ Σ. Este evident că se păstrează tipul gramaticii şi că L(G’) = L(G) Cerinta 2.3

Orice gramatică liniară la dreapta este echivalentă cu o gramatică de acelaşi tip, dar cu reguli de forma: A ::= aB sau A ::= a, unde A, B ∈ Ω, iar a ∈ Σ ∪ λ. Demonstraţie. Fie A ::= wB o regulă a gramaticii iniţiale, A, B ∈ Ω, w ∈ Σ*. Dacă |w| = 1, aceasta nu suferă nici o modificare, fiind în forma cerută. Presupunem că |w| = n > 1. Atunci w = a1a2…an, introducem n-1 simboluri neterminale noi B1, B2, …, Bn-1 şi înlocuim regula A::= wB cu mulţimea de reguli A ::= a1B1, B1 ::= a2B2, …, Bn-2 ::= an-1Bn-1, Bn-1 ::= anB. Dacă n = 0 (mai spunem că avem de-a face cu o redenumire) atunci parcurgem următoarele etape (a se vedea şi propoziţia 5.3). Iniţial, se determină mulţimea1 R(B) = D | D ∈Ω, B D. Regula A ::= B se înlocuieşte cu mulţimea de reguli A ::= αC| D ::= αC ∈ P, D ∈ R(B), α ≠ λ ∪ A ::= α| D ::= α ∈ P, D ∈ R(B).

→*

Fie A::= w o regulă a gramaticii iniţiale, A ∈ Ω şi w ∈ Σ*. Dacă n = |w| ≤ 1, aceasta rămâne neschimbată, altfel se consideră n-1 neterminale noi C1, C2, …,Cn-1, şi dacă w = a1a2…an, regula se înlocuieşte cu mulţimea de reguli A := a1C1, C1 ::= a2C2, …, Cn-2 ::= an-1Cn-1, Cn-1 ::= an. Se parcurg toate regulile gramaticii iniţiale şi se transformă ca mai sus. Trebuie avut în vedere ca regulile să fie înregistrate o singură dată. Exemplul 2.4

Fie gramatica G = (S, A, B, C, D, a, b, c, S, S ::= A | abcB, A ::= C | D, B ::= A | ab, C ::= S). Obţinem succesiv:

R(S) = A, C, D, S, R(A) = C, D, S, A, R(B) = A, C, D, S, R(C) = S, A, C, D, R(D) = ∅.

Considerăm regula S ::= abcB şi simbolurile X1, X2. Formăm mulţimea S1 = S ::= aX1, X1 ::= bX2, X2 ::= cB.

Pentru regula B ::= ab, considerăm simbolul X3 şi mulţimea de reguli P1 = B::=aX3, X3 ::= b.

În acest moment, regulile sunt:

1 R(B) reprezintă mulţimea redenumirilor directe sau prin simboluri intermediare ale neterminalului B.

S ::= A | aX1; X1 ::= bX2; A ::= C | D; X2 ::= cB; B ::= A | aX3; X3 ::= b. C ::= S;

Regula S ::= A se transformă în S ::= aX1 (care există deja), regula A::= C se transformă în A ::= aX1, regula A ::= D se elimină, regula B::=A se înlocuieşte cu B ::= aX1, iar regula C ::=S se înlocuieşte cu regula C ::= aX1. Gramatica G’ are mulţimea neterminalelor Ω’ = S, B, X1, X2, X3, aceeaşi mulţime de terminale, simbolul de start S şi mulţimea de reguli P’ = S ::= aX1, X1 ::= bX2, X2 ::= cB, B ::= aX1 | aX3, X3 ::= b. Se observă că simbolurile A, C şi D sunt inutile Regulile A ::= aX1 şi C ::= aX1 pot fi adăugate, dar în procesul de generare nu se vor aplica niciodată. Observaţia 2.2

Fie G o gramatică liniară la stânga, există o gramatică liniară la stânga G’ astfel încât L(G’) = L(G), iar regulile gramaticii G’ sunt numai de forma A ::= Ba şi A ::= a, unde A, B ∈ Ω, iar a ∈ Σ ∪ λ. Demonstraţie. Se procedează ca la demonstraţia propoziţiei 2.3. Cerinta 2.5

Fie G o gramatică în care producţiile sunt de forma A ::= Ba şi A ::= a. Atunci există o gramatică G’ echivalentă cu G pentru care producţiile sunt de forma A ::= aB şi A ::= a. Demonstraţie. Fie G = (Ω, Σ, S, P) gramatica dată. Construim G’=(Ω’, Σ, S’, P’), unde S’ este un neterminal nou, considerat ca axiomă în gramatica G’, Ω’ = Ω ∪ S’, iar P’ se obţine din P prin transformarea fiecărei producţii, după cum urmează:

1. A ::= a ∈ P ⇔ S’ ::= aA∈ P’, A ≠ S; 2. S ::= a ∈ P ⇔ S’ ::= aS ∈ P’ şi S’ ::= a ∈ P’; 3. A ::=Ba ∈ P ⇔ B ::= aA ∈ P’, A ≠ S; 4. S ::= Ba ∈ P ⇔ B ::= aS∈ P’ şi B ::= a ∈ P’.

Fie w∈L(G). Dacă |w| = 1, rezultă S ::= w ∈ P, deci (regula 2) S’::=w ∈ P’. Prin urmare w ∈ L(G’). Dacă w = a1a2…an, n > 1, atunci există derivarea: S → A1an → A2an-1an → A3an-2an-1an … → An-1 a2a3… an-2an-1an → a1a2…an. Producţiile folosite au fost: S ::= A1an; A1 ::= A2an-1; …, An-2 ::= An-1a2 şi An-1 ::= a1. Deci, în P’, se vor utiliza regulile A1 ::= an; A2 ::= an-1A1; …, An-1 ::= a2An-2 şi S’ ::= a1An-1. Rezultă că w ∈ L(G’). Incluziunea inversă se demonstrează similar. Observaţia 2.3

Propoziţiile anterioare arată echivalenţa dintre gramaticile liniare la stânga şi cele liniare la dreapta. Nu trebuie crezut că dacă o gramatică are pe lângă reguli de tipul A ::= a, atât reguli de forma A ::= aB, cât şi reguli de forma C ::= Db, ea va fi echivalentă cu o gramatică liniară la stânga (sau la dreapta). De exemplu, gramatica

cu regulile S ::= aA | aB; A ::= Sb; B ::= b generează2 un limbaj de tip 2 şi nu unul de tip 3 aşa cum ar părea la prima vedere. Exemplul 2.5

Următoarele limbaje sunt de tip 3: L1 = an | n≥1, L2 = Σ+, unde Σ este un alfabet finit (a se face legătura şi cu elementele lexicale ale limbajelor de programare), L3 = a(ba)n | n ≥0. L1 este generat de gramatica G1 având regulile: P=S ::= aS | a. Fie Σ = a1, a2, …, an, L2 este generat de o gramatică cu regulile: P = S ::= aiS | i = 1, 2, …, n ∪ S ::= ai | i = 1, 2, …, n. Limbajul L3 este generat de gramatica cu regulile P = S := aA | a, A ::= bB, B ::= aA | a. Exemplul 2.6

Fie gramatica G = (E, T, F, (, ), +, *, a, E, P) unde E este simbolul de start, iar P are următoarele elemente: E ::= E+T | T; T ::= T*F | F, F ::= (E) | a. Arborii de derivare pentru şirurile a+(a*a) şi (a+a)*a sunt3: E E / | \ | E + T T | | / | \ T F T * F | / | \ | | F ( E ) F a | | / | \ a T ( E ) / | \ /|\ T * F E + T | | | | F a T F | | | a F a | a Cerinta 2.6

Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Oricare ar fi A ∈ Ω, α ∈ (Ω ∪ Σ)*, A α dacă şi numai dacă există un A-arbore cu frontiera α. →*

Demonstraţie. Fie n numărul nodurilor interioare al unui A-arbore cu frontiera α. Dacă n = 1 atunci, arborele are forma:

A

X1 X2 … Xk

2 Se demonstrează uşor că limbajul generat de gramatica de la observaţia 2.3 este L = anbn | n ≥ 1. 3 În arbori, au fost trecute direct etichetele vârfurilor şi nu elementele din mulţimea X.

Prin urmare, în G există producţia A ::= X1X2…Xk, Deci A → X1X2…Xk. Să presupunem că proprietatea are loc pentru arbori cu cel mult n - 1 noduri interioare şi fie un A-arbore cu n noduri interioare şi frontiera α (n > 1). Descendenţii lui A nu pot fi toţi frunze. Fie X1, X2, …, Xk etichetele acestor descendenţi şi αi frontiera Xi – arborelui dacă Xi ∈ Ω şi α = Xi

→* i dacă Xi ∈ Σ. Deoarece orice Xi-arbore are cel mult n-1 noduri, atunci Xi α (evident şi pentru Xi

→* i ∈ Σ). Prin urmare, în G există derivarea A → X1X2…Xk α1X2…Xk α→* →

→

→*

→*

→*

1α2X3 … Xk * α1α2 …αk-1Xk * α1α2 …αk = α.

Reciproc, presupunem că derivarea A α are lungimea n (în gramatica G) şi procedăm prin inducţie după n. Pentru n = 1, rezultă că A → α, iar dacă α = X

→*

1X2…Xk atunci se pune în evidenţă A-arborele: A

X1 X2 Xk …

Presupunem că afirmaţia este valabilă pentru derivări de lungime cel mult n - 1 care încep de la un neterminal din G şi fie derivarea, în n paşi, A α. Fie A ::= X1X2…Xk prima producţie din derivare. Deci A → X1X2…Xk α. Atunci (conform propoziţiei 2.1) α = α1α2 …αk şi Xi α→*

i (în cel mult n-1 paşi). Dacă Xi ≠ αi, atunci există un Xi – arbore cu frontiera αi. Dacă Xi = αi atunci Xi – arborele este format doar din nodul etichetat cu Xi. A

X1 X2 Xk-1 Xk

α1 α2 αk-1 αk

Astfel, A-arborele de frontieră α se obţine prin aşezarea Xi-arborilor în ordinea X1, X2, …, Xk şi adăugarea unui nou nod cu eticheta A şi descendenţii X1, X2, …, Xk. Observaţia 2.4

Fie G = (Ω, Σ, S, P) o gramatică independentă de context. Atunci α ∈ L(G), adică S α, dacă şi numai dacă există un arbore de derivare (S-arbore) cu frontiera α.

Observaţia 2.5 Fie G = (Ω, Σ, S, P) o gramatică independentă de context şi w∈ L(G), deci

există un arbore de derivare cu frontiera w. a) Evident, se poate pune în evidenţă o derivare extrem stânga (resp.

dreapta) pentru w din S. Totuşi, pentru un anumit cuvânt pot exista mai multe derivări extrem stânga (resp. dreapta), ceea ce denotă o ambiguitate în procesul de generare.

b) Pentru orice cuvânt w∈ L(G), numărul de derivări extrem stânga pentru w este egal cu numărul de derivări extrem dreapta.

Exemplul 2.7 Fie G = (S, a, b, S, S ::= SbS | a) şi cuvântul w = (ab)3a. Se observă că:

S → SbS → SbSbS → abSbS → abSbSbS → ababSbS → abababS → abababa şi S → SbS → SbSbS → SbSbSbS → abSbSbS → ababSbS → abababS → abababa. Dacă numerotăm regulile de rescriere:

1. S ::= SbS, 2. S ::= a

atunci derivările cuvântului (ab)3a sunt obţinute prin aplicarea secvenţelor de reguli: 1,1,2,1,2,2,2 (resp. 1,1,1,2,2,2,2). Totuşi limbajul (ab)na | n ≥ 1 nu este ambiguu deoarece este generat şi de gramatica liniară la dreapta G1 = (S, X, Y, a, b, S, S ::= Xa, X := aY, Y ::= bX | b) care nu este ambiguă. Observaţia 2.6

Orice gramatică independentă de context care conţine, printre regulile sale de rescriere, producţii de unul din tipurile (1)-(4), cu neterminalul A util in generarea de cuvinte peste Σ, este ambiguă:

(1) A ::= AA; (2) A ::= AγA; (3) A ::= αA | Aβ; (4) A ::= αA | αAβA.

Cerinta 2.7

Fie G = (Ω, Σ, S, P) o gramatică independentă de context, iar A ∈ Ω cu proprietatea că există o producţie de forma A ::= Aα. Atunci există o gramatică G’ echivalentă cu G care pentru orice A-regulă A ::= β avem A ∉ Pref(β). Demonstraţie. Fie A ::= Aαi, i = 1, 2, …, n, toate A-regulile de rescriere ale gramaticii G care au neterminalul A ca primă literă a membrului drept, iar A ::= βi , i = 1, 2, …, m, celelalte A-reguli. Considerăm gramatica G’ = (Ω ∪ B, Σ, S, P’) unde B ∉ (Ω ∪ Σ) este un simbol nou, iar P’ se obţine din P astfel:

P’=(P-A :: Aαi; 1≤i≤n) ∪ A ::= βiB; 1≤i≤m ) ∪B ::= αiB | αi; 1 ≤ i ≤ n. Observăm că noua gramatică nu mai este recursivă la stânga în A, dar este recursivă la dreapta în B. Echivalenţa celor două gramatici rezultă imediat. Exemplul 2.8 [Generarea factorialului]

Următoarea gramatică, G = (Ω, Σ, S, P), prezentată în Păun(1974), generează factorialul numerelor naturale: Ω = S, A, A_, A0, A+, X, Y, Z, Σ = #, a, P = (S, A) ; (S, aa); (S, A_S); (S, A0A0); (#A_, #A+); (A+A_, A_ZA+); (A+A0, A0ZA+); (A+#, ZX#); (A+X, XZA+); (A+Z, ZA+); (ZA_, A_Z); (X#, Y#), (A0Y, YA0), (ZY, A0Y); (XY, YA_); (#Y, #A0); (A0A_, A_A0); (#Y, #a); (aA0, aa)

Atunci Var(G) = 7 şi Prod(G) = 19. Măsura Simb(G) nu poate fi evaluată deoarece G nu este o gramatică independentă de context. Exemplul 2.9

Fie gramatica independentă de context G = (Ω, Σ, S, P), unde Ω = S, A, B, Σ = a, b şi P = (S, aB); (S, bA); (A, a); (A, aS); (A, bAA); (B, b); (B, bS); (B, aBB). Atunci Var(G) = 3, Prod(G) = 8 şi Simb(G) = 32. Fie derivarea D1: S → aB → abS → abbA → abba. Atunci Index(D1, G) = 1. Derivarea D2: S → bA → bbAA → bbaSA → bbaaBA → bbaaaBBA → … → bbaaabba, are indexul Index(D2, G) = 3.

3. Mecanisme pentru recunoaşterea automată a mulţimilor regulate

Exemplul 3.1

Fie Q = q0, q1, q2, q3, Σ = 0, 1, F = q0. Pentru automatul M = (Q, Σ, δ, q0, F), dat prin diagrama:

1

1

1

1

000 0

q0 q1

q2 q3

funcţia δ, definită tabelar, este:

δ 0 1 q0 q2 q1 q1 q3 q0 q2 q0 q3 q3 q1 q2

Cerinta 3.1

Cu notaţiile de mai sus, δ(q, uv) = δ(δ(q,u), v), pentru oricare u, v ∈ Σ*. Demonstraţie. Se utilizează un raţionament inductiv după lungimea cuvântului v. Dacă |v| = 0 atunci δ(q, uv) = δ(δ(q, u), λ) = δ(q, u). Presupunem afirmaţia adevărată pentru cuvinte v de lungime cel mult n. Fie v de lungime n + 1, v = wa, unde a ∈ Σ şi w ∈ Σ*. Obţinem succesiv: δ(q, uv) = δ(q, uwa) = δ(δ(q, uw), a) = δ(δ(δ(q, u), w), a) = δ(δ(q, u), wa) = δ(δ(q, u), v). Exemplul 3.2

Fie automatul din exemplul 3.1. Atunci: a) δ(q0, 10101100) = δ(δ(q0, 1), 0101100) = δ(δ(q1, 0), 101100) =

δ(δ(q3, 1), 01100) = δ(δ(q2, 0), 1100) = δ(δ(q0, 1), 100)= δ(δ(q1, 1),00) = δ(δ(q0, 0),0) = δ(δ(q2, 0), λ)= δ(q2, 0) = q0 ∈ F.

b) δ(q0, 11101001) = δ(δ(q0, 1), 1101001) = δ(δ(q1, 1), 101001) = δ(δ(q0, 1), 01001) = δ(δ(q1, 0), 1001) = δ(δ(q3, 1), 001)= δ(δ(q2, 0), 01)= δ(δ(q0, 0), 1) = δ(δ(q2, 1), λ) = δ(q2,1) = q3 ∉ F.

Exemplul 3.3

Limbajul acceptat de automatul prezentat în exemplul 3.1 este constituit din mulţimea şirurilor peste 0, 1 în care apar un număr par de ‘0’ şi un număr par de ‘1’. Exemplul 3.4

Fie N = (Q, Σ, δN, q0, F) cu Q = A, B, C, Σ = a, b, q0 = A, F = B, C şi δN dată prin tabelul:

δN a b A A, B B B A, C C C B, C A

şi w = abababb. Atunci, obţinem succesiv:

δN(A, abababb) = δN(A, bababb) ∪ δN(B, bababb); δN(A, bababb) = δN(B, ababb) = δN(A, babb) ∪ δN(C, babb); δN(B, bababb) = δN(C, ababb) = δN(B, babb) ∪ δN(C, babb); δN(A, babb) = δN(B, abb) = δN(A, bb) ∪ δN(C, bb); δN(B, babb) = δN(C, abb) = δN(B, bb) ∪ δN(C, bb); δN(C, babb) = δN(A, abb) = δN(A, bb) ∪ δN(B, bb); δN(A, bb) = δN(B, b) = C; δN(B, bb) = δN(C, b) = A; δN(C, bb) = δN(A, b) = B; δN(A,abababb) = A, B, C.

Observăm că F ∩ δN(A, abababb) ≠ ∅. Deci abababb ∈ L(N). Cerinta 3.2.

Orice limbaj acceptat de un AFD este acceptat de un AFN. Demonstraţie. Evident. Cerinţa 3.3.

Fie L un limbaj acceptat de un AFN. Atunci există un AFD, notat cu M, astfel încât L(M) = L. Demonstraţie. Fie N = (Q, Σ, δ, q0, F) un AFN astfel încât L(N) = L. Definim un AFD, notat cu M = (QM, Σ, δM, q0’, F’) unde:

QM = P(Q); q0’ = qo; F’ = P | P ⊆ Q, P ∩ F ≠ ∅, iar

δM(∅, a) = ∅; δM(P, a)= ; oricare P ⊆ Q, P ≠ ∅. U

Pq

q∈

(δ a),

Este suficient să demonstrăm că δM(s, w) = δ(s, w), oricare s ∈ Q şi oricare w ∈ Σ*. Dezvoltăm un raţionament inductiv. Pentru |w| = 0, afirmaţia este evidentă. Presupunem că afirmaţia este adevărată pentru orice cuvânt de lungime k. Fie w ∈ Σ* astfel încât |w| = k + 1, w = αa, |α| = k, a ∈ Σ. Prin urmare: δM(s, w) = δM(s, αa) = δM(δM(s, α)), a)= = = δ(s, αa).

În concluzie, w ∈ L(M) ⇔ δ(q

),(),(

arMsr M

δαδ

U∈ r∈

),(),(

ars

δα

Uδ

0, w) ∩ F ≠ ∅ ⇔ δM(q0, w) ∩ F ≠ ∅ ⇔ δM(qo’, w) ∈ F’ ⇔ w ∈ L(M’). Exemplul 3.5

Fie automatul finit nedeterminist din exemplul 3.4. Automatul finit determinist asociat are este caracterizat prin tabelul:

QM P(Q) A b q7’ ∅ q7’ q7’ q0’ A q3’ q1’ q1’ B q4’ q2’ q2’ C q5’ q0’ q3’ A, B q6’ q5’ q4’ A, C q6’ q3’ q5’ B, C q6’ q4’ q6’ A, B, C q6’ q6’

deoarece:

δM(q0’, a) = δM(A, a) = δN(A, a) = A, B = q3’; δM(q0’, b) = δM(A, b) = δN(A, b) = B = q1’; δM(q1’, a) = δM(B, a) = δN(B, a) = A, C = q4’; δM(q1’, b) = δM(B, b) = δN(B, b) = C = q2’; δM(q2’, a) = δM(C, a) = δN(C, a) = B, C = q5’; δM(q2’, b) = δM(C, b) = δN(C, b) = A = q0’; δM(q3’, a) = δM(A, B, a) = δN(A, a) ∪ δN(B, a) = A, B, C = q6’; δM(q3’, b) = δM(A, B, b) = δN(A, b) ∪ δN(B, b) = B, C = q5’; δM(q4’, a) = δM(A, C, a) = δN(A, a) ∪ δN(C, a) = A, B, C = q6’; δM(q4’, b) = δM(A, C, b) = δN(A, b) ∪ δN(C, b) = A, B = q3’; δM(q5’, a) = δM(B, C, a) = δN(B, a) ∪ δN(C, a) = A, B, C = q6’; δM(q5’, b) = δM(B, C, b) = δN(B, b) ∪ δN(C, b) = A, C = q4’; δM(q6’, a) = δM(A, B, C,a) = δN(A,a) ∪ δN(B,a) ∪ δN(C,a)=A, B, C = q6’; δM(q6’, b) = δM(A, B, C,b) =δN(A,b) ∪ δN(B,b) ∪ δN(C,b)=A, B, C = q6’,

iar F’ = q1’, q2’, q3’, q4’, q5’, q6’. Observăm că q7’ este stare inutilă şi se poate elimina din QM.

4. Optimizarea automatelor finite

Algoritmul 4.1 [Determinarea stărilor accesibile4]

Prin aplicarea strategiei greedy, putem obţine un şir ascendent de mulţimi cu stări accesibile, majorat în sensul relaţiei de incluziune de mulţimea stărilor automatului considerat.

Fie S0 = q0. Pentru i ≥ 0, formăm Si+1 = Si ∪ q ∈ Q - Si| există s ∈ Si şi a ∈ Σ astfel încât δ(s, a) = q. O altă modalitate de construire a şirului ascendent utilizează relaţia de recurenţă: Si+1 = Si ∪ δ(s, a) | s ∈ Si, a ∈ Σ.

Este clar că trebuie să existe k0, k0 ≤ |Q| astfel încât Sk0 = Sk0+1, k0 fiind cel mai mic număr natural cu această proprietate; în aceste condiţii Sk0+j = Sk0, oricare j ≥ 1. Mulţimea stărilor accesibile este Sk0.

Intrare: Q, Σ, q0, δ, F Ieşire: Q’ – mulţimea stărilor accesibile SEQ

1. i := 0; S0 := q0; 2. do Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i+1; while(Si – Si-1 ≠ ∅); 3. Q’ = Si.

END. Algoritmul 4.2 [Determinarea stărilor utile5]

Prin aplicarea strategiei greedy, putem obţine un şir ascendent de mulţimi cu stări utile, majorat în sensul relaţiei de incluziune de mulţimea stărilor automatului considerat.

Fie U0 = F. Pentru i ≥ 0, formăm Ui+1 = Ui ∪ q ∈ Q - Ui| există a ∈ Σ astfel încât δ(q, a) ∈ Ui.

Este clar că trebuie să existe k0, k0 ≤ |Q| astfel încât Uk0 = Uk0+1, k0 fiind cel mai mic număr natural cu această proprietate; în aceste condiţii Uk0+j = Uk0, oricare j≥1. Mulţimea stărilor utile este Uk0.

Intrare: Q, Σ, q0, δ, F Ieşire: U’ – mulţimea stărilor utile

SEQ 1. i := 0; U0:= F; 2. do

for a ∈ Σ do for q ∈ Q - Ui do if δ(q, a) ∈ Ui then Ui+1 = Ui ∪ q; i = i +1; while(Ui – Ui-1 ≠ ∅);

3. U’ = Ui. END.

4 Problema determinării stărilor accesibile este echivalentă cu problema determinării vârfurilor unui digraf care sunt legate prin cel puţin un drum de vârful care corespunde stării q0. Dacă se determină matricea existenţei drumurilor sau, echivalent, închiderea tranzitivă a relaţiei binare asociată diagramei de tranziţie (de exemplu, folosind algoritmul Roy-Warshal) atunci stările accesibile corespund valorii 1 în linia stării q0 din matricea existenţei drumurilor. 5 În unele lucrări, stările utile sunt denumite stări observabile.

Cerinta 4.1 [Lema de pompare]

Fie L un limbaj regulat. Există atunci un număr natural n astfel încât pentru orice cuvânt w ∈ L, |w| ≥ n, w = xyz cu proprietăţile:

a) |xy| ≤ n; b) |y| ≥ 1; c) xyiz ∈ L pentru oricare i ≥ 0.

Demonstraţie. Se foloseşte automatul minimal care recunoaşte L. Rezultă că n este unic determinat şi depinde numai de L. Fie M = (Q, Σ, δ, q0, F) astfel încât L(M) = L şi M este automatul minimal. Considerăm n := |Q|. Fie w ∈ L, |w| ≥ n, w ∈ L, |w| ≥ n. Atunci w = a1a2 … am, m ≥ n. Fie qi = δ(q0, a1a2…ai), i = 1, 2, …, m. Deoarece w ∈ L rezultă că qm ∈ F. Cum sunt evidenţiate m + 1 stări, iar m ≥ n, rezultă că, în şirul q0, q1, …, qm, există două stări care se repetă. Fie qs şi qt stările care se repetă (evident 0 ≤ s < t ≤ m; se poate lua chiar s minim cu aceste proprietăţi). Se descompune w astfel: x = a1a2…as, y = as+1as+2…at, z = at+1at+2…am. Se observă că această descompunere satisface cerinţele formulate. Exemplul 4.1 [ ]

2ka2ka

na

Fie L = | k ≥ 1. Vom arăta că L nu este limbaj regulat. Presupunem contrariul. Fie n numărul natural dat de lema de pompare aplicată pentru presupusul limbaj regulat L şi w ∈ L astfel încât w = , adică |w| = n

2 2 > n pentru n > 1. Atunci w = xyz cu a) |xy| ≤ n; b) |y| ≥ 1; c) xyiz ∈ L pentru oricare i ≥ 0. Fie i = 2. Obţinem |xy2z| = |xyz| + |y| = n2 + |y|. Dar n2 < |xy2z| ≤ n2 + n < (n+1)2. Deci xy2z ∉ L, contrar celor presupuse. În concluzie L nu este limbaj regulat. Exemplul 4.2 [akbk]

Fie L = akbk | k ≥ 1. Presupunem că L este limbaj regulat şi fie n numărul dat de Teorema 4.3. Fie w = anbn = xyz. Cum |y| > 0, apar trei situaţii:

1. y = as, 0 < s ≤ n. Pentru i = 0 se va obţine un cuvânt cu mai puţine simboluri a decât b, deci xy0z ∉ L;

2. y = bt, 0 < t ≤ n. Analog, pentru i=0, rezultă xy0z ∉ L; 3. y = asbt, 0 < s, t ≤ n. Pentru i = 2 se amestecă literele şi se obţine

xy2z = an-sasbtasbtbn-t = anbtasbn ∉ L. Deci L nu este limbaj regulat. Cerinta 4.2

Fie L un limbaj acceptat de un AFD cu n stări. Atunci L ≠ ∅ ⇔ există w ∈ L astfel încât |w| < n; Demonstraţie. Presupunem că L este nevid. Fie w ∈ L. Notăm w0 := w.

Dacă |w0| < n atunci stop, altfel aplicăm Teorema 4.3 şi rezultă descompunerea w0 = xyz cu proprietăţile: a) |xy| ≤ n; b) |y| ≥ 1; c) xyiz ∈ L pentru oricare i ≥ 0. Pentru i = 0, formăm w1 = xz ∈ L, deoarece L este acceptat de un AFD, deci este limbaj regulat.

Continuăm cu obţinerea secvenţei, descrescătoare în lungime, w0, w1, …, wt. Ne oprim când |wt| < n.

Implicaţia inversă (⇐) este evidentă.

Cerinta 4.3

Fie L un limbaj acceptat de un AFD cu n stări. Atunci L este infinit ⇔ există w ∈ L, n ≤ |w| < 2n. Demonstraţie. Fie L limbajul generat de un AFD cu n stări. Dacă limbajul este infinit atunci, sigur există un cuvânt w ∈ L astfel încât |w| > n.

Fie w0 := w. Conform lemei de pompare rezultă că w0 = xyz cu proprietăţile: a) |xy| ≤ n; b) |y| ≥ 1; c) xyiz∈L pentru oricare i ≥ 0.

Dacă |w0| < 2n atunci stop, altfel considerăm w1 = xz ∈ L, pentru care |w1| < |w0|.

Dacă |w1| < 2n atunci stop, altfel reluăm procesul şi vom obţine o sevenţă, descrescătoare în lungime, w0, w1, …, wt. Ne oprim când |wt| < n.

Reciproc, dacă în L există un cuvânt w astfel încât n ≤ |w| < 2n, atunci prin aplicarea lemei de pompare şi considerarea cuvintelor xyiz, i ≥ 0, obţinem o mulţime infinită de cuvinte ale limbajului, deci L este infinit. Algoritmul 4.3

Fie L un limbaj acceptat de un AFD cu n stări. Pentru a verifica dacă L ≠ ∅, se poate aplica următorul algoritm.

Intrare: Q, Σ, q0, δ, F Ieşire: “DA” dacă L este nevid; “NU” în caz contrar.

SEQ

1. i := 0; S0:= q0; 2. do Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i + 1; while(Si – Si-1 ≠ ∅); 3. if Si ∩ F = ∅ then write “NU”; else write “DA”.

END. Se observă că mulţimea Si, de la pasul 3, conţine stările accesibile. Este clar că dacă nici o stare finală nu este accesibilă atunci limbajul L este vid. Algoritmul 4.4

Fie L un limbaj acceptat de un AFD cu n stări. Pentru a verifica dacă L ≠ ∅, se poate aplica următorul algoritm.

Intrare: Q, Σ, q0, δ, F Ieşire: “DA” dacă L este infinit; “NU” în caz contrar.

SEQ

1. i := 0; S0:= q0; 2. do Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i + 1; while(i < n); 3. do

if Si ∩ F ≠ ∅ then write “DA”; stop. Si+1 := Si ∪δ(s, a) | s ∈ Si, a ∈ Σ; i = i + 1; while(i < 2n);

4. write “NU”. END.

5. Transformări asupra gramaticilor formale

Cerinta 5.1 [Eliminarea redenumirilor]

Fie G = (Ω, Σ, S, P) o gramatică de tipul 2 sau 3. Există o gramatică G1 = (Ω, Σ, S, P1) de acelaşi tip cu G, echivalentă cu G şi fără redenumiri. Demonstraţie. Fie G = (Ω, Σ, S, P) o gramatică de tipul 2 sau 3 şi P’ := A ::= w | w ∉ Ω, A ::= w ∈ P mulţimea regulilor din P care nu sunt redenumiri. Fie P” := A ::= w | A ∈Ω, există B, B ∈ Ω şi A B (în G, derivare în cel puţin un pas), iar B → w ∈ P’ o mulţime de reguli care nu sunt redenumiri. Formăm gramatica G

→+

1 = (Ω, Σ, S, P1) cu P1 := P’ ∪ P”. Evident G1 este fără redenumiri şi de acelaşi tip cu G. Demonstrăm că G şi G1 sunt echivalente.

Fie w ∈ L(G), deci S w, printr-o derivare stângă (conform lemei 5.1), în G, de forma: S = w

→*

→*0 w1 w→*

2 … w→* →*

→*

→*

→*

→*

→*

→*

k = w, derivările wi wi+1, i = 0, 1, 2, …, k - 1 fiind de lungime nenulă, iar pentru fiecare din ele este posibilă numai una din situaţiile:

a) wi wi+1 este o derivare de lungime 1 obţinută prin aplicarea unei reguli din P’. Deci wi w→*

i+1, în gramatica G1. b) wi wi+1 este o derivare de lungime cel puţin egală cu 2, astfel încât

există v ∈ (Ω∪Σ)*, pentru care wi v (derivare stângă cu

redenumiri) şi v → w→*

i+1, derivare printr-o regulă din P’. Prin aplicarea

unei reguli din P” referitor la derivarea iniţială wi v se poate găsi w v în Gi

→* 1. Prin cuplarea derivărilor rezultă că este posibil ca S w în G1.

Reciproca este imediată. Cerinţa 5.2 [Determinarea simbolurilor neterminale care “generează” cuvântul vid]

Fie G = (Ω, Σ, S, P) o gramatică cu producţiile de forma (p, q) ∈ Ωx(Ω∪Σ)*. Şirul de mulţimi generat prin:

U0 = ∅; Um+1 = Um ∪ X | X ∈ Ω, există w, w ∈ Um*, X ::= w ∈ P

are următoarele proprietăţi:

a) U0 ⊆ U1 ⊆ … Um ⊆ … ⊆ Ω şi există k, număr natural, astfe încât Uk = Uk+1.

b) Dacă Uk = Uk+1, atunci Uk = Uk+i, pentru oricare i > 0. c) Fie k* cel mai mic număr natural pentru care Uk* = Uk* +1. Atunci

Uk* = X | X ∈ Ω şi X λ. →*

Demonstraţie. Proprietatea a) rezultă din construcţia şirului de mulţimi, iar proprietatea b) se poate demonstra uşor prin inducţie.

Vom demonstra proprietatea c). Mai general, vom arăta că Um ⊆ X | X ∈ Ω şi X λ, pentru oricare m număr natural. →*

Dacă m = 0, este evident. Presupunem că Um ⊆ X | X ∈ Ω şi X λ şi fie X ∈ Um+1. Dacă X ∉ Um rezultă că există w, w∈Um*, X ::= w ∈ P. Sunt posibile două cazuri:

Cazul 1: w = λ. Deci X λ. →*

Cazul 2. w ≠ λ. Atunci w = x1x2…xr, unde xi ∈ Um, i = 1, 2, …, r. Din ipoteza de inducţie rezultă că xi λ, i = 1, 2, …, r. Deci X λ. →* →

→**

→*

→*

→*

→*

→*

În ambele cazuri a rezultat că X ∈X | X ∈ Ω şi X λ. În concluzie Uk* ⊆ X | X ∈ Ω şi X λ . →*

Reciproc, presupunem că Uk* ≠ ∅ şi arătăm că X | X ∈ Ω şi X λ ⊆

Uk*, prin inducţie completă în raport cu lungimea derivării X λ. Dacă derivarea X λ este de lungime 1 atunci X ::= λ este producţie

din P, deci X ∈ U→*

1 ⊆ Uk*. Presupunem că pentru orice derivare X λ cu lungimea cel mult m

rezultă X ∈ U→*

k*. Fie X λ o derivare de lungime m+1. Punem în evidenţă primul pas al derivării. Rezultă că există v astfel încât X ::= v şi X → v λ, unde derivarea v λ are lungimea m. Evident pentru m ≠ 0 trebuie ca v ≠ λ. Prin urmare v = v

→*

→*

→*

1v2…vr este o scriere a lui v cu elemente vi ∈ Ω, i = 1, 2, …, r.

Dacă ar exista un i pentru care vi ∈ Σ, acesta nu ar mai putea fi eliminat pe parcursul derivării v λ. Conform propoziţiei 2.1 rezultă că vi λ, i = 1, 2, …, r. Prin aplicarea ipotezei de inducţie rezultă că vi ∈ Uk* şi deci v ∈ Uk*. Astfel obţinem X ∈ Uk*. Cerinţa 5.3 [Limbaje independente de context generate de gramatici cu λ - producţii]

Fie G = (Ω, Σ, S, P) o gramatică cu producţiile de forma (p, q) ∈ Ωx(Ω∪Σ)*. Atunci L(G) este un limbaj independent de context. Demonstraţie. Fie P1 = Y ::= w1 | există w ∈ (Ω∪Σ)+, cu Y ::= w astfel încât w1 se obţine din w prin ştergerea a zero, unu sau mai multor simboluri X ∈ Ω pentru care X λ şi G1 = (Ω, Σ, S, P1).

Evident, gramatica G1 este independentă de context, iar L(G1) = L(G) – λ. Ceinţa 5.4 [Simboluri care generează cuvinte peste Σ6]

Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Există o gramatică G1 = (Ω1, Σ, S, P1) independentă de context, echivalentă cu G, astfel încât pentru oricare X ∈ Ω1, mulţimea w ∈ Σ* | X w este nevidă. →*

Demonstraţie. Construim şirul de mulţimi U0, U1, U2, … folosind următorul algoritm:

1. U0 := ∅; i := 1; 2. Ui := Ui-1 ∪ X | X ::= w ∈ P, w ∈ (Ui ∪ Σ)* 3. Dacă Ui ≠ Ui-1 atunci i := i + 1 şi se continuă cu pasul 2. 4. Se consideră Ω1 = Ui, P1 se obţine din P prin eliminarea producţiilor

în care apare cel puţin un simbol neterminal din Ω - Ω1. Să observăm că U0 ⊆ U1 ⊆ … ⊆ Um ⊆ … ⊆ Ω (numărul maxim de aplicări

al pasului 2 este maximum card (Ω)), deci există k astfel încât Uk = Uk+1 şi Uk = Uk+p pentru oricare p > 0. Indicele i furnizat de algoritm corespunde celui mai mic

6 Acestea se mai numesc şi simboluri productive. Prin analogie cu sistemele AFD, simbolurile productive vor fi numite şi simboluri utile. Simbolurile care sunt în acelaşi timp accesibile (definiţia 5.3) şi productive le vom numi simboluri utilizabile, precum în Atanasiu (1987).

k pentru care Uk = Uk+1. Notăm această valoare prin k*. Deci se poate scrie că U0 ⊆ U1 ⊆ … ⊆ Uk*.

De asemenea, pentru oricare i = 1, 2, …, k*, dacă X ∈ Ui atunci există w ∈ Σ* astfel încât X w. Dacă i = 1, afirmaţia rezultă din construcţia mulţimii U

→*

→*

→n

→n → in

1. Presupunem proprietatea adevărată pentru un indice i şi considerăm X ∈ Ui+1.

Dacă X ∈ Ui demonstraţia este încheiată. Considerăm cazul X ∈ Ui+1 – Ui, deci există producţia X ::= X1X2…Xr, cu Xi ∈ Ui ∪ Σ, i = 1, 2, …, r. Dacă Xi ∈ Σ, considerăm wi = Xi; altfel, prin ipoteza de inducţie există wi astfel încât Xi wi. Formăm derivarea X → X1X2…Xr w→*

1w2 …wr şi luăm w = w1w2…wr. Pentru a completa demonstraţia propoziţiei este suficient să arătăm că dacă

X w (derivare în n paşi) şi w ∈ Σ* atunci există i astfel încât X ∈ Ui. Vom proceda prin inducţie după n (lungimea derivării).

Pentru n = 1, din construcţie va rezulta că X ∈ U1. Să presupunem afirmaţia adevărată pentru derivări de lungime cel mult n şi să considerăm o derivare de lungime n + 1. Punem în evidenţă primul pas al derivării, adică X → X1X2…Xr

w. Conform propoziţiei 2.1 rezultă că w = w1w2…wr cu Xp wp (p = 1, 2, …, r). Dacă Xp ∈ Σ (np = 0) atunci luăm j[p] = 0, adică Xp∈ U0. Dacă Xp ∈ Ω atunci, prin utilizarea ipotezei de inducţie rezultă că există j[p] astfel încât Xp ∈ Uj[p]; Cum şirul construit este ascendent, putem lua i = 1+ maxj[1], j[2], …, j[r] şi rezultă X ∈ Ui.

Pe baza afirmaţiilor de mai sus se deduce echivalenţa gramaticilor G şi G1. Cerinţa 5.5 [Decidabilitatea problemei L(G) ≠ ∅]

Există un algoritm care pentru o gramatică independentă de context stabileşte dacă L(G) = ∅ sau L(G) ≠ ∅. Demonstraţie. Se poate utiliza următorul algoritm:

1. U0 := ∅; i := 1; 2. Ui := Ui-1 ∪ X | X ::= w ∈ P, w ∈ (Ui ∪ Σ)* 3. Dacă Ui ≠ Ui-1 atunci i := i + 1 şi se continuă cu pasul 2. 4. Dacă S ∈ Ui atunci L(G) ≠ ∅ altfel L(G) = ∅.

Justificarea corectitudinii algoritmului urmează paşii prezentaţi în cadrul demonstraţiei propoziţiei 5.5. Cerinţa 5.6 [Determinarea simbolurilor accesibile]

Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Există G1 = (Ω1, Σ1, S, P1) echivalentă cu G care nu are simboluri inaccesibile. Demonstraţie. Vom demonstra că algoritmul de mai jos va determina simbolurile accesibile. Paşii algoritmului sunt:

1. U0 := S; i := 1; 2. Ui := Ui-1 ∪ X | există A ::= uXv ∈ P, astfel încât A ∈ Ui-1. 3. Dacă Ui ≠ Ui-1 atunci i:= i+1 şi se continuă de la pasul 2. 4. Fie k* valoarea lui i obţinută la acest pas. Formăm Ω1 := Ω ∩ Uk*, Σ1 :=

Σ ∩ Uk* şi P1 producţiile lui P care au în ambii membrii numai simboluri din Uk*.

Cum Uk* ⊆ Ω ∪ Σ, are cardinal finit, rezultă că procesul descris se termină în timp finit. Se arată uşor că G şi G1 sunt echivalente şi că pentru oricare A∈ Ω1 ∪ Σ1 există u şi v din (Ω1∪Σ1)* astfel încât S uAv. →*

Cerinţa 5.7 Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅.

Atunci G este echivalentă cu o gramatică G1 fără simboluri neutilizabile. Demonstraţie. Asupra gramaticii G se aplică propoziţia 5.5 şi se determină G1 echivalentă cu G care are numai simboluri neterminale care pot “genera” cuvinte peste alfabetul terminal (aşa numitele simboluri productive sau utile). Apoi, asupra gramaticii G1 se aplică propoziţia 5.6 pentru a obţine G2 ce are numai simboluri accesibile din simbolul de start. Dacă, gramatica nu are redenumiri şi nici λ-producţii, atunci s-a obţinut o gramatică proprie (definiţia 5.4, teorema 5.1). Cerinţa 5.8

Fie G = (Ω, Σ, S, P) o gramatică independentă de context cu L(G) ≠ ∅. Există G1 = (Ω1, Σ1, S, P1) echivalentă cu G care este gramatică proprie. Exemplul 5.1

Simbolurile neutilizabile ale gramaticii cu mulţimea de reguli (S, A), (S, B), (A, aB), (A, bS), (A, b), (B, AB), (B, Ba), (C, AS), (C, b) sunt B, a şi C. Exemplul 5.2

După eliminarea λ-producţiilor, gramatica cu regulile (S, aSbS), (S, bSaS), (S, λ) devine echivalentă cu gramatica cu regulile (S’, S), (S’, λ), (S, aSbS), (S, aSb), (S, abS), (S, ab), (S, bSaS), (S, baS), (S, bSa), (S, ba). Exemplul 5.3

Fie gramatica G cu mulţimea de reguli P = (S, A), (A, bS), (A, b). Gramatica proprie echivalentă cu G are mulţimea regulilor P’ = (S, bS), (S, b), iar A este un simbol neutilizabil.

6. Forme normale. Lema Bar-Hillel Observaţia 6.1

Este suficient să se lucreze cu mecanisme generative echivalente cu gramaticile proprii (obţinute după transformările necesare). Cerinta 6.1

Fie G = (Ω, Σ, S, P) o gramatică proprie. Atunci există G1 gramatică în forma normală Chomsky echivalentă cu G. Demonstraţie. Prin aplicarea propoziţiei 2.2 putem considera că mulţimea P conţine numai reguli de forma A ::= X1X2…Xm (m > 1) şi A ::= a, cu A, X1, …, Xm ∈ Ω, a ∈ Σ. Regulile pentru care m = 2 rămân nemodificate în P1. Dacă m > 2, considerăm m - 2 neterminale noi şi pentru regula curentă adaugăm în P1 cele m - 1 reguli: A ::= X1D1, D1 ::= X2D3, …, Dm-3 ::= Xm-2Dm-2, Dm-2 ::= Xm-1Xm.

Este uşor de demonstrat că după prelucrarea tuturor regulilor din P, gramatica obţinută este în forma normală Chomsky şi este echivalentă cu G. Exemplul 6.1

Fie gramatica cu regulile S ::= bA | aB; A ::= bAA | aS | a; B ::= aBB | bS | b. Introducem neterminalele noi Xa şi Xb. Formăm regulile Xa ::= a şi Xb ::= b. Apoi

modificăm regulile gramaticii iniţiale cu excepţia regulilor A ::= a şi B ::= b. Obţinem noua mulţime de reguli:

S ::= XbA | XaB; A ::= XbAA | XaS | a; B ::= XaBB | XbS | b; Xa ::= a; Xb ::= b.

Introducem noi simboluri neterminale şi modificăm regulile care au în membrul drept cel puţin trei simboluri. Fie Y1 şi Y2 simboluri neterminale noi. Gramatica în forma normală Chomsky, echivalentă cu gramatica iniţială, are regulile:

S :;= XbA | XaB; A ::= XbY1 | XaS | a; B ::= XaY2 | XbS | b; Y1 ::= AA; Y2 ::= BB; Xa::= a; Xb ::= b.

Cerinta 6.2

Fie G = (Ω, Σ, S, P) o gramatică de tip 2 în forma normală Chomsky. Dacă derivarea A → w1 → … → wn, n ≥ 1, wn ∈ Σ*, are proprietatea că cel mai lung lanţ de la rădăcină la vârfurile terminale în arborele de derivare asociat ei în gramatica GA = (Ω, Σ, A, P) are k noduri, atunci |wn| ≤ 2k-1. Demonstraţie. Aplicăm metoda inducţiei în raport cu k. Cum n ≥ 1 rezultă k ≥ 2. Pentru k = 2 rezultă n = 1 şi w1 ∈ Σ, deoarece G este în forma normală Chomsky, deci |w1| ≤ 2k-1. Presupunem afirmaţia adevărată pentru orice întreg m, 2 ≤ m ≤ k, unde k este un întreg fixat, k ≥ 2. Considerăm o derivare A → w1 → … → wn, n≥1, wn ∈ Σ*, care are proprietatea că cel mai lung lanţ de la rădăcină la vârfurile terminale în arborele de derivare asociat ei are k + 1 noduri. Primul pas al derivării constă în aplicarea unei reguli de forma A ::= XY cu X şi Y neterminale (gramatica este în forma normală Chomsky).

Prin aplicarea ipotezei de inducţie asupra arborilor de derivare cu rădăcinile X şi Y obţinem

|wn| ≤ 2k-1 + 2k-1 = 2k, deci

|wn| ≤ 2(k+1)-1. Cerinta 6.3

Fie gramatica proprie G = (Ω, Σ, S, P) şi A ::= α1Bα2 o A-producţie şi B ::= β1 | β2 | … βk toate B-producţiile din mulţimea P. Considerăm G1 = (Ω, Σ, S, P1) unde P1 = (P – A ::= α1Bα2) ∪ A ::= α1β1α2 | α1β2α2 |… | α1βkα2 . Atunci G şi G1 sunt gramatici echivalente. Demonstraţie. Se arată, prin dublă incluziune, că L(G) = L(G1).

Cerinta 6.4 Fie gramatica fără λ-producţii şi numai cu simboluri utilizabile, G = (Ω, Σ, S,

P) şi A ::= Aα1 | Aα2 … | Aαk toate A-producţiile recursive la stânga şi A ::= β1 | β2 | … βm restul A-producţiilor din mulţimea P. Fie X un simbol nou, X ∉ Ω ∪ Σ, Ω1 = Ω ∪ X şi gramatica G1 = (Ω1, Σ, S, P1), unde P1 se obţine din P prin înlocuirea tuturor A-producţiilor cu regulile: A ::= β1 | β2 | … βm, A ::= β1X | β2X | … βmX şi X ::= α1 | α2 … | αk, X ::= α1X | α2X … | αkX.

Atunci G şi G1 sunt echivalente. Demonstraţie. Se arată că L(G) = L(G1). Cerinta 6.5

Fie G = (Ω, Σ, S, P) o gramatică proprie. Atunci există gramatica G*, în forma normală Greibach, echivalentă cu G. Demonstraţie. Se aplică algoritmul: Intrare: Gramatica G1 în forma normală Chomsky, nerecursivă la stânga, fără λ-producţii, Ω1 = A1, A2, …., Am, S1 ≡ A1. Ieşire: Gramatica G* în forma normală Greibach.

SEQ 1. P* := P1; i := m; 2. while i > 1 do

SEQ i := i - 1; while (există j, i < j ≤ m, Ai ::= Ajα în P*) do

P* := (P* - Ai ::= Ajα) ∪ Ai ::= βα | Aj ::= β ∈ P* END

3. for indici i ai simbolurilor Y do while (există j, 1 ≤ j ≤ m, Yi ::= Ajα ∈ P*) do P* := (P* - Yi ::= Ajα ) ∪ Yi ::= βα | Aj ::= β ∈ P*

END. Exemplul 6.2

Fie gramatica G, cu simbolurile neterminale numerotate şi regulile: A1 ::= A2A3; A2 ::= A3A1 | b; A3 ::= A1A2 | a.

Se observă că gramatica G, deşi are reguli de tip FNC, este recursivă în mai mulţi paşi.

Considerăm regula A3 ::= A1A2 şi o înlocuim cu A3 ::= A2A3A2, prin aplicarea lemei 6.1. Observăm că în continuare persistă recursivitatea în mai mulţi paşi. Considerăm regula A3 ::= A2A3A2 şi o înlocuim, folosind lema 6.1, cu regulile A3 ::= A3A1A3A2 | bA3A2. Observăm că am ajuns la reursivitate într-un singur pas şi putem aplica lema 6.2. Eliminăm regula A3 ::= A3A1A3A2 şi introducem regulile A3 ::= bA3A2Y3 | aY3; Y3 ::= A1A3A2Y3 | A1A3A2. Am obţinut următoarea mulţime de reguli:

A1 ::= A2A3; A2 := A3A1 | b; A3 ::= bA3A2Y3 | aY3 | bA3A2 | a Y3 ::= A1A3A2Y3 | A1A3A2.

În continuare aplicăm algoritmul din demonstraţia teoremei 6.3. Eliminăm regula A2 ::= A3A1 şi adăugăm regulile: A2 ::= bA3A2Y3A1 | aY3A1 | bA3A2A1 | aA1. Observăm că A2 ::= b rămâne pe loc. Apoi regula A1 ::= A2A3 se elimină şi se introduc regulile: A1 ::= bA3A2Y3A1A3 | aY3A1A3 | bA3A2A1A3 | aA1A3 | bA3. Până acum am aplicat pasul 2 cu indicii i =2 şi 1.

Aplicăm, în continuare, pasul 3 pentru Y3. Astfel regulile Y3 ::= A1A3A2Y3 | A1A3A2

se înlocuiesc cu Y3 ::= bA3A2Y3A1A3A3A2Y3 | aY3A1A3A3A2Y3 | bA3A2A1A3A3A2Y3 |

aA1A3A3A2Y3 | bA3A3A2Y3 | bA3A2Y3A1A3A3A2 | aY3A1A3A3A2 | bA3A2A1A3A3A2 | aA1A3A3A2 | bA3A3A2.

Gramatica G*, în forma normală Greibach, echivalentă cu gramatica dată, are

regulile: A1 ::= bA3A2Y3A1A3 | aY3A1A3 | bA3A2A1A3 | aA1A3 | bA3; A2 ::= bA3A2Y3A1 | aY3A1 | bA3A2A1 | aA1 | b; A3 ::= bA3A2Y3 | aY3 | bA3A2 | a Y3 ::= bA3A2Y3A1A3A3A2Y3 | aY3A1A3A3A2Y3 | bA3A2A1A3A3A2Y3 | aA1A3A3A2Y3 | bA3A3A2Y3 | bA3A2Y3A1A3A3A2 | aY3A1A3A3A2 | bA3A2A1A3A3A2 | aA1A3A3A2 | bA3A3A2.

Trebuie observat că, în general, procesul de normalizare, conduce la creşterea

numărului neterminalelor dar şi a regulilor. Astfel cresc măsurile Var şi Prod. Cerinta 6.6 [Lema Bar-Hillel]

Fie L un limbaj independent de context oarecare. Atunci există numerele naturale p = p(L) şi q = q(L) astfel încât orice cuvânt w ∈ L cu |w| > p se poate descompune sub forma w = uvxyz, unde |vxy| ≤ q, vy ≠ λ şi pentru oricare număr natural i, uvixyiz ∈ L. Demonstraţie. Dacă λ ∈ L atunci se ia p = p(L’) şi q = q(L’) unde L’ = L – λ. Presupunem că λ ∉ L şi fie G = (Ω, Σ, S, P) o gramatică de tip doi în forma normală Chomsky astfel încât L = L(G). Dacă |Ω| = n, luăm p = 2n şi q = 2n-1. Fie w∈ L cu |w| > p. Folosind teorema 6.2 rezultă că cel mai lung lanţ de la rădăcină la vârfurile terminale, din arborele de derivare al cuvântului w, pornind de la simbolul de start S, conţine cel puţin n + 2 noduri. În caz contrar ar rezulta că |w| ≤ 2n.

Deoarece |Ω| = n rezultă că cel mai lung lanţ conţine două noduri n1 şi n2 etichetate cu acelaşi neterminal X. Presupunem că nodul n1 este mai aproape de rădăcina S decât nodul n2 şi fie D1 subarborele de rădăcină n1. Evident frontiera lui D1, notată cu a, conform teoremei 6.2, are lungimea (notată cu |a|) cel mult 2n+1. Fie D2 subarborele cu rădăcina n2 şi frontiera x. Atunci există v ∈ Σ* şi y ∈ Σ* astfel încât a = vxy. Evident, v şi y nu pot fi simultan vide pentru că regula care se aplică din n1 este de forma X ::= YZ, cu Y şi Z neterminale. Există şi cuvintele u şi z peste Σ astfel încât S uXy uvXyz uv→* →* →* 2Xy2z … uv

→* →*

ixyiz, i≥1. De asemenea, |vxy| = |a| ≤ q, iar vy ≠ λ şi uvixyiz∈L pentru orice i ≥ 0. Exemplul 6.3

Un exemplu simplu de limbaj care nu este independent de context este L = anbncn | n ≥ 1. Prin reducere la absurd, putem presupune contrariul, adică L este un limbaj independent de context. Atunci există constantele p şi q date de lema

Bar-Hillel. Se alege un număr natural k > p / 3 şi cuvântul w = akbkck de lungime mai mare ca p. Din descompunerea furnizată de teorema 6.4 rezultă că v şi y conţin cel mult una din literele a, b sau c; altfel prin iterare nu s-ar mai păstra ordinea alfabetică. Totuşi prin iterare ar trebui să se obţină acelaşi număr de simboluri a, b şi c, ori nu pentru orice i ≥ 0 se poate obţine acest lucru. Rezultă că L nu este un limbaj independent de context. Cerinta 6.7

Fie G o gramatică independentă de context. Atunci L(G) este infinit dacă şi numai dacă există w ∈ L(G) astfel încât p < |w| ≤ p + q, unde p şi q sunt numerele furnizate de teorema 6.4. Demonstraţie. Dacă L(G) este infinit rezultă că există w ∈ L(G) cu |w| > p, deoarece Σ este o mulţime finită. Dacă |w| ≤ p + q atunci stop, altfel aplicarea teoremei 6.4 şi alegerea lui i = 0, în procesul iterativ conduce la un cuvânt mai scurt, dar de lungime mai mare ca p. După un număr finit de paşi se ajunge la un cuvânt cu lungimea cel mult p + q. Afirmaţia reciprocă rezultă din aplicarea teoremei 6.4 şi generarea unui şir infinit de cuvinte prin iteraţie.

7. Gramatici şi automate Cerinta 7.1

Fie G = (Ω, Σ, S, P) o gramatică liniară la dreapta7. Atunci există un automat finit nedeterminist (deci şi unul determinist) M astfel încât L(M) = L(G). Demonstraţie. Fără a restrânge generalitatea putem presupune că simbolul S nu apare în membrul drept al nici unei reguli din P, iar fiecare regulă are una din formele: A ::=a şi A ::= aB cu A, B ∈ Ω şi a ∈ Σ.

Fie X ∉ Ω ∪ Σ şi automatul finit nedeterminist M = (Ω∪X, Σ, δ, S, S1) unde δ : (Ω ∪ X)xΣ → P(Ω ∪ X) este definită prin:

=∅∉=≠∈=∈=≠∪∈=

=,,

::,,::|::,,::|

),(XY

PaYXYPaAYAPaYXYXPaAYA

aYδ

iar S1 = S, X dacă S ::= λ ∈ P şi S1 = X dacă S ::= λ ∉ P. Vom demonstra că L(M) = L(G), prin dublă incluziune. Fie w ∈ Σ*, w ≠ λ,

astfel încât w = a1a2…an, n ≥ 1 şi ai ∈ Σ, i = 1, 2, …, n. Atunci w ∈ L(G) dacă şi numai dacă există producţiile Di ::= aiDi+1 ∈ P, cu D1 = S, i = 1, 2, …, n-1 şi Dn ::= an ∈ P. Deci există stările s1, s2, …, sn+1, unde sn+1 = X, iar s1 = S, sn+1 ∈ S1, si+1 ∈ δ(si, ai), i = 1, 2, …, n, echivalent cu w ∈ L(M). Este uşor de văzut că dacă w ∈ L(M) atunci w ∈ L(G).

Caz special: Dacă w = λ şi w ∈ L(G) atunci există unica producţie S ::= λ ∈ P, deci S1 = S, X, adică S ∩ S1 ≠ ∅, ceea ce este echivalent cu λ ∈ L(M). Cerinta 7.2

Orice limbaj generat de o gramatică liniară8 este regulat.

7 A se vedea şi propoziţia 2.5 (manual).

Demonstraţie. Se aplică teorema 3.1, teorema 3.2 şi teorema 7.1 (din manual) Exemplul 7.1

Fie gramatica G = (Ω, Σ, S, P), unde Ω = S, A, B, Σ = a, b şi P = S ::= aA | a, A ::= bB, B ::= aA | a.

Un AFN care recunoaşte limbajul L(G) are stările S, A, B, X, mulţimea stărilor finale este X, iar funcţia de tranziţie este:

δ A B S A, X ∅ A ∅ B B A, X ∅ X ∅ ∅

Cerinta 7.3

Pentru orice limbaj regulat L există o gramatică liniară G astfel încât L=L(G). Demonstraţie. Fie automatul finit determinist M = (Q, Σ, δ, q0, F) astfel încât L = L(M). Gramatica echivalentă G = (Ω, Σ, S, P) se construieşte astfel: Ω = Q, S = q0, iar pentru λ ∉ L(M) mulţimea regulilor P este p ::= aq | δ(p, a) = q ∪ p ::= a | δ(p, a) ∈ F. Dacă λ ∈ L(M) atunci q0 ∈ F şi adăugăm un simbol nou S, ca simbol de start şi regulile S ::= q0 | λ. Gramatica obţinută este echivalentă cu o gramatică liniară prin eliminarea redenumirilor şi definiţia 5.1(manual) Egalitatea L(G) = L(M) rezultă imediat. Exemplul 7.2

Fie automatul dat prin tabelul

δ a b C q0 q1 Q0 q1 q1 q2 q2 q2 Q0

Cu starea iniţială q0 şi F = q0. Deoarece λ ∈ L(M), în prima fază, rezultă următoarele reguli:

S ::= q0 | λ; q0 ::= aq1 | cq0 | c; q1 ::= aq1 | bq2; q2 ::= bq2 | cq0 | c.

După eliminarea redenumirilor se obţine: S ::= aq1 | cq0 | c | λ; q0 ::= aq1 | cq0 | c;

8 Din acest motiv gramaticile liniare se mai numesc şi gramatici regulate. Rezultă, de aici, că familia limbajelor de tip 3 conţine limbajele finite şi este închisă la operaţiile de reuniune, produs şi stelare (*). Astfel, limbajele de tip 3 sunt descriptibile cu ajutorul expresiilor regulate, generabile de gramatici liniare şi recunoscute de sisteme tranziţionale şi deci de automate finite.

q1 ::= aq1 | bq2; q2 ::= bq2 | cq0 | c.

Un automat pushdown (cu memorie locală gestionată prin disciplina LIFO

[eng. Last In First Out] – numită memorie pushdown) citeşte banda de intrare (de la stânga la dreapta) folosind un număr de stări interne (ca şi un AFD sau AFN), dar tranziţia, în general nedeterministă, se face nu numai în raport cu starea anterioară şi informaţia curentă de pe banda de intrare, ci şi în funcţie de cea mai recentă informaţie stocată în memoria auxiliară (prelucrată ca o stivă de capacitate infinită). Observaţia 7.1

Mişcarea automatului este posibilă numai dacă memoria stivă este nevidă. Exemplul 7.3

Fie Q = q0, q1, q2, Σ = a, b, Γ = a, Z0, F = q0 şi funcţia de tranziţie δ definită astfel: δ(q0, a, Z0) = (q1, aZ0), δ(q1, a, a) = (q1, aa), δ(q1, b, a) = (q2, λ), δ(q2, b, a) = (q2, λ), δ(q2, λ, Z0) = (q0, λ), δ(q, x, Z0) = ∅ în celelalte cazuri. Fie M = (Q, Σ, Γ, δ, q0, Z0, F). Se poate arăta că L(M) = anbn | n ≥ 0. Cerinta 7.4 [Un limbaj recunoscut de un APD cu stări finale poate fi recunoscut şi de un APD cu memoria pushdown vidă]

Fie L(M) limbajul recunoscut de automatul pushdown M = (Q, Σ, Γ, δ, q0, Z0, F). Atunci există un APD, notat M’=(Q’, Σ, Γ’, δ’, qinit, X, ∅), care recunoaşte L(M) cu memoria pushdown vidă, adică Lλ(M’) = L(M). Demonstraţie. Fie Q’ = Q ∪ qinit, qλ unde qinit şi qλ sunt două elemente distincte şi noi în raport cu Q. De asemenea, considerăm X un simbol nou în raport cu Γ şi formăm Γ’ = Γ∪X. Dacă definim δ’ ca mai jos atunci se poate demonstra, prin dublă incluziune – vezi Popovici şi colectiv(1991), că Lλ(M’) = L(M). Funcţia δ’ acţionează conform următoarelor şapte legi:

a) δ’(qinit, λ, X) = (q0, ZoX); b) δ’(q, a, Z) = δ(q, a, Z), pentru oricare q, a şi Z astfel încât q ∈ Q, a ∈ Σ,

Z∈Γ; c) δ’(q, λ, Z) = δ(q, λ, Z) dacă q ∈ Q – F şi Z ∈ Γ; d) δ’(q, λ, Z) = δ(q, λ, Z) ∪ (qλ, λ) dacă q ∈ F şi Z ∈ Γ; e) δ’(q, λ, X) = (qλ, λ) dacă q ∈ F; f) δ’(qλ, λ, Z) = (qλ, λ) dacă Z ∈ Γ∪X; g) δ’(q, a, Z) = ∅ în toate celelalte cazuri.

Cerinta 7.5 [Un limbaj recunoscut de un APD cu memoria pushdown vidă poate fi recunoscut şi de un APD cu stări finale]

Fie Lλ(M) limbajul recunoscut de automatul pushdown M = (Q, Σ, Γ, δ, q0, Z0, ∅). Atunci există un APD, notat M’ = (Q’, Σ, Γ’, δ’, qinit, X, qf), care recunoaşte Lλ(M) cu starea finală qf, adică Lλ(M) = L(M’). Demonstraţie. Fie Q’ = Q ∪ qinit, qf unde qinit şi qf sunt două elemente distincte şi noi în raport cu Q. De asemenea, considerăm X un simbol nou în raport cu Γ şi formăm Γ’ = Γ∪X. Dacă definim δ’ ca mai jos atunci se poate demonstra, prin

dublă incluziune (conform Popovici şi colectiv(1991)), că Lλ(M) = L(M’). Funcţia δ’ acţionează conform următoarelor patru legi:

a) δ’(qinit, λ, X) = (q0, ZoX); b) δ’(q, a, Z) = δ(q, a, Z), pentru oricare q, a şi Z astfel încât q ∈ Q, a

∈Σ∪λ, Z ∈ Γ; c) δ’(q, λ, X) = (qf, λ), dacă q ∈ Q; d) δ’(q, a, Z) = ∅, în toate celelalte cazuri.

Cerinta 7.6

Pentru orice gramatică independentă de context G = (Ω, Σ, S, P) care generează limbajul L = L(G) există un sistem APD care recunoaşte L. Demonstraţie. Presupunem că P conţine reguli de forma u ::= v, cu |u| = 1 şi v ∈ (Ω ∪ Σ)*. Construim automatul M = (q, Σ, Ω ∪ Σ, δ, q, S, ∅) cu funcţia de tranziţie definită prin următoarele trei reguli:

1. [expandare] δ(q, λ, X) = (q, α) | (X ::= α) ∈ P pentru toate regulile mulţimii P;

2. [reducere] δ(q, a, a) = (q, λ), dacă a ∈ Σ; 3. [altfel] δ(q, a, X) = ∅, în toate celelalte cazuri.

Se arată, prin dublă incluziune, folosind metoda inducţiei complete (vezi Popovici şi colectiv(1991)), că L(G) = Lλ(M). Exemplul 7.4

Fie gramatica G = (S, A, 0, 1, 2, S, P) unde P constă din producţiile: S ::= S2 | A2; A ::= 0A1 | 01. Se observă că L(G) = 0n1n2m | n, m ≥ 1.

Sistemul APD care recunoaşte limbajul L(G) este M = (q, 0, 1, 2, S, A, 0, 1, 2, δ, q, S, ∅) unde δ are următoarea definiţie:

δ(q, λ, S) = (q, S2), q, A2); δ(q, λ, A) = (q, 0A1), (q, 01); δ(q, 0, 0) = (q, λ); δ(q, 1, 1) = (q, λ); δ(q, 2, 2) = (q, λ); δ(q, 0, 1) = δ(q, 0, 2) = δ(q, 0, S) = δ(q, 0, A) = ∅; δ(q, 1, 0) = δ(q, 1, 2) = δ(q, 1, S) = δ(q, 1, A) = ∅; δ(q, 2, 0) = δ(q, 2, 1) = δ(q, 2, S) = δ(q, 2, A) = ∅.

Cerinta 7.7

Pentru orice sistem APD care recunoaşte limbajul L cu memoria pushdown vidă, există o gramatică independentă de context care generează limbajul L. Demonstraţie. Fie M = (Q, Σ, Γ, δ, q0, Z0, ∅) un APD astfel încât L = Lλ(M). Construim gramatica G = (Ω, Σ, S, P) cu reguli de forma u ::= v astfel încât |u| = 1, v ∈ (Ω∪Σ)*. Fie S un simbol special astfel încât S ∉ QxΓxQ ∪ Σ. Considerăm mulţimea simbolurilor neterminale ca fiind Ω = QxΓxQ ∪ S, iar fiecare element din QxΓxQ de forma (q, Z, r) îl vom scrie compact sub forma [qZr]. Producţiile din mulţimea P se definesc folosind următoarele reguli:

1. [Start] Pentru fiecare q ∈ Q introducem producţia S ::= [q0Z0q].

2. [Ştergere] Pentru oricare a ∈ Σ ∪ λ astfel încât (r, λ) ∈ δ(q, a, Z) se introduce producţia [qZr] ::= a.

3. [Compunere] Pentru oricare a ∈ Σ ∪ λ pentru care (r, α1α2…αk) ∈ δ(q, a, Z), unde αi ∈ Γ (i = 1, 2, …, k), considerăm toate combinaţiile de k stări s1, s2, …, sk pentru a forma producţii de forma [qZsk] ::= a[rα1s1] [s1α2s2]…[sk-1αksk], unde k > 0.

Prin inducţie completă în raport cu numărul de tranziţii (respectiv în raport cu lungimea derivării) se arată că Lλ(M) ⊆ L(G) (respectiv L(G) ⊆ Lλ(M)). Pentru detalii se poate consulta Popovici şi colectiv(1991). Exemplul 7.5

Fie Q = q0, q1, q2, Σ = a, b, Γ = a, Z0, şi funcţia de tranziţie δ definită astfel: δ(q0, a, Z0) = (q1, aZ0), δ(q1, a, a) = (q1, aa), δ(q1, b, a) = (q2,λ), δ(q2, b, a) = (q2,λ), δ(q2, λ, Z0) = (q0,λ), δ(q, x, Z0) = ∅, în celelalte cazuri. Fie M = (Q, Σ, Γ, δ, q0, Z0, ∅). Se poate arăta că Lλ(M) = anbn | n ≥ 0. A se vedea şi exemplul 7.3.

Gramatica de tip doi care recunoaşte limbajul Lλ(M), construită pe baza metodei dată de demonstraţia teoremei 7.7 are 24 de producţii, după cum urmează. Conform [Start] introducem trei producţii:

S ::= [q0Z0q0] | [q0Z0q1] | [q0Z0q0]. Conform [Compunere] pentru δ(q0, a, Z0) = (q1, aZ0) introducem

următoarele nouă producţii: [q0Z0q0] ::= a [q1aq0] [q0Z0q0]; [q0Z0q0] ::= a [q1aq1] [q1Z0q0]; [q0Z0q0] ::= a [q1aq2] [q2Z0q0]; [q0Z0q1] ::= a [q1aq0] [q0Z0q1]; [q0Z0q1] ::= a [q1aq1] [q1Z0q1]; [q0Z0q1] ::= a [q1aq2] [q2Z0q1]; [q0Z0q2] ::= a [q1aq0] [q0Z0q2]; [q0Z0q2] ::= a [q1aq1] [q1Z0q2]; [q0Z0q2] ::= a [q1aq2] [q2Z0q2];

Folosind [Compunere] pentru δ(q1, a, a) = (q1, aa) obţinem încă nouă producţii:

[q1Z0q0] ::= a [q1aq0] [q0aq0]; [q1Z0q0] ::= a [q1aq1] [q1aq0]; [q1Z0q0] ::= a [q1aq ] [q2 2aq0]; [q1Z0q1] ::= a [q1aq0] [q0aq1]; [q1Z0q1] ::= a [q1aq1] [q1aq1]; [q1Z0q1] ::= a [q1aq2] [q2aq1]; [q1Z0q2] ::= a [q1aq0] [q0aq2]; [q1Z0q2] ::= a [q1aq1] [q1aq2]; [q1Z0q2] ::= a [q1aq2] [q2aq2];

Aplicăm regula [Ştergere] pentru δ(q1, b, a) = (q2, λ) şi δ(q2, b, a) = (q2, λ). Obţinem producţiile: [q1aq2] ::= b şi [q2aq2] ::= b.

Pentru tranziţia δ(q2, λ, Z0) = (q0,λ), obţinem producţia: [q2Z0q0] ::= λ. Evident, λ-producţiile pot fi eliminate şi se obţine o gramatică de tip doi, dar

foarte complexă (în sensul că mărimea mulţimilor Ω şi P este considerabilă). Comparaţi cu gramatica obţinută printr-o simplă modificare a gramaticii din exemplul 2.2 (manual). Observaţia 7.2

Fie M = (Q, Σ, Γ, δ, q0, B, ∅) un sistem MT. Atunci L(M) = ∅. Observaţia 7.3

Fie M = (Q, Σ, Γ, δ, q0, B, Q) un sistem MT. Atunci L(M) = Σ*. Observaţia 7.4

Introducerea nedeterminismului asupra sistemelor MT nu creşte puterea de acceptare. Mai precis, are loc:

Cerinta 7.8

Pentru orice maşină Turing M există o gramatică G, de tip 0, astfel încât L(M) = L(G). Demonstraţie. Se poate urmări Hopcroft şi Ullman(1979). Cerinta 7.9

Următoarele afirmaţii sunt adevărate. a) Pentru orice gramatică dependentă de context (de tip 1) G = (Ω, Σ, S, P)

există o gramatică monotonă G’ = (Ω, Σ, S, P’) astfel încât L(G’) = L(G) – λ.

b) Pentru orice automat liniar mărginit M există o gramatică monotonă G astfel încât L(M) = L(G).

Demonstraţie. Pentru a) se poate consulta, de exemplu, lucrarea Jucan şi Andrei (2002). Pentru b) recomandăm studierea lucrării Hopcroft şi Ullman (1979). Exemplul 7.6

O maşină Turing care acceptă limbajul L = anbncn | n > 0 este M = (Q, Σ, Γ, δ, q0, B, F), unde Q = q0, q1, q2, q3, q4, q5, Σ = a, b, c, Γ = a, b, c, x, y, z, B, F = q5, iar δ este dată prin tabelul: δ A B c x Y z B q0 (q1,x,D) ∅ ∅ ∅ (q4,y,D) ∅ ∅ q1 (q1, a, D) (q2, y, D) ∅ ∅ (q1,y,D) ∅ ∅ q2 ∅ (q2, b, D) (q3, z, S) ∅ ∅ (q2,z,D) ∅ q3 (q3, a, S) (q3, b, S) ∅ (q0,z,D) (q3,y,S) (q3,z,S) ∅ q4 ∅ ∅ ∅ ∅ (q4,y,D) (q4,z,D) (q5,B,D) q5 ∅ ∅ ∅ ∅ ∅ ∅ ∅

8. Proprietăţi de închidere Cerinta 8.1

Familia limbajelor dependente de context este închisă faţă de reuniune. Demonstraţie. Fie L1 şi L2 două limbaje dependente de context generate de gramaticile G1 = (Ω1, Σ1, S1, P1 ) şi G2 = (Ω2, Σ2, S2, P2) astfel încât gramaticile G1 = (Ω1, Σ1, S1, P1 – S1 ::= λ) şi G2 = (Ω2, Σ2, S2, P2 - S2 ::= λ) să fie dependente de context, iar Ω1 ∩ Ω2 = ∅, Ω1 ∩ Σ2 = ∅ şi Ω2 ∩ Σ1 = ∅. Fie S ∉ Ω1 ∪ Ω2 ∪ Σ1 ∪ Σ2.

Formăm gramatica G = (Ω1 ∪ Ω2 ∪S, Σ1 ∪Σ 2, S, P) unde P = (P1 – S1 ::= λ) ∪ (P2 – S2 ::= λ) ∪ S::= w | S1 ::= w ∈ P1 sau S2 ::= w ∈ P2.

Arătăm că L = L1 ∪ L2 este generat de gramatica G. Evident G, fără producţia S ::= λ, este dependentă de context (a se vedea

definiţia 5.1(manual), pentru legătura cu limbajele dependente de context). Fie w ∈ L(G). Presupunem că w ≠ λ. Atunci există o derivare S w. La

primul pas se poate aplica, fie o producţie din P→*

1, fie o producţie din P2. Presupunem că iniţial se aplică o producţie din P , următoarele producţii sunt tot din P

1→*

1, deoarece Ω1 ∩ Ω2 = ∅. Rezultă că S1 w, adică w ∈ L(G1). Analog

pentru aplicarea primei producţii din P2. Dacă w = λ atunci S ::= λ, adică S1 ::= λ sau S2 ::= λ. Deci w ∈ L1 ∪ L2.

Fie w ∈ L1 ∪ L2 – λ. Atunci w ∈ L1 (S1 w, în G→*→*

1) sau w ∈ L2 (S2 w, în G2). Prin înlocuirea primului pas al derivării şi aplicarea producţiei

corespunzătoare din P, obţinem S w, în G. →*

Pentru w = λ raţionamentul este banal. Observaţa 8.1

Enunţul şi demonstraţia de mai sus pot fi refăcute pentru a arăta închiderea la reuniune a familiilor L2 şi L3. Conform teoremei 3.3 (manul), familia limbajelor regulate este cea mai mică familie de limbaje care conţine limbajele finite şi este închisă la reuniune, produs (concatenare) şi la operaţia * (închiderea Kleene). Trebuie remarcat că familia L3 include strict familia limbajelor finite. Cerinta 8.2

Fie Σ un alfabet şi L ⊆ Σ* un limbaj regulat. Atunci Σ* - L este un limbaj regulat Demonstraţie. Dacă L este un limbaj regulat aunci există M = (Q, Σ, δ, q0, F) un sistem AFD astfel încât L(M) = L. Atunci sistemul M1 = (Q, Σ, δ, q0, Q - F) este considerat astfel încât L(M1) = Σ* - L. Cerinta 8.3

Familia limbajelor regulate este închisă la operaţia de intersecţie. Demonstraţie. Se foloseşte faptul că A ∩ B = C(CA ∪ CB), unde prin CX se notează complementara mulţimii X. Observaţia 8.2

Familia limbajelor regulate peste un alfabet Σ, fiind închisă la reuniune, intersecţie şi complementară, formează o algebră booleană în care suma booleană este reuniunea, produsul boolean este intersecţia, iar complementul unui element este obţinut prin formarea limbajului complementar (diferenţa până la Σ*.) Cerinta 8.4

Familia L2 este închisă la reuniune. Demonstraţie. Fie L1 şi L2 două limbaje independente de context generate de gramaticile G1 = (Ω1, Σ1, S1, P1 ) şi G2 = (Ω2, Σ2, S2, P2) astfel încât gramaticile G1 = (Ω1, Σ1, S1, P1 – S1 ::= λ) şi G2 = (Ω2, Σ2, S2, P2 - S2 ::= λ) să fie independente de context, iar Ω1 ∩ Ω2 = ∅, Ω1 ∩ Σ2 = ∅ şi Ω2 ∩ Σ1 = ∅. Fie S ∉ Ω1 ∪ Ω2 ∪ Σ1 ∪Σ 2. Formăm gramatica G = (Ω1 ∪ Ω2 ∪S, Σ1 ∪ Σ 2, S, P) unde P = P1 ∪ P2 ∪ S::= S1, S::= S2. Este uşor de arătat că L = L1 ∪ L2 este generat de gramatica G. Evident redenumirile pot fi eliminate (propoziţia 5.3 - manual), dacă acest lucru este necesar în aplicaţii. Cerinta 8.5

Familia L2 este închisă la concatenare (produs).

Demonstraţie. Fie L1 şi L2 două limbaje independente de context generate de gramaticile G1 = (Ω1, Σ1, S1, P1 ) şi G2 = (Ω2, Σ2, S2, P2) astfel încât gramaticile G1 = (Ω1, Σ1, S1, P1 – S1 ::= λ) şi G2 = (Ω2, Σ2, S2, P2 - S2 ::= λ) să fie independente de context, iar Ω1 ∩ Ω2 = ∅, Ω1 ∩ Σ2 = ∅ şi Ω2 ∩ Σ1 = ∅. Fie S ∉ Ω1 ∪ Ω2 ∪ Σ1 ∪Σ 2. Formăm gramatica G = (Ω1 ∪ Ω2 ∪S, Σ1 ∪ Σ 2, S, P) unde P = P1 ∪ P2 ∪ S::= S1S2. Este uşor de arătat că L = L1L2 este generat de gramatica G. Cerinta 8.6

Familia L2 este închisă la operaţia * (stelare). Demonstraţie. Fie L un limbaj independent de context generat de gramatica G1 = (Ω1, Σ1, S1, P1) astfel încât gramatica G1 = (Ω1, Σ1, S1, P1 – S1 ::= λ) este independentă de context,. Fie S ∉ Ω1 ∪ Σ1 . Formăm gramatica G = (Ω1 ∪ S, Σ1, S, P) unde P = P1 ∪ S::= SS1 | λ. Este uşor de arătat că L* este generat de gramatica G. Evident λ-producţiile pot fi eliminate (propoziţia 5.4 - manual), dacă acest lucru este necesar în aplicaţii. Observaţia 8.3

Dacă L este un limbaj de tip i (i = 2 sau 3) atunci L+ este de tip i. Cerinta 8.7

Familia L2 nu este închisă la intersecţie şi complementară. Demonstraţie. Considerăm limbajele independente de context L1 = anbmcm | n ≥ 1, m ≥ 1 şi L2 = anbncm | n ≥ 1, m ≥ 1 generate de gramaticile G1 = (S1, A1, B1, a, b, c, S1, S1 ::= A1B1, A1 ::= aA1 | a, B1 ::= bB1c | bc) şi G2 = (S2, A2, B2, a, b, c, S2, S2 ::= A2B2, A2 ::= aA2b | ab, B2 ::= cB2 | c). Evident L1 ∩ L2 = anbncn | n ≥ 1 care nu este independent de context, după cum a fost justificat în exemplul 6.3. Deci L 2 nu este închisă la intersecţie. Dacă L2 ar fi închisă la complementară, atunci ar trebui să fie închisă şi la intersecţie deoarece L 2 este închisă la reuniune, iar în teoria mulţimilor are loc relaţia A ∩ B = C(CA ∪ CB). Folosind principiul reducerii la absurd deducem că L2 nu este închisă la complementară. Cerinta 8.8

Fie L ∈ L2 şi R ∈ L3, L1 = L ∩ R şi L2 = L – R. Atunci Li ∈ L2 (i = 1, 2). Demonstraţie. Este suficient să demonstrăm că L1 ∈ L2. Deoarece familia L 3 este închisă la complementară (R ∈ L 3 conduce la CR ∈ L3), iar L – R = L ∩ CR, va rezulta că şi L2 ∈ L2.

Fără a restrânge generalitatea putem continua în următoarele ipoteze: a) L şi R sunt limbaje peste acelaşi alfabet Σ; b) mulţimea L ∪ R nu conţine cuvântul vid λ.

Fie M = (Q, Σ, δ, q0, F) sistemul AFD care recunoaşte limbajul R, L(M) = R. Dacă F = f1, f2, …, fm atunci fie Mi =(Q, Σ, δ, q0, fi) şi Ri = L(Mi), i = 1, 2, …, m. Fie G = (Ω, Σ, S, P) o gramatică de tip 2, în forma normală Chomsky, care generează limbajul L, L(G) = L. Este evident că L ∩ R = (L ∩ R1) ∪ (L ∩ R2) ∪ … ∪ (L ∩ Rm). Prin urmare este suficient să arătam că Li = (L ∩ Ri) este

independent de context, cu i oarecare în mulţimea 1, 2, …, m. Invocarea proprietăţii de închidere a familiei L 2 la reuniune va încheia demonstraţia.

Construim G1 = (Ω1, Σ, S1, P1) gramatica independentă de context astfel încât Ω1 = (Ω ∪ Σ) x Q x Q, S1 = (S, q0, fi) şi P1 conţine toate producţiile de forma:

a. (A, q, q1) ::= (B, q, q2) (C, q2, q1), unde q, q1, q2 ∈ Q, iar A ::= BC ∈ P. b. (A, q, q1) ::= (a, q, q1), unde q, q1 ∈ Q, iar A ::= a ∈ P. c. (a, q, q1) ::= a, a ∈ Σ, δ(q, a) = q1.

Faptul că L(G1) = L ∩ R rezultă din justificarea următoarelor afirmaţii: i→*

→*

→*

→*

→*

1 →*

→*

U∈a

UΣ∈

Σa

a

a) (A, qi, qj) (X→*1, qi, q1) (X2, q1, q2) … (Xn+1, qn, qj) ⇔ A

X1X2 … Xn+1, oricare A, X1, X2, …, X ∈ Ω, q ∈ Q. n+1→*b) (a1, q1, q2) (a2, q2, q3) … (an, qn, qn+1) a1a2…an ⇔ δ(q1, a1a2…an) =

qn+1. Într-adevăr, fie w = a1a2…an ∈ L(G1), deci S1 a→*

→*

1a2…an; (S, q0, fi) (A1, q0, q1) … (An, qn-1, fi) (a→*

→*

1, q0, q1) … (an, qn-1, fi) a1a2…an, prin aplicarea producţiilor în ordinea 1), 2) şi 3), în final. Prin urmare, conform a) obţinem S A1A2…An, iar conform b) rezultă δ(q1, a1a2…an) = fi. Cum fi ∈ F rezultă w ∈ Ri. Obţinem, de asemenea, existenţa producţiilor Ai ::= ai, i = 1, 2, …, n. De asemenea rezultă şi S A1A2…An a1a2…an, echivalent cu w ∈ L. În final obţinem w ∈ L ∩ Ri.

În partea a doua a demonstraţiei considerăm w = a1a2…an ∈ L ∩ Ri. Din w ∈ Ri deducem existenţa stărilor q1, q2, …, qn-1 astfel încât qi = δ(q0, a1a2…ai), i = 1, 2, …, n-1. În plus, fi = δ(q0, a1a …a2

→*n). Derivarea S a→*

1a2…an poate fi scrisă astfel S A1A2…An a1a2…an. Aceste rezultate permit asamblarea unei derivări în G1: S = (A, q0, fi) (A→*

1, q0, q1) … (An, qn-1, fi) (a1, q0, q1) … (an, qn-1, fi) a 1a2…an, adică w ∈ L(G1). Cerinta 8.9

Considerăm transformarea de substituire definită asupra limbajelor ca în definiţia 1.8 - manual. Familia limbajelor independente de context este închisă la substituţii. Demonstraţie. Fie L un limbaj independent de context peste Σ, iar pentru fiecare a ∈ Σ, fie Σa alfabetul asociat lui a. Fie s: Σ* → P(( )*) substituţia lui Σ* în

P(( )*). Evident s are următoarele proprietăţi (din definiţia 1.8): Σ

Σ a

1. pentru oricare a ∈ Σ, s(a) ⊆ Σa; 2. s(λ)=λ; 3. pentru oricare i, 1 ≤ i ≤ k, dacă ai ∈ Σ atunci s(a1a2…ak) =

s(a1)s(a2)…s(ak). Presupunem că, pentru fiecare a ∈ Σ, s(a) este un limbaj independent de

context. Trebuie să arătăm că s(L) este limbaj independent de context. Conform ipotezei, există gramaticile G = (Ω, Σ, S, P) şi Ga = (Ωa, Σa, Sa, Pa)

astfel încât L = L(G) şi s(a) = L(Ga) pentru oricare a ∈ Σ. Presupunem că Ωa ∩ Ωb = Σa ∩ Σb = ∅ pentru a ≠ b şi pentru fiecare a, b ∈ Σ avem Ωa ∩ Σb = ∅ şi Ω ∩ Ωa = ∅. Dacă λ ∈ Σ ∪ Σa (adică S ::= λ ∈ P sau Sa ::= λ ∈ Pa, a ∈ Σ atunci trebuie ca (Ω, Σ, S, P- S ::= λ) şi (Ωa, Σa, Sa, Pa- Sa ::= λ) să fie gramatici independente de context. Definim transformarea t: Ω ∪ Σ ∪ λ → Ω ∪ Sa | a ∈ Σ ∪ λ prin t(λ) = λ; t(X) = X pentru oricare X∈Ω, t(a)=Sa pentru oricare a ∈ Σ astfel încât,

prin extensie, rezultă că pentru oricare x1, x2, …, xn ∈ Ω ∪ Σ ∪ λ are loc relaţia t(x1x2…xn) = t(x1)t(x2)…t(xn).

Formăm gramatica G1 = (Ω1, Σ1, S, P1) astfel încât Ω1 := Ω ∪ ( ), ΣUΣ∈

Ωa

a

UΣ∈

Σa

aΣ

aP

→*

→* →*

1aS

1aS

→*

→*

ΣaP

ΣaP

* S

1 =

, iar P1 = ( ) ∪ X →::= t(α) | X ::= α ∈ P. U∈a

Evident G1 = (Ω1, Σ1, S, P1 – S ::= λ) este independentă de context. Se arată, prin dublă incluziune, că L(G1) = s(L).

a) s(L) ⊆ L(G1): Fie w ∈ s(L) = , deci există α ∈ L astfel încât w =

s(α). Dacă α = λ atunci există, în gramatica G, producţia S ::= λ, deci în G

UL

s∈α

α )(

→*

1 există producţia S ::= t(λ), adică S ::= λ. Obţinem s(λ) = λ, adică w = λ şi w ∈ L(G1). Dacă α ≠ λ atunci există, în gramatica G, simbolurile terminale a1a2…ak astfel încât α = a1a2…ak. Deoarece s(α) = s(a1)s(a2)…s(ak), rezultă că pentru fiecare i, 1 ≤ i ≤ k există wi ∈ s(ai) şi w = w1w2…wk. Din α ∈ L = L(G) rezultă că există, în G, derivarea S α

→*

1 α→*

→*

1a

1aS

2 … α→*

1a

→*

p = α (=a1a2…ak). Prin aplicarea transformării t obţinem existenţa, în G1, a derivării S t(α1) t(α

2aS

→*

kaS

2) … t(α p) = t(α) = t(a1) t(a2) … t(ak) = … .

Deoarece s(akaS

→*

i) = L( G ) atunci există în fiecare G , derivarea wi, i =

1, 2, …, k. Prin urmare w→*i în G1 şi S …

w1aS

2aS1w2 … wk = w. În concluzie, w ∈ L(G1).

b) L(G1) ⊆ s(L): Fie w ∈ L(G1), adică există derivarea S α1 α→*

U∈a

2 … α→*

S

2a kaS

1a →*

1aG

p = w. Deoarece mulţimile de neterminale ale gramaticilor din ipoteză sunt disjuncte (am presupus că Ω ∩ Ωa = ∅ pentru oricare a ∈ Σ) producţiile din P1 de forma X ::= t(α), unde X ::= α ∈ P, pot fi permutate cu producţiile din , astfel încât iniţial să nu se utilizeze producţii din .

Deci există o derivare S w

U∈a

1a S

→*

→*

kaSt ∈ Sa | a ∈ Σ*. Prin urmare există k ≥1 astfel

încât wt = … şi a2a 1a2…ak ∈ L(G). Cum S w, rezultă că →

1a

… w şi apoi obţinem descompunerea w = wS

S1w2…wk astfel încât

wi în G1 şi deci şi în , pentru i = 1, 2, … k. Se mai poate spune că

w1aG

i ∈ L( ), adică wi ∈ s(ai), i = 1, 2, …, k. În concluzie rezultă că w ∈ s(a1)s(a2)…s(ak) = s(a1a2…ak) ⊆ s(L). Observaţia 8.4

Familia limbajelor independente de context este închisă la homomorfisme. Observaţia 8.5

Un sistem gsm este un sistem AFN care, în plus, faţă de banda de intrare (cuvinte peste Σ) conţine şi o bandă de ieşire (pentru manipularea cuvintelor peste

∆). Faptul că (q2, u) ∈ δ(q1, a) arată trecerea din starea q1 in starea q2, când capul de citire a întâlnit simbolul a, dar şi emiterea cuvântului u ∈ ∆* la ieşire. Funcţia δ se extinde la Σ*, în mod obişnuit. Cerinţa 8.10

Orice clasă de limbaje peste alfabetul Σ închisă la substituţii finite şi intersecţie cu limbaje regulate este închisă la transformări gsm. Demonstraţie. Fie C o clasă de limbaje cu proprietatea din enunţ şi sistemul gsm M = (Q, Σ, ∆, δ, q0, F).

Considerăm substituţia finită s: Σ → P(Q x Σ x ∆* x Q) definită astfel încât pentru oricare a ∈ Σ, s(a) = (q1, a, u, q2) | q1, q2 ∈ Q, u ∈ ∆* , (q2, u) ∈ δ(q1, a).

Fie limbajul R ⊆ (Q x Σ x ∆* x Q)* definit prin R = ((q0, a1, u1, q1) (q1, a2, u2, q2) … (qn-1, an, un, qn) | qn ∈ F, (qi, ui) ∈δ(qi-1, ai), i = 1, 2, …, n. Limbajul R este regulat deoarece este acceptat de automatul finit nedeterminist A = (Q, Q x Σ x ∆* x Q, δ1, q0, F), cu q2 ∈δ1(q1, (q1, a, u, q2)) dacă şi numai dacă (q2, u) ∈δ(q1, a) pentru oricare q1, q2 ∈ Q, u ∈ ∆* şi a ∈ Σ.

Definim homomorfismul h : Q x Σ x ∆* x Q → ∆* prin h(q1, a, u, q2) = u, pentru oricare q1, q2 ∈ Q, u ∈ ∆* şi a ∈ Σ.

Atunci pentru oricare L ∈ C, rezultă gM(L) = h(s(L)∩R). Sunt valide echivalenţele: • w ∈ h(s(L) ∩ R) dacă şi numai dacă există α ∈ s(L) ∩ R astfel încât w =

h(α); • α ∈ s(L) ∩ R dacă şi numai dacă există v ∈ L astfel încât α ∈ s(v) ∩ R;

deci α = (q0, a1, u1, q1) (q1, a2, u2, q2) … (qn-1, an, un, qn) , qn ∈ F, (qi, ui) ∈ δ(qi-1, ai), i = 1, 2, …, n; v = a1a2…an.

Prin urmare h(α) = u1u2…un. Deci w ∈ h(s(L) ∩ R) dacă şi numai dacă există cuvintele v = a1a2…an ∈ L, w = u1u2…un ∈ ∆*, stările q0, q1, …, qn ∈ Q, qn ∈ F astfel încât (qi, ui) ∈ δ(qi-1, ai), i = 1, 2, …, n, echivalent cu w ∈ gM(v).

Deoarece gM(L) = h(s(L) ∩ R) pentru L ∈ C, iar C este închisă la substituţii finite şi intersecţia cu limbaje regulate obţinem: L ∈ C ⇒ s(L) ∈ C ⇒ s(L) ∩ R ∈ C ⇒ h(s(L) ∩ R) ∈ C ⇒ gM(L) ∈ C. Observaţia 8.6

Deoarece familiile Li ( i = 2, 3) satisfac condiţille teoremei 8.10 rezultă că acestea sunt închise la transformări gsm.

9. Specificarea sintaxei limbajelor de programare Exemplul 9.1

Vom ilustra utilizarea limbajului C++ în codificarea algoritmului pentru determinarea stărilor accesibile ale unui sistem AFD. Pentru acest exemplu, automatul M este un obiect al clasei Sistem_AFD caracterizat prin atributele: numar_stari = |Q|, cardinal_sigma = | Σ |, stare_initiala = q0 , delta (funcţia de tranziţie) definită ca tablou, stari_accesibile (tablou care va conţine stările accesibile) şi n_accessible (cardinalul mulţimii stărilor accesibile). La declararea automatului se va apela constructorul care va citi datele. Stările accesibile se determină prin apelarea metodei aferente. Afişarea datelor despre automat se realizează, de asemenea, printr-o metodă specifică.

#include <iostream.h> class Sistem_AFD private: int numar_stari; int cardinal_sigma; int q0; int **delta; int *stari_accesibile; // Structură de date organizată ca o coadă int n_accesibile; public: Sistem_AFD(); //Constructor ~Sistem_AFD(); //Destructor Determină_stările_accesibile(); // Metoda care implementează algoritmul 4.1 Afişare_informaţii(); //Vizualizarea informaţiilor Sistem_AFD::Sistem_AFD() //Constructor int i, j; cout << "Introduceţi numărul stărilor iniţiale: "; cin >> numar_stari; // Se presupune că stările vor fi codificate prin numerele naturale // 0, 1, 2, …, numar_stari-1. cout << "Introduceţi numărul simbolurilor alfabetului :"; cin >> cardinal_sigma; // Se presupune că literele vor fi codificate prin numerele naturale // 0, 1, 2, …, cardinal_sigma-1. cout "Introduceţi starea iniţială:"; do cin >> q0; while ((q0 <0) || (q0 >= numar_stari)); delta = new int *[numar_stari]; for (i = 0; i<numar_stari; i++)

delta[i] = new int [cardinal_sigma]; cout << "Introducerea funcţiei de tranziţie." << "Valoarea –1 pentru lipsa tranziţiilor.\n"; for (i=0; i<numar-stari; i++) for(j=0; j<cardinal_sigma; j++) cout << "delta [ " << i << " ][ " << j << " ] ="; cin >> delta[i][j]; stari_accesibile = new int [numar_stari]; n_accesibile = 0; // sfârşit constructor Sistem_AFD :: ~Sistem_AFD() //Destructor int i; for (i = 0; i<numar_stari; i++)

if (delta[i]) delete [ ] delta[i]; if (delta) delete[ ] delta; if(stari_accesibile) delete [ ] stari_accesibile; // Iniţializări implicite delta = NULL; stari_accesibile = NULL; numar_stari = 0;

cardinal_sigma = 0; q0 = 0; n_accesibile = 0; //sfârşit destructor void Sistem_AFD :: Determină_stările_accesibile() int primul_slot = 0; // Tabloul este organizat ca o coadă. // Inserarea presupune incrementarea variabilei ultimul_slot, // iar "eliminarea" din coadă presupune incrementarea variabilei // primul_slot. Tabloul este suficient de // larg pentru a include toate stările automatului. int ultimul_slot = 0; int qc; //starea curentă; int qt; //starea posibil accesibilă din qc; int a_fost_vizitată; // variabilă logică care va atesta prezenţa/absenţa // stării qt în tabloul stari_accesibile; int i, j; // variabile de lucru stari_accesibile[0] = q0; // starea iniţială este accesibilă; while (primul_slot <= ultimul_slot) qc = stari_accesibile[primul_slot]; for (i = 0; i< cardinal_sigma; i++) qt = delta[qc][i]; if (qt != -1) // începe procesul de căutare-secvenţială // în tabloul stărilor accesibile a_fost_vizitată = 0; j = 0; while ((j<=ultimul_slot) && (!a_fost_vizitată)) if (qt == stari_accesibile[j]) a_fost_vizitată = 1; else j++; if (!a_fost_vizitată) stari_accesibile[++ultimul_slot] = qt; // sf. test qt; // sf. iteraţie după i primul_slot++; // sf. while n_accesibile = ultimul_slot+1; // sf. metoda Determină_stările_accesibile void Sistem_AFD :: Afişare_informaţii () cout << "Stările accesibile sunt : \n "; int i; for (i = 0; i < n_accesibile; i++) cout << "stări_accesibile [ " << i << " ] = " << stari_accesibile[i] << "\n"; // sf. metoda Afişare_informaţii // Testarea clasei void main(void) Sistem_AFD M; M.Determină_stările_accesibile(); M.Afişare_informaţii();

Exemplul 9.2 [Liste în Prolog]

Exemplificăm prin câteva predicate utile în prelucrarea listelor, folosind implementarea Turbo Prolog. domains list=integer* /* Se defineste tipul lista de intregi */ predicates wlist(list) /* afisarea elementelor unei liste */ nlist(list,integer) /* Numarul elementelor unei liste */ slist(list,integer) /* Suma elementelor listei */ addx(integer,list,list) /* Adauga x la fiecare element al listei */ addl(list,list,list) /* aduna element cu element doua liste */ dlist(list,list) /* dublarea elementelor unei liste */ rnlist(list,list) /* eliminarea numerelor negative */ inlist(integer,list) /* este in lista? Yes or No */ catlist(list, list, list) /* concatenare de liste */ clauses wlist([]) :- !. wlist([H | T]) :- write(H), nl, wlist(T). nlist([],0) :-!. nlist([_|T],N) :- nlist(T,N1), N=N1+1. slist([],0) :- !. slist([X|C],S) :- slist(C,S1), S=S1+X. addx(X,[], []):- !. addx(X,[A|R], [Y|R1]) :- Y=A+X,addx(X,R,R1). addl([],L,L) :- !. addl(L,[],L) :- !. addl([A|L1],[B|L2],[C|L3]) :- C=A+B,addl(L1,L2,L3). dlist([], []) :- !. dlist([A|B], [A,A|C]) :- dlist(B,C). rnlist([],[]) :- !. rnlist([X|A],[X|B]) :- X>=0, !, rnlist(A,B). rnlist([X|A],B) :- X<0,!, rnlist(A,B). inlist(X, [X|A]) :- !. inlist(X, [_|A]) :- inlist(X,A). catlist([],L,L) :- !. catlist([X|L1], L, [X|L2]):- catlist(L1, L, L2). Exemplul 9.3

Următoarele clause sunt suficiente pentru a permite testarea apartenenţei unui cuvânt la mulţimea cuvintelor acceptate de un sistem AFN. Considerăm automatul prezentat în exemplul 3.4. Stările sunt s1, s2, s3 şi corespund notaţiei cu A, B, C din exemplul 3.4 - manual. Vocabularul este a, b. Declaraţiile Prolog sunt: delta(s1, a, s1). delta(s1, a, s2).

delta(s1, b, s2). delta(s2, a, s1). delta(s2, a, s3). delta(s2, b, s3). delta(s3, a, s2). delta(s3, a, s3). delta(s3, b, s1). stare_iniţială(s1). stare_finală(s2). stare_finală(s3). accepta(X, []) :- stare_finală(X), write("Da"). accepta(X, [Prima_literă | Restul]) :- delta(X, Prima_literă, Y), accepta(Y, Restul). aparţine(W) :- stare-iniţială(X), accepta(X, W). aparţine( _ ) :- write("Nu"). ?- aparţine([a, b, a, b, a, b, b]). Observaţia 9.1

În Prolog se comunică cunoştinţe. Determinarea efectivă a soluţiei este realizată de către nucleul Prolog prin metode specifice: unificare, backtracking etc. Observaţia 9.2

Limbajul Prolog permite atât codificarea algoritmilor recursivi, cât şi a celor nerecursivi. Următoarele declaraţii permit calculul factorialului în ambele variante. 00F] | [#x202A-#x202E] | [#x206A-#x206F] | #xFEFF Exemplul 9.4

Secvenţa XML următoare ilustrează definirea înregistrărilor tip bază de date: <?XML version = "1.0" ?> <!DOCTYPE DOCUMENT [

<!ELEMENT DOCUMENT (CLIENT)*> <!ELEMENT CLIENT (NUMESIPRENUME, DATA, COMENZI)> <!ELEMENT NUMESIPRENUME (NUME, PRENUME)> <!ELEMENT NUME (#PCDATA)> <!ELEMENT PRENUME (#PCDATA)> <!ELEMENT DATA (#PCDATA)> <!ELEMENT COMENZI (POZITIE)*> <!ELEMENT POZITIE (PRODUS, NUMAR, PRET)> <!ELEMENT PRODUS (#PCDATA)> <!ELEMENT NUMAR (#PCDATA)> <!ELEMENT PRET (#PCDATA)> ]>

<DOCUMENT> <!—Date despre clienti--> <CLIENT> <NUMESIPRENUME> <NUME>Ionescu</NUME> <PRENUME>Marian</PRENUME> </NUMESIPRENUME> <DATA>Februarie 23, 2005</DATA>

<COMENZI> <POZITIE> <PRODUS>CAIET DICTANDO</PRODUS> <NUMAR>15</NUMAR> <PRET>25000</PRET> </POZITIE> <POZITIE> <PRODUS>CRETA</PRODUS> <NUMAR>10</NUMAR> <PRET>15000</PRET> </POZITIE> </COMENZI> </CLIENT> <CLIENT> <NUMESIPRENUME> <NUME>Popescu</NUME> <PRENUME>Alexandru</PRENUME> </NUMESIPRENUME> <DATA>Februarie 24, 2005</DATA> <COMENZI> <POZITIE> <PRODUS>CARTE</PRODUS> <NUMAR>1</NUMAR> <PRET>500000</PRET> </POZITIE> <POZITIE> <PRODUS>CD AUDIO</PRODUS> <NUMAR>10</NUMAR> <PRET>150000</PRET> </POZITIE> </COMENZI> </CLIENT> </DOCUMENT>

Exemplul 9.5

Documentul următor defineşte două tipuri de obiecte (cerc şi elipsă) împreună cu atributele acestora.

<?XML version = "1.0" ?> <!DOCTYPE DOCUMENT [ <!ELEMENT DOCUMENT (CERC|ELIPSA)*> <!ELEMENT CERC EMPTY> <!ELEMENT ELIPSA EMPTY> <!ATTLIST CERC X CDATA #IMPLIED Y CDATA #IMPLIED R CDATA #IMPLIED> <!ATTLIST ELIPSA X CDATA #IMPLIED Y CDATA #IMPLIED

L CDATA #IMPLIED H CDATA #IMPLIED> ]> <DOCUMENT> <CERC X="100" Y="100" R="25"> <CERC X="200" Y="160" R="50"> <CERC X="170" Y="100" R="15"> <ELIPSA X="150" Y="100" L="100" H="50"> <ELIPSA X="220" Y="130" L="100" H="50"> <ELIPSA X="60" Y="240" L="80" H="100"> </DOCUMENT>

10. Introducere în analiza sintactică Cerinta 10.1 [Gramaticile dependente de context sunt recursive9.]

Există un algoritm care pentru orice G = (Ω, Σ, S, P) - gramatică dependentă de context – şi orice w ∈ Σ+ decide dacă afirmaţia “w ∈ L(G)” este adevărată. Demonstraţie. Fiind dată gramatica G = (Ω, Σ, S, P), dependentă de context şi w ∈ Σ+ astfel încât |w| = m, definim, prin recurenţă, şirul de mulţimi Xi, i ≥ 0, astfel:

X0 = S, Xi+1 = Xi ∪ v | v ∈ (Ω∪Σ)+, există u ∈ Xi astfel încât u→v şi |v|≤ m, i≥0.

Vom arăta că şirul construit are următoarele proprietăţi: • P1: Xk = v | v ∈ (Ω ∪ Σ)+, S v, |v| ≤ m, k = 0, 1, …; →k

• P2: Xi (i ≥ 0) este un şir ascendent, în sensul relaţiei de incluziune şi

mărginit de U (Ω ∪ Σ)m

k =1

k

0pX

→k

→k

şi există p ∈ N astfel încât Xp = Xp+1.

• P3. Dacă Xp = Xp+1 atunci Xp = Xp+i, oricare i ≥ 0. • P4. Fie p0 = min p | Xp = Xp+1. Atunci w ∈ L(G) dacă şi numai dacă

. w ∈Demonstraţia proprietăţii P1 [prin inducţie în raport cu k]. Fie Yk := v | v ∈

(Ω ∪ Σ)+, S v, |v| ≤ m. Vom arăta că X

k (obţinut prin construcţia recurentă) coincide cu Yk, k = 0, 1, … Pentru k = 0, proprietatea este, în mod evident, adevărată. Este suficient să observăm că X0 = Y0 = S. Presupunem că P1 este adevărată pentru un k oarecare şi demonstrăm că Xk+1 = Yk+1. Iniţial, demonstrăm că Xk+1 ⊆ Yk+1. Fie v ∈ Xk+1. Atunci fie v ∈ Xk, fie v ∈α | α ∈ (Ω ∪ Σ)+, există u ∈ Xk astfel încât u → α şi |α| ≤ m. Dacă v ∈ Xk atunci, prin ipoteza de inducţie rezultă v ∈ Yk, dar Yk ⊆ Yk+1 (o derivare în cel mult k paşi poate fi considerată şi ca derivare în cel mult k + 1 paşi). Prin urmare v ∈ Yk+1. Fie v ∈α | α ∈ (Ω ∪ Σ)+, există u ∈ Xk astfel încât u → α şi |α| ≤ m. Avem succesiv S

u şi u → v şi |v| ≤ m. Deci S v şi |v| ≤ m. Prin urmare v ∈ Y→ +1kk+1. A

9 În teoria algoritmilor, o gramatică formală G se numeşte recursivă dacă există un algoritm care acceptă, la intrare, orice cuvânt w peste vocabularul terminal şi produce, la ieşire, răspunsul la întrebarea: “w ∈ L(G)? “ Nu trebuie să confundăm această noţiune cu cea referitoare la recursivitatea la stânga (resp. dreapta) a gramaticilor, introdusă prin definiţia 2.10.

mai rămas de justificat incluziunea inversă: Yk+1 ⊆ Xk+1. Fie v ∈ Yk+1. Atunci S v şi |v| ≤ m. Rezultă că există u∈(Ω ∪ Σ)→ +1k →k

→k

m

w

+ astfel încât S u → v (am pus în evidenţă ultimul pas al derivării), iar u = x1αy1, v = x1βy1 şi α ::= β ∈ P. Deoarece gramatica este dependentă de context, deci şi monotonă, obţinem că |α| ≤ |β|, deci |u| ≤ |v|. Cum |v| ≤ m, rezultă şi |u| ≤ m. Adică u ∈ Yk ⊆ Xk (conform ipotezei de inducţie). În concluzie, v este un element al mulţimii v | v ∈ (Ω ∪ Σ)+, există u ∈ Xk astfel încât u → v şi |v| ≤ m ⊆ Xk+1. Dacă S v şi |v| ≤ m atunci în mod banal v ∈ Yk ⊆ Xk (conform ipotezei de inducţie).

0pX∈

Demonstraţia proprietăţii P2. Construcţia şirului de mulţimi arată şi

caracterul ascendent al şirului. Mărginirea este posibilă deoarece se lucrează cu mulţimile de cardinal finit Ω şi Σ, iar mulţimea cuvintelor de lungime cel mult m este o mulţime finită.

Demonstraţia proprietăţii P3 [prin inducţie în raport cu i]. Cazul i = 1 este chiar cel din ipoteză. Admitem, prin ipoteza de inducţie, că Xk = Xk+i, pentru un i fixat. Dorim să arătăm că proprietatea se păstrează pentru indicele i + 1. Dar Xk+(i+1) = Xk+i ∪ v | v ∈ (Ω ∪ Σ)+, există u ∈ Xk+i astfel încât u → v şi |v| ≤ m = (prin ipoteza de inducţie) Xk ∪ v | v ∈ (Ω ∪ Σ)+, există u ∈ Xk astfel încât u → v şi |v| ≤ m = Xk+1 = Xk.

Demonstraţia proprietăţii P4 Fie w ∈ L(G), deci S w, adică w ∈ X→X

m. Dacă m > p0 atunci se aplică proprietatea P3 şi rezultă că

0p∈ . Dacă m ≤ p0 atunci se aplică proprietatea P2 şi rezultă

0pXw ∈ . Reciproc, dacă , prin aplicarea proprietăţii P

w1, rezultă S w. Prin urmare w ∈ L(G). →≤ 0k

Cele de mai sus ne permit formularea următorului algoritm:

1. k := 0; Xk := S; 2. Repetă paşii

2.1. Xk+1 = Xk ∪ v | v ∈ (Ω ∪ Σ)+, există u ∈ Xk astfel încât u → v şi |v| ≤ m;

2.2. k := k + 1; până când Xk = Xk-1.

3. Dacă w ∈ Xk atunci w ∈ L(G) altfel w ∉ L(G). Exemplul 10.1

Fie gramatica G = (S, A, a, b, S, (S, AA), (S, AS), (S, b), (A, SA), (A, AS), (A, a)) şi w = abaab (|w| = 5). Prin aplicarea propoziţiei 10.1 se obţine următorul şir de mulţimi: X0 = S; X1 = X0 ∪ AA, AS, b; X2 = X1 ∪ SAA, ASA, aA, AAS, Aa, SAS, ASS, aS, AAA, Ab; X3 = X2 ∪ AAAA, ASAA, bAA, SSAA, SASA, SaA, SAAS, SAa, ASSA, aSA, AASA, AbA, ASAS, ASa, aAS, aa, AaS, AAAS, Aab, bAS, SSAS, SASS, SaS, SAAA, SAAS, SAb, ASSS, aSS, AASS, AbS, ASb, aAA, ab, AaA, AAa, , ab

X4 = X3 ∪ SAAAA, ASAAA, aAAA, AASAA, AaAA, AAASA, AAaA, AAAAS, AAAa, SASAA, ASSAA, aSAA, AAAAA, AbAA, ASASA, ASaA, ASAAS, ASAa, bSAA, bASA, baA, bAAS, bAa, SbAA, SSSAA, SSASA, SSaA, SSAAS, SSAa, SASSA, SaSA, SAASA, SAbA, SASAS, SASa, AAaA, ASaA, SaAS, Sab, SaAS, SAASS, SAaS, SAAAS, SAAb, Saa, ASSSA, aSSA, AASSA, AbSA, ASbA, ASSAS, ASSa, aAAA, aASA, abA, AaSA, AAbA, AASAS, AASa, SAbA, AbAS, Aba, aSAS, AbAS, ASASS, ASaS, ASAb, aSa, aASS, aaS, aAAS, aAb, AaAA, AaAS, Aab, ASAAS, AAASS, AAbS, AAAb, SAab, ASab, aab, bSAS, bASS, baS, bAAA, bAAS, bAb, SAAAS, SbAS, SSASS, SSSAS, SSaS, SSAAA, SSAb, bASS, SSASS, SASSS, SaSS, SAASS, SAbS, SASAA, SASb, AAaS, baS, SaAA, bAAAA, SaAA, SAaA, SAAa, ASAb, ASAb, bAb, Sab, ASSSS, aSSS, AASSS, AbSS, ASAAS, ASbS, ASSb, aAAS, abS, aSb, AaSS, AAbS, AASb, SAbS, AbAA, AbAS, Abb, aaA, SAaA, ASaA, aaA, AaAS, Aaa, ASAa, aAa, AASa, Aaa, ... X9 = X8 ∪ abaab, ...

Observăm că w ∈ X9. Prin urmare w ∈ L(G). Cerinta 10.2

Există un algoritm care să determine, pentru o gramatică independentă de context G = (Ω, Σ, S, P) şi un cuvânt w ∈ Σ*, dacă w ∈ L(G) sau w ∉ L(G).

Demonstraţie. Deoarece orice gramatică independentă de context este echivalentă cu o gramatică în forma normală Greibach (teorema 6.3) putem presupune că G este în forma normală Greibach. Dacă w = λ atunci w ∈ L(G) dacă şi numai dacă S ::= λ ∈ P. Presupunem că w ≠ λ. Atunci w ∈ L(G) dacă şi numai dacă S w. În cadrul derivării fiecare producţie adaugă exact un terminal, deci S w (lungimea derivării este egală cu lungimea cuvântului w). Un algoritm pentru a decide dacă w ∈ L(G) sau nu, ar trebui să genereze toate derivările de lungime |w|. Acest lucru este posibil deoarece numărul regulilor este finit şi prin aplicarea metodei backtracking se pot genera toate derivările de o anumită lungime.

→*

→ ||w

Exemplul 10.2

Considerăm datele de intrare din exemplul 10.1. Rezultatul aplicării algoritmului CYK este prezentat în următorul tabel:

j i = 1 i = 2 i = 3 i = 4 i = 5 5 V15 = A, S 4 V14 = A, S V24 = A, S 3 V13 = A, S V23 = S V3,3 = A, S 2 V12 = A, S V22 =A V3,2 =S V42 = A, S 1 V11 =A V21 = S V31 = A V41 = A V51 = S

Cerinta 10.3

Algoritmul CYK (Cocke, Younger şi Kasami) calculează mulţimile Vi,j (j = 1, 2, …, m; i = 1, 2, …, m – j + 1) folosind O(m3) operaţii de reuniune.

Demonstraţie. Complexitatea pasului 1 este O(m). Numărul de operaţii de reuniune din pasul 2 este dat de numărul tripletelor (j, i, k) - cardinalul mulţimii -

(1, 1, _), (1, 2, _), …., (1, m, _), (2, 1, 1), (2, 2 1), …, (2, m-1, 1), (3, 1, 1), (3, 1, 2), (3, 2, 1), (3, 2, 2), …, (3, m-2, 1), (3, m-2, 2), …., (m, 1, 1), (m, 1, 2), …, (m, 1, m-1),

adică o expresie de ordinul O(m3).

Prin _ am notat executarea doar a pasului 2.a. Prin urmare complexitatea algoritmului este de O(m3) operaţii de reuniune.

Pentru obţinerea analizei stângi a unui cuvânt w generat de gramatica G se poate utiliza o procedură recursivă inspirată de schema algoritmului CYK. Se presupune, în continuare, că G este în forma normală Chomsky. Procedura ANALIZA, care furnizează analiza stângă, are următorul cod (în limbaj algoritmic):

Integer n(100); Integer h; Procedure Analiza (i, j, A) Integer i, j; Neterminal A; SEQ if (j = 1) then SEQ h := h + 1; n[h] := #(A ::= ai); END else SEQ If (există k astfel încât k = mins | s = 1, 2, …, j-1, A ::= BC ∈ P, B ∈ Vis , C ∈ Vi+s, j-s) then SEQ h := h+1; n[h] := #(A ::= BC); if (k < j-k) then SEQ Analiza(i, k, B); Analiza(i+k, j-k, C); END else SEQ Analiza(i+k, j-k, C); Analiza(i, k, B); END; END END END

Procedura este apelată prin Analiza(1, |w|, S) numai dacă algoritmul CYK a furnizat rezultatul “w ∈L(G)”. Valoarea variabilei h va fi majorată de valoarea [log2|w|]. Cerinta 10.4

Fie G = (Ω, Σ, S, P) o gramatică independentă de context, nerecursivă la stânga şi A wXu (stânga). Atunci există o constantă reală pozitivă, c, astfel încât

→χ

→χ

|χ| ≤ c|w|+2.

Demonstraţie. Fie n = |Ω| şi arborele corespunzător derivării A wXu (stânga). Atunci, în acest arbore nu există nici un drum de lungime mai mare decât n(|w| + 2). Fie s = max |α| |A ::= α∈P. Cum în arborele de derivare nu sunt mai mult de sn(|w| + 2) noduri interioare, rezultă că lungimea unei analize stângi poate fi

majorată ca în enunţ. Se observă că se poate lua c = sn care depinde numai de gramatica G, nu şi de forma propoziţională. Exemplul 10.3

Fie gramatica cu regulile S ::= aSb | b şi cuvântul w = aaabbb. Prin aplicarea algoritmului de analiză sintactică descendentă rezultă următoarele configuraţii:

(q, 1, λ, S$) |- (q, 1, S1, aSb$) |- (q, 2, S1a, Sb$) |- (q, 2, S1aS1, aSbb$) |- (q, 3, S1aS1a, Sbb$) |- (q, 3, S1aS1aS1, aSbbb$) |- (q, 4, S1aS1aS1a, Sbbb$) |- (q, 4, S1aS1aS1aS1, aSbbbb$) |- (r, 4, S1aS1aS1aS1, aSbbbb$) |- (q, 4, S1aS1aS1aS2, abbbb$) |- (r, 4, S1aS1aS1aS2, abbbb$) |- (r, 4, S1aS1aS1a, Sbbb$) |- (r, 3, S1aS1aS1, aSbbb$) |- (q, 3, S1aS1aS2, abbb$) |- (q, 4, S1aS1aS2a, bbb$) |- (q, 5, S1aS1aS2ab, bb$) |- (q, 6, S1aS1aS2abb, b$) |- (q, 7, S1aS1aS2abbb, $) |- (t, 7, S1aS1aS2abbb, λ).

Analiza sintactică a cuvântului aaabbb este 112 unde indicii şi asocierile sunt

următoarele: 1 (S1) pentru S ::= aSb, respectiv 2 (S2) pentru S ::= ab. Cerinta 10.5

Fie G = (Ω, Σ, S, P) o gramatică independentă de context, fără λ-producţii şi aciclică, w ∈ Σ*, iar A uXw (dreapta). Atunci există o constantă reală pozitivă, c, astfel încât

→χ

|χ| ≤ c|w|. Demonstraţie. În virtutea propoziţiei 5.3, putem presupune că gramatica G nu are redenumiri. Deoarece gramatica nu are λ-producţii atunci în orice derivare X

w, numărul (notat prin h) producţiilor de forma Y ::= α, cu |α| ≥ 2 nu poate depăşi |w|. Evident h < |w|. Vom arăta, prin inducţie după h, că |χ|≤ 2|w|.

→χ

Pentru h = 0, rezultă că |w| = 1, lungimea derivării este 1, deci |χ|≤ 2|w|. Presupunem că h > 1, A → Y1Y2...Ym w (dreapta), deci w = w→*

→*1w2...wm

(proprietatea de localizare) astfel încât Yi wi, prin aplicarea a hi reguli, i = 1, 2, ..., m. Evident h = 1 + h1 + h2 + ... + hm. Fie χi fiecare dintre cele i derivări drepte. Prin ipoteza de inducţie rezultă că |χi| ≤ hi + |wi|. Prin sumare, rezultă că |χ| ≤ 1 + h1 + h2 + ... + hm + |w1| + |w2| + ... + |w | = h + |w| ≤ 2 |w|. m

→*Fie w ∈ Σ*, α ∈ (Ω ∪ Σ)+, şi α u o derivare dreaptă, unde u este un prefix al lui w. Conform celor de mai sus, lungimea derivării este cel mult 2|u|. Numărul analizelor sintactice parţial drepte consistente cu w care se referă la prefixul u este cel mult |P|2|u|, unde |P| reprezintă numărul producţiilor gramaticii date. Cuvântul w are |w| prefixe deci numărul analizelor sintactice este cel mult |P|2 + |P|4 + ... + |P|2|w| < c|w|. În rolul lui c se poate lua, de exemplu, |P|4. Exemplul 10.4

Fie gramatica din exemplul 10.3 şi cuvântul w = a3b3. Conform algoritmului analizei sintactice ascendente au loc următoarele tranziţii:

(q, 1, $, λ) |- (q, 2, $a, D) |- (q, 3, $aa, DD) |- (q, 4, $aaa, DDD) |- (q, 5, $aaab, DDDD) |- (q, 5, $aaS, 2DDDD) |- (q, 6, $aaSb, D2DDDD) |- (q, 6, $aS, 2D2DDDD) |- (q, 6, $aSb, D1D2DDDD) |- (q, 7, $S, 1D2D2DDDD) |- (t, 7, λ, 1D1D2DDDD).

Analiza sintactică a cuvântului aaabbb este 112 unde indicii producţiilor sunt următoarele: 1 pentru S ::= aSb, respectiv 2 pentru S ::= ab.

Bibliografie

1. Academia Română – Institutul de lingvistică ,,Iorgu Iordan”, DEX –

Dicţionarul explicativ al limbii române, Ediţia a II - a, Univers enciclopedic, 1996.

2. Aho, A.V., Ullman, J.D., The theory of parsing, translation and compiling, Vol. I, Prentice-Hall, 1972.

3. Albeanu G., Algoritmi şi limbaje de programare, Editura FRM, 2000. 4. Atanasiu A., Bazele Informaticii, Universitatea din Bucureşti, 1987. 5. Atanasiu A., Mateescu Al., Limbaje formale, Culegere de probleme,

Universitatea din Bucureşti, 1990. 6. Gries D., Compiler Construction for Digital Computers, John Wiley & Sons,

1971. 7. Grigoraş Gh., Limbaje formale şi tehnici de compilare, Universitatea “Al. I.

Cuza”, Iaşi, 1984. 8. Gruska J., On a classification of context-free grammars, Kybernetika, 3(1967),

22-29. 9. Hausser R., Foundations of Computational Linguistics, Human-Computer

Communication in Natural Language, 2nd Edition, Springer, 2001. 10. Hopcroft, J.E., Ullman, J.D., Introduction to Automata Theory, Languages and

Computation, Addison Wesley Publishing Company, 1979. 11. Hristea Florentina, Introducere în procesarea limbajului natural cu aplicaţii în

Prolog, Editura Universităţii din Bucureşti, 2000. 12. Jucan Toader, Andrei Stefan, Limbaje formale şi teoria automatelor,

Universitatea “Al. I. Cuza”, Iaşi, 2002. 13. Maliţa Mihaela, Antrenamente Prolog - Introducere în limbajul de programare

logică Prolog. Editura Universităţii din Bucureşti, 2000. 14. Manna, Z., Mathematical Theory of Computation, McGraw-Hill, 1974. 15. Păun Gh., Câteva gramatici dependente de context, Studii şi cercetări

matematice, Tom 26, Nr. 8, 1974. 16. Păun Gh., Mecanisme generative ale proceselor economice, Editura Tehnică,

Bucureşti, 1980. 17. Păun Gh., Probleme actuale în teoria limbajelor formale, Editura ştiinţifică şi

enciclopedică, Bucureşti, 1984. 18. Popovici C., Rudeanu S., Georgescu H., Bazele Informaticii, Vol II,

Universitatea Bucureşti, 1991. 19. Serbanaţi Luca-Dan, Limbaje de programare şi compilatoare, Editura

Academiei, Bucureşti, 1987. 20. Simovici Dan, Limbaje formale şi tehnici de compilare, EDP Bucureşti, 1978. 21. Ţăndăreanu N., Bazele Informaticii. Exerciţii de calcul boolean, automate şi

limbaje formale, Universitatea din Bucureşti, 1980.

Filehost_Limbaje Formale Si Automate- Grigore Albeanu

Documents

Transcript of Filehost_Limbaje Formale Si Automate- Grigore Albeanu