Modulul 4.

Limbaje independente de context

Cuprins
Introducere .................................................................................................................. 109
Competenţe ................................................................................................................. 109
U1. Arbori de derivaţie pentru gramatici independente de context ............................ 110
U2. Simplificarea gramaticilor independente de context.şi forme normale ............... 116
U3. Lema de pompare pentru limbaje independente de contex ................................. .132
U4. Automate push-down şi legătura lor cu gramaticile independente de context ... .138
U5. Proprietăţi de închidere ale familiei limbajelor de tip 2...................................... .150
Soluţiile testelor de autoevaluare pentru modulul 4 .................................................. .160

Introducere
Modulul 4 este dedicat limbajelor de tip 2 din ierarhia lui Chomsky, numite
limbaje independente de context. Se defineşte noţiunea de arbore de derivaţie,
noţiune foarte importantă în teoria compilării, iar apoi se introduc formele
normale: Chomsky şi Greibach, pentru gramaticile independente de context. Se
introduce aici un nou tip de automat, numit automat push-down nedeterminist, şi
se demonstrează că acest automat recunoaşte limbajele independente de context.

Este prezentat şi automatul push-down determinist, care recunoaşte o subclasă

proprie a limbajelor indpendente de context şi anume clasa limbajelor
independente de context deterministe.

Se studiază proprietăţile limbajelor independente de context printre care şi o lemă

de pompare pentru limbajele independente de context.

Competenţe
La sfârşitul acestui modul studenţii vor fi capabili să:
- Folosească noţiunile definite în descrierea limbajelor formale;
- Construiască gramatici generative şi analitice pentru diferite limbaje;
- Construiască algoritmi normali în sens Markov cu o intrare şi o ieşire
fixată.
- implementeze algoritmii prezentaţi într-un limbaj de programare general

- 109 -
Unitatea de învăţare M4.U1. Arbori de derivaţie pentru gramatici
independente de context
Cuprins
M4.U1.1. Introducere ............................................................................................... 110
M4.U1.2. Obiectivele unităţii de învăţare ................................................................ 110
M4.U1.3. Arbori de derivaţie pentru gramaticile I.D.C. .......................................... 110
M4.U1.5. Rezumat....................................................................................................115
M4.U1.1. Introducere
Limbajele independente de context sunt generate de gramaticile de tip 2 din
ierarhia lui Chomsky, adică gramatici de forma: G = ( VN, VT, S, P),unde
mulţimea regulilor P este de forma: A  α,, cu A variabilă din VN, iar α un şir
format din variabile şi terminale, adică α  (VN VT)*.

Vom prezenta o metodă vizuală de descriere a oricărei derivaţii într-o gramatică

I.D.C. sub forma unui arbore de derivaţie.

M4.U1.2. Obiectivele unităţii de învăţare

La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să:
 înţeleagă şi să explice algoritmii de construcţie ai unui arbore de derivaţie
pornind de la o gramatică independentă de context;
 transforme un arbore de derivaţie în alt arbore de derivaţie înlocuind un
subarbore al arborelui iniţial prin alt subarbore.

Durata medie de parcurgere a unităţii de învăţare este de 2 ore.

M4.U1.3 Arbori de derivaţie pentru gramaticile I.D.C.

Definiţia 3.1.1 Un graf de tip arbore este un graf cu următoarele proprietăţi:

i) există un nod în care nu intră nici un arc, numit rădăcină;
ii) în oricare alt nod intră exact un arc;
iii) există un drum de la rădăcină către oricare nod (graf conex);
iv) nodurile din care nu pleacă nici un arc se numesc frunze.
Definiţia 3.1.2 Fie G= ( VN,VT,S,P) o gramatică I.D.C. Un arbore de derivaţie în G este un
arbore în care:
i) fiecare nod este etichetat cu un simbol din VN  VT ;
ii) eticheta rădăcinii este S;
iii) dacă nodul A are cel puţin un descendent atunci el are o etichetă din VN;

- 110 -
 iv) dacă A1, A2, A3,….,Ak sunt toţi descendenţii direcţi ai lui A în ordine de la stânga
spre dreapta atunci : A  A1A2…Ak este o regulă din P.

A  A1A2…Ak
A1 A2 … Ak

Exemplul 1 ▼ Fie G = ({S,A,B},{a,b},S,P), unde mulţimea P conţine regulile:

S  aAB
S  a
 S
S  bBA

S  b
A  aS a A B

B  bS
a S b S

b a

Fig. 3.1.1.

Figura 3.1.1.
Pentru această gramatică, un arbore de derivaţie având frunzele a,a,b,b şi a este
cel din figura 3.1.1.
Definiţia 3.1.3 Se numeşte rezultat al unui arbore cuvântul format din etichetele frunzelor
citite de la stânga spre dreapta.

Conform acestei definiţii rezultatul arborelui de derivaţie din figura 3.1.1. este cuvântul
aabba.
Vom arăta mai târziu că dacă α este rezultatul unui arbore de derivaţie, atunci:
*
S  α.
G
Definiţia 3.1.4 Se numeşte subarbore al unui arbore graful format dintr-un nod împreună cu
toţi descendenţii săi.

- 111 -
 *
Exemplul 2 Fie arborele de derivaţie de mai jos. Atunci există derivaţia A  ab.
G
A

a S

Teorema 3.1.1 Figura 3.1.2.


Fie G =(VN,VT,A,P ) o gramatică I.D.C. Atunci pentru α  λ , (S  α )  există un
G

arbore de derivaţie în gramatica G al cărui rezultat este α .

▼ Demonstraţie:

Vom demonstra că dacă GA=(VN,VT,A,P) atunci pentru orice A în VN avem (A  α )
GA
dacă şi numai dacă există un subarbore cu rădăcina A al cărui rezultat este α .
Se observă că regulile din P sunt aceleaşi pentru orice gramatică GA, deci
 
( A  α )  (A  α )
GA GB
şi, pentru că G = GS, avem
 
(A  α )  (A  α ).
GA G

a) Presupunem că α este rezultatul unui arbore de derivare în gramatica GA; demonstrăm prin

inducţie, în raport cu numărul de noduri care nu sunt frunze, că A  α :
GA

a1) Dacă există un singur nod care nu e frunză atunci arborele arată ca în
figura 3.1.3.

A1 A2 … Ak

Rezultă că α =A1A2…Ak şi, din definiţia arborelui deFigura

derivaţie, avem A  α  P, deci
3.1.3.

Aα .

a2) Presupunem că α este rezultatul unui arbore A cu n noduri care nu sunt frunze şi
că rezultatul anterior este valabil pentru arbori cu cel mult n-1 noduri care nu sunt frunze.

- 112 -
 Considerăm descendenţii direcţi ai lui A: A1,A2,…,Ak , deci (A  A1….Ak  P).
Dacă Ai nu e o frunză, rezultă că Ai este o variabilă, rădăcină a unui subarbore cu
rezultatul α i şi cu cel mult n-1 noduri care nu sunt frunze.
Dacă Ai este o frunză, punem Ai = α i.
Se observă că dacă j < i atunci nodul Aj şi toţi descendenţii săi se află la stânga lui Ai şi a
tuturor descendenţilor săi.
Rezultă că α = α 1 α 2…… α k .
Deoarece din ipoteza inducţiei α i este rezultatul unui subarbore cu rădăcina Ai şi cu
*
cel mult n-1 noduri care nu sunt frunze, rezultă că (Ai  α i).
G

Deci A  A1A2…Ak  α1α 2 ...α k  α ,
G G

adică
*
(A  α ).
G

b) Presupunem acum că A  α . Vom arăta că există un arbore de derivaţie cu rezultatul α în
GA
GA, prin inducţie relativ la numărul de paşi ai derivaţiei.

b1) Dacă A  α într-un singur pas rezultă că ( A  α P ) şi dacă α =A1A2…Ak rezultă

GA
din definiţia arborelui de derivaţie că există un arbore cu rezultatul α :

A1 A2 … Ak

Figura 3.1.4

b2) Presupunem că A  α în n paşi şi că pentru orice derivaţie a lui β cu numărul de
GA
*
paşi mai mic decât n există o derivaţie cu rezultatul β . Fie primul pas al derivaţiei A  α de
forma A  A1A2…Ak.
Atunci orice simbol al lui α este sau unul dintre Ai sau derivat dintr-un Ai în cel mult n-1
paşi.
Deci, există subarborii T1,T2,..,Tk de rădăcini A1,A2,…,Ak, cu rezultatele α1 , α 2 ,..., α k atunci

când Ai  α i .
GA
Deci dacă la arborele din Figura 3.1.4 adăugăm subarborii Ti, obţinem:

- 113 -
 A

A1 A2 … Ak

T1 T2 Tk

α1 α2 … αk Figura 3.1.5

Rezultă că arborele din Figura 3.1.5 (în care câte un arbore Tj poate fi vid, dacă Aj  VT) are
rezultatul format din rezultatele subarborilor T1, …,Tk în ordine de la stânga α1α 2 ....α k  α .
▲

1. Fie gramatica G=({S, A, B},{a, b}, S, P) cu mulţimea producţiilor P:

S  SS
S  aSb
S  ab
Să se construiască arbori de derivare, dacă este posibil, pentru cuvintele:
x1 = a2b2a2b2,
x2 = aababb,
x3 = babab,
x4 = aabbab.
Dacă nu este posibil să se justifice de ce.

Să ne reamintim...

Fie G= ( VN,VT,S,P) o gramatică I.D.C. Un arbore de derivaţie în G este un

arbore în care:
i) fiecare nod este etichetat cu un simbol din VN  VT ;
ii) eticheta rădăcinii este S;
iii) dacă nodul A are cel puţin un descendent atunci el are o etichetă din
VN;
iv) dacă A1, A2, A3,….,Ak sunt toţi descendenţii direcţi ai lui A în ordine
de la stânga spre dreapta atunci : A  A1A2…Ak este o regulă din P.
Teorema 3.1.1
Fie G =(VN,VT,A,P ) o gramatică I.D.C. Atunci pentru α  λ ,

(S  α )  există un arbore de derivaţie în gramatica G al cărui
G
rezultat este α .

Test de evaluare a cunoştinţelor

I. Întrebări.
1. Ce este un arbore de derivare într-o gramatică IDC G?

- 114 -
 II. Exerciţii propuse.
2. Se consideră arborele din figura următoare. Să se construiască o
gramatică IDC G, astfel încât arborele din imagine să fie arbore de
derivaţie în G.

a S S b
S
 a

M4.U1.4 Rezumat
Unitatea de învăţare prezintă un mod vizual de reprezentare al unei derivaţii într-o
gramatică îndependentă de context, arborele de derivaţie. Obţinerea acestui arbore
de derivaţie este rezultatul esenţial al fazei de analiză sintactică din construcţia
compilatoarelor. În plus arborele de derivaţie este folosit pentru de monstrarea
multor rezultate privind limbajele independente de context.

- 115 -
Unitatea de învăţare M4.U2. Simplificarea gramaticilor
independente de context şi forme normale

Cuprins
M4.U2.1. Introducere ............................................................................................... 116
M4.U2.2. Obiectivele unităţii de învăţare ................................................................ 116
M4.U2.3. Simplificarea gramaticilor I.D.C. ............................................................. 116
M4.U2.4. Forme normale pentru gramatici I.D.C. . ................................................. 122
M4.U2.5. Rezumat. . ................................................................................................ 131

M4.U2.1. Introducere
Regulile independente de context sunt de forma A  α,, cu A variabilă din VN, iar
α un şir format din variabile şi terminale, adică α  (VN VT)*. Pentru că
membrul drept al regulei de rescriere α poate avea orice formă este greu de spus
ceva relativ la numărul de paşi şi lungimea unui cuvânt dintr-o derivaţie.

Se pot însă gasi alte forme de gramatici echivalente care pot fi folosite foarte bine
în demonstraţii sau în construcţii de limbaje independente de context. Astfel de
forme sunt forma normala Chomsky şi forma normală Greibach care se obţin
printr-o serie de transformări pornind de la o gramatică generală independentă de
context.

M4.U2.2. Obiectivele unităţii de învăţare

La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să:
 înţeleagă şi să explice algoritmii de simplificare ai gramaticilor
independente de context;
 înţeleagă şi să explice algoritmii de de construcţie ai formelor normale
pentru gramatici independente de context;
 să foloseasca algoritmii anteriori în construirea unor gramatici în formă
normala Chomsky sau Greibach.

Durata medie de parcurgere a unităţii de învăţare este de 3-4 ore.

M4.U2.3 Simplificarea gramaticilor I.D.C.

Vom arăta întâi cum se poate verifica dacă un limbaj generat de o gramatică I.D.C.
este vid sau nu.

Teorema 3.2.1
Există un algoritm pentru a determina dacă limbajul generat de o gramatică I.D.C. este
vid sau nu.

- 116 -
▼ Demonstraţie:
*
Fie G=(VN,VT,S,P) o gramatică I.D.C.; presupunem că S  w pentru un anume
w  VT* .
Considerăm un arbore de derivaţie al lui w în gramatica G. Presupunem că există un
drum în arbore cu două noduri n1 şi n2 cu aceeaşi etichetă A şi cu n2 descendentul lui n1; fie w1
şi w2 rezultatele arborilor n1 respectiv n2.
* *
Astfel, avem derivaţiile A w1 şi A w 2 , iar w2 este un subcuvânt al lui w1.
Rezultă că w poate fi descompus în forma w=w3w1w4 , unde w3 sau w4 pot fi λ.
Dacă înlocuim subarborele n1 cu n2, obţinem:
*
S  w 3 w 2 w 4  L(G) .
G
În această derivaţie am eliminat cel puţin un nod n1 cu eticheta A. Procesul se poate
repeta, până când în arbore nu mai există nici un drum cu două noduri cu aceeaşi etichetă.
Acest proces este finit, deoarece la fiecare pas se elimină cel puţin un nod.
Considerăm acum ultimul arbore obţinut. Dacă gramatica G are m variabile, atunci în
arborele de derivaţie nu poate exista un drum de lungime mai mare decât m, pentru că în caz
contrar un nod s-ar repeta.
În concluzie, dacă gramatica G generează vreun cuvânt, atunci există o derivaţie a unui
cuvânt a cărui arbore nu conţine nici un drum de lungime mai mare decât m. Rezultă
următorul algoritm:
Formăm o mulţime M de arbori corespunzători derivaţiilor din G, după cum urmează:
 arborele format din nodul S aparţine mulţimii M;
 dacă arborele A  M, se adaugă arborele obţinut din A prin aplicarea unei singure reguli
dacă sunt respectate următoarele două condiţii:
 arborele obţinut nu este în M;
 arborele obţinut nu are drumuri de lungime mai mare decât m.
Procedeul acesta este finit, deoarece există un număr finit de paşi (numărul este
dependent doar de numărul variabilelor m şi de numărul de reguli din P).
*
În final, dacă M conţine vreun arbore al cărui rezultat este din VT , atunci L(G) este
nevid. În caz contrar, L(G)   .
▲

Observaţia 3.2.1 Teorema 3.2.1 este foarte importantă în simplificarea gramaticilor I.D.C.;
însă acest rezultat nu mai este valabil pentru gramaticile D.C.

Teorema 3.2.2
Fie G=(VN,VT,S,P) o gramatică I.D.C. Atunci există o gramatică G1, echivalentă cu G,
*
astfel încât A  VN , α  VT* astfel încât A  α ( adică L(G A )   ).
GA

▼ Demonstraţie:
Fie A  VN . Considerăm GA=(VN, VT, A, P). Conform teoremei 3.2.1, se poate
determina dacă L(GA) este vid sau nu.
Dacă L(G A )   , atunci scoatem A din VN, adică VN  VN \ {A} şi scoatem din P
toate regulile care îl conţin pe A (indiferent în ce membru, stâng sau drept).

- 117 -
După ce eliminăm toţi neterminalii A pentru care L(G A )   , obţinem gramatica
G1=( VN1 ,VT,S,P1). Evident că L(G1 )  L(G) . Să arătăm că L(G) \ L(G1 )   :
Presupunem că există un cuvânt w  L(G) \ L(G1 ) . Atunci există o derivare
* *
S  α1Aα 2  w , cu A  VN \ VN1 .
Astfel, am obţinut două afirmaţii contradictorii:
*
 pe de o parte, w1  VT* astfel încât A  w 1 (deci w1  L(G A ) );
G
 pe de altă parte, deoarece A  VN \ VN1 , avem L(G A )   .
Din contradicţia obţinută rezultă că A  VN , L(G A )   .
▲

În continuare vom elimina simbolurile care nu apar în nici o derivaţie.

Definiţia 3.2.1 Fie G=(VN,VT,S,P) o gramatică I.D.C.


i) A  VN este un simbol inaccesibil dacă nu există S  α1Aα 2 ;
ii) A  VN este un simbol neutilizabil dacă nu există nici o derivare de forma:

S  α1Aα 2  w1w 3 w 2 , unde w i  VT* .

Teorema 3.2.3
Fie G=(VN,VT,S,P) o gramatică I.D.C., astfel încât L(G)   . Atunci există gramatica
G1, echivalentă cu G, astfel încât VN1 nu conţine simboluri neutilizabile, adică:
* *
A  VN1 există o derivaţie S  w1Aw 2  w1w 3 w 2 cu w i  VT* .
▼Demonstraţie:
Presupunem că G este o gramatică deja redusă conform Teoremei 3.2.2 (adică
A  VN , L(G A )   }. Construim în continuare gramatica G1= (VN1 , VT , S, P1 ) .
Mulţimea neterminalelor VN1 se determină iterativ:
 S VN1
 dacă A  VN1 , atunci adăugăm în VN1 toate variabilele B pentru care există în P
câte o regulă A  α1 Bα 2
Procesul se opreşte când nici o nouă variabilă nu mai poate fi adăugată.
*
Fie atunci B VN1 ; în acest caz, există măcar o derivaţie B  w 3  VT* şi există
A1,A2,…,Ak astfel încât:
S  α1A1α1  P

A1  α2 A 2 α2  P *
 şi B w 3 ,
...

A i  αi 1A i 1αi1  P, i  1, k

A k  αk 1 Bαk1  P

- 118 -
de unde rezultă următoarea derivaţie:
* *
S  α1 A1α1  α1 α2 A 2 α2 α1  α1 α2 ...αk 1Bαk 1αk ...α1  w1w 3 w 2

Deci G1 satisface condiţiile teoremei şi este uşor de demonstrat că L(G)=L(G1), unde

P1 se obţine din P înlăturând toate regulile care conţin simboluri din VN \ VN1 .
▲

Sintetizând teoremele anterioare, rezultă următorii algoritmi cu valoare practică:

Algoritm Eliminare Simboluri Inaccesibile:

Intrare G=(VN,VT,S,P)
1
Ieşire G1=(V N ,VT,S,P)

Pas 1 V0={S} , i=1

Pas 2 Vi=Vi-1  { A  VN  B  αAβ  P , B  Vi-1 }
Pas 3 Dacă Vi  Vi-1 atunci i=i+1, salt la Pas 2 ;
altfel VN1=Vi , P1={ A  α A  V N }
1

Algoritm Eliminare Simboluri Neutilizabile:

Intrare G=(VN,VT,S,P)
2
Ieşire G2=( VN ,VT,S,P2)

Pas 1 Vo=  , i=1

Pas 2 Vi=Vi-1  { A A α P, α ( Vi-1  VT)* }
Pas 3 Dacă Vi  Vi-1 atunci i=i+1, salt la Pas 2
altfel VN =Vi , P2= { A  α A  VN }
2 2

Exemplul 7 Să se simplifice gramatica G=({S,A,B,C}, {a,b}, S, P), unde

mulţimea regulilor este dată de următoarele reguli:
S  A
S  B
B  AB

B  Ba
A  aB
P:
A  bS
A  b
C  AS

C  b
▼ Rezolvare:
Eliminăm simbolurile inaccesibile:
V0={S} , i=1
V1={S}  {A,B}={S,A,B} , i=2
V2={S,A,B}  {  }  V1=V2  VN1 ={S,A,B}
- 119 -
 S  A | B 
P1= 
B  AB | Ba 


A  aB | bS | b 
Eliminăm şi simbolurile neutilizabile:
V0=  , i=1
V1=   {A}={A} , i=2
V2={A}  {S} , i=3
V3={A,S}    V3=V2  VN ={A,S}
2

S  A 
P2=  
A  bS

A  b 

▲

Definiţia 3.2.2 Fie G o gramatică I.D.C. Spunem că o derivaţie în G este o derivaţie la

stânga dacă la fiecare pas al derivaţiei se înlocuieşte cel mai din stânga neterminal.

Aşadar, dacă α1  α 2  α 3  ...  α n este o derivaţie la stânga, atunci i {1,..., n  1}

w1i  VT , A  VN , β i2 , β i3  (VN  VT ) astfel încât:
α i  w1i Aβ i2 , α i 1  w1i β i3β i2 .

Lema 3.2.1

Fie G o gramatică I.D.C. Dacă S  w, atunci există o derivaţie la stânga a lui w în G.
▼Demonstraţie:
Demonstraţia se face prin inducţie în raport cu numărul de paşi dintr-o derivaţie.
Pentru n = 1 S  w evident;
Presupunem teorema adevărată pentru orice derivaţie cu lungimea  n-1 şi fie o
derivaţie în n paşi : S  α1  α 2  ...  w .
Luăm în considerare simbolurile primului cuvânt derivat α 1 =A1A2…Ak; atunci

w=w1w2…wk cu Ai  wi în cel mult n-1 paşi.

Deci există o derivaţie la stânga Ai  wi, pentru fiecare i  1, k .
Atunci S  A1A2…Ak  ...  w1w2…wk şi deci există derivaţia la stânga de forma:
  
S  A1A2…Ak  w1A2…Ak  w1w2A3…Ak  ...  w1w2…wk.
▲

Definiţia 3.2.3 Fie G o gramatică I.D.C. G = (VN, VT, S, P). O regulă de forma
A  B  P, unde A, B  VN , se numeşte redenumire.

Teorema 3.2.4
Fie G o gramatică I.D.C.; atunci există gramatica G 1  G fără redenumiri.
▼Demonstraţie
Fie G = (VN, VT, S, P). Construim o nouă mulţime de producţii P1 prin includerea
tuturor producţiilor din P care nu sunt redenumiri.

- 120 -
 *
Presupunem că A  B pentru A, B  VN ; atunci adăugăm în P1 toate regulile de
G
forma A  α , unde B  α  P nu este o redenumire. Se observă că este suficient să
*
considerăm numai acele şiruri de derivaţii A  B a căror lungime este mai mică decât
G
cardinalul mulţimii VN, aceasta deoarece, în caz contrar, în şirul redenumirilor ar apărea cel
puţin o variabilă de două ori, aceasta însemnând că şirul respectiv de redenumiri este
echivalent cu unul mai scurt, în care fiecare variabilă apare o singură dată.
Se obţine astfel gramatica modificată G1=(VN,VT,S,P1). Să verificăm echivalenţa
acesteia cu gramatica G iniţială:
*
a) dacă A  α  P1 , atunci A  α . Deci dacă w  L(G1 ) , atunci w  L(G) .
G
Aşadar L(G1 )  L(G) .
b) fie cuvântul w  L(G) şi considerăm o derivaţie la stânga a lui w în gramatica G:
S  α 0  α1  α 2  ...  α n  w .
G G
Dacă α i  α i 1 (pentru 0  i  n) printr-o producţie care nu e redenumire, atunci
G

α i  α i1 .
G1
Dacă α i-1  α i printr-o regulă care nu este redenumire (i  0)
G
şi α i  α i1 printr-o regulă de tip redenumire
G
şi α i1  α i 2  ...  α j prin reguli care nu sunt redenumiri
G G G
şi α j  α j1 printr-o regulă care nu este redenumire,
G
atunci α i , α i 1 ,...,α j au aceeaşi lungime şi, pentru că derivaţia este o derivaţie la stânga,
simbolul înlocuit în fiecare pas este pe aceeaşi poziţie. Dar atunci
α i  α j1 printr-o producţie din P1 \ P .
G1

Deci α n  L(G1 ), L(G)  L(G1 ) .

Din a) şi b) rezultă că L(G1 )  L(G) .
▲
În practică putem aplica următorul algoritm:

Algoritm Eliminare Redenumiri:

Intrare Gramatica G, independentă de context, G=(VN,VT,S,P)

Ieşire Gramatica G1, independentă de context, fără redenumiri, echivalentă cu G:
1
G1=( VN ,VT,S,P1)

Varianta I
Pas 1 P0={ A  α  P nu este redenumire } , i=1
*
Pas 2 Pi=Pi-1  {A  α j A  B  P  B  α j  Pi 1}

- 121 -
Pas 3 Dacă Pi  Pi-1 atunci i=i+1, salt la Pas 2; altfel
P1=Pi şi V 1N  {A  VN A  α  P1}

Sau

Varianta a II-a
Mai întâi, pentru fiecare A  VN se construieşte RA=  


B A  B astfel:
 
Pas a R0={A} , i=1
Pas b Ri=Ri-1  {C B  C  P, B  R i1}
Pas c Dacă Ri  Ri-1 atunci i=i+1, salt la Pas a;
altfel RA=Ri .
Construcţia propriu-zisă:
Pas 1 P1  
Pas 2 Fie B  α  P . Dacă α  VN atunci salt la Pas 4 ;
altfel continuă cu Pas 3 .
Pas 3 P1  P1  A  α B  R A 
Pas 4 P= P \ B  α . Dacă P   atunci salt la Pas 2 ;
altfel continuă cu Pas 5 .
Pas 5 G1=( V N , VT , S, P1 ), unde VN  A A  α  P1
1 1

M4.U2.4 Forme normale pentru gramatici I.D.C.

Vom arăta, în cele ce urmează, că pentru orice gramatică independentă de context, există o
gramatică echivalentă în care regulile au forme particulare, forme uşor de utilizat în
demonstraţii.

Forma normală Chomsky

Teorema 3.3.1 (Forma normală Chomsky)

Orice limbaj I.D.C. poate fi generat de o gramatică în care toate regulile sunt de forma
A  BC sau A  a, cu A,B,C  VN şi a  VT.

▼Demonstraţie:
Fie G o gramatică I.D.C. Din teorema 3.3.4 rezultă că există o gramatică echivalentă
G1=(VN,VT,S,P) în care nu există reguli A  B, A,B  VN. Deci dacă o regulă are un singur
simbol în partea dreaptă atunci el este un terminal.
Construim forma normală Chomsky în două etape:

a) Considerăm o regulă în P de forma:

A  B1B2…Bm cu m  2 (3.3.1)
Dacă Bi  VT îl înlocuim cu Ci, o nouă variabilă, şi adăugăm regula Ci  Bi la P.
Deci regula (3.3.1) se înlocuieşte cu mulţimea de reguli:
A  C1C2…Cm unde Ci=Bi dacă Bi  VN
Ci  Bi dacă Bi  VT
- 122 -
Atunci mulţimea variabilelor se modifică în V'N =VN  {Ci | Bi  VT} iar P’ va fi mulţimea
noilor reguli.
Fie G2=(V'N,VT,S,P’). Vom demonstra că L(G2)=L(G1).

a1) Din construcţia lui G2, dacă ( α  β ) atunci ( α  β ) şi deci L(G1)  L(G2) .
G1 G2
a2) Vom demonstra prin inducţie în raport cu numărul de paşi într-o derivaţie că dacă
 
A  w ,A  VN, w  VT  atunci A  w.
G2 G1

Pentru n=1 afirmaţia este evidentă.


Presupunem afirmaţia adevărată pentru orice derivaţie în k paşi şi fie A  w prin k+1
G2
paşi. Primul pas în derivaţie trebuie să fie de forma:
A  C1C2…Cm , m  2.
G2

Atunci w=w1w2…wm, unde Ci  wi, 1  i  m în cel mult k paşi. Rezultă că şi în gramatica G
G2

avem: Ci  wi.
G1
Dacă Ci  V'N\VN atunci se poate folosi numai regula Ci  ai pentru ai VT, de unde ai
= wi.
Aşadar, din construcţia lui P’ există o regulă A  B1B2…Bm a lui P cu Bi = Ci dacă Ci  VN şi
Bi=ai dacă Ci  V’N\VN.

Pentru aceşti Ci avem derivaţiile în G2: Ci  wi pentru că nu sunt mai mulţi de k paşi
G2

în derivaţie. Atunci Bi  wi.
G1

Deci A  w, şi în concluzie L(G2)  L(G1).
G1

b) Modificăm acum G2 prin adăugarea unor noi simboluri şi a unor noi reguli şi anume:
- o regulă de forma A  B1B2…Bm cu m  3, A,Bi  VN se înlocuieşte cu
A  B1 D1

D 1  B 2 D 2 , unde Di sunt noi variabile.

...

D m  2  B m 1 B m
 
Astfel rezultă G3 şi evident (A  w)  (A  w) .
G2 G3
▲

Exemplul 1 Fie gramatica G = ({S,T,L}, {a,b,+,*,[,]}, S, P), cu regulile P:

S  T+S
S T

T  L*T

- 123 -
 T L

L  [S]
L a
L b
Să se realizeze transformarea în forma normală Chomsky.
▼ Aplicăm algoritmul ce rezultă din demonstraţia teoremei 3.3.1 :
Pas 1: Eliminăm întâi redenumirile S  T  . Atunci mulţimea de reguli
 
T  L
S  T  S S L*T S  [S]
T  L * T T  [S] Sa 
devine: 
 

L  [S] Ta Sb 
L  a Tb 
 

L  b 

Pas 2: Regulile aflate deja în forma normală Chomsky sunt păstrate ca atare:

L  a Ta S  a
 
L  b Tb S  b

Celelalte reguli sunt înlocuite fiecare în modul următor:

  S  TD 1
S  TC 1S se înlocuiest e cu 
S  T  S se înlocuiest e cu  D1  C1S
C  
 1
  T  LD 2
T  LC 2 T se înlocuiest e cu 
T  L * T se înlocuiest e cu  D 2  C 2 T
C  *
 2
 L  C 3 D 3
L  C 3SC 4 se înlocuiest e cu 

L  [S] se înlocuiest e cu  D 3  SC 4
C
 3  [
C 4 ]
  S  LD 5
S  LC 5T se înlocuiest e cu 
S  L * T se înlocuiest e cu  D 5  C 5 T
C  *
 5
 T  C 6 D 6
T  C 6SC 7 se înlocuiest e cu 

T  [S] se înlocuiest e cu  D 6  SC 7
C 6  [
C 7 ]
În final, gramatica în formă normală Chomsky va fi G3=(VN,VT,S,P3),
unde VN= {S, L, T}  {C i | i  1,7}  {D i | i  1,6} iar P3 conţine următoarele
reguli:

- 124 -
 S  TD1 T  LD 2 
D  C S D2  C2T 
 1 1

C1   C2  * 
 
S  LD 5 T  C6 D6 L  C3D3 
 
D 5  C 5 T D 6  SC7 D 3  SC 4 
C  * C6  [ C3  [ 
 5 
 C 7 ] C 4 ] 
S  a Ta La 
 

S  b Tb Lb 

▲

Forma normală Greibach

În această formă normală fiecare regulă are membrul drept începând cu un terminal,
eventual urmat de variabile.

Lema 3.3.1
Definim o A-regulă ca fiind o regulă cu A în membrul stâng. Fie G=(VN,VT,S,P) o
gramatică I.D.C. şi fie A  α1Bα 2 o regulă din P, astfel încât
{B  β1 ,B  β 2 ,…,B  β r} este mulţimea tuturor B-regulilor din P.
Atunci L(G)=L(G1) unde G1=(VN,VT,S,P1), în care P1 se obţine din P prin eliminarea
regulei A  α1Bα 2 şi adăugarea regulilor A1  α1β1α 2 , A  α1β 2 α 2 ,…, A  α1β r α 2 .

▼Demonstraţie:
Evident L(G1)  L(G) căci dacă A  α1Bα 2 e folosită într-o derivaţie, atunci sigur
există i astfel încât: A  α1Bα 2  α1β i α 2 şi deci A  α1β i α 2 .
G G G1
Pentru a demonstra că L(G)  L(G1) observăm că A  α1Bα 2 este singura regulă din
G care nu este în G1. Ori de câte ori este folosită A  α1Bα 2 , variabila B trebuie să fie
înlocuită într-un târziu de un β i. Aceşti doi paşi pot fi înlocuiţi de unul singur: A  α1β i α 2 .
▲

Lema 3.3.2
Fie G = (VN, VT, S, P) o gramatică I.D.C. şi mulţimea A-regulilor pentru care A este cel
mai din stânga simbol al părţii drepte (reguli cu recursie stângă) de forma: {A  Aα1 ,
A  Aα 2 , . . . , A  Aα r }.
Fie A  β1 , A  β 2 ,…, A  β s , restul A-regulilor din P. Fie G1=(VN  {Z},VT,S,P1)
gramatica I.D.C., formată prin adăugarea variabilei Z la VN şi înlocuirea tuturor A-
regulilor cu:
A   i
(1) 
A   i Z , 1  i  s
Z   i
(2) 
Z   i Z , 1  i  r

- 125 -
 Atunci L(G)=L(G1)

▼Demonstraţie:
Înainte de a demonstra lema să observăm că numai A-regulile generează, prin
derivarea la stânga, limbajul regulat:
{ β1 , β 2 ,..., β s }{ 1 , 2 ,.., r }* ,
aceasta fiind şi mulţimea generată de A-regulile lui G.

a) Fie x  L(G). Dintr-o derivaţie la stânga a lui x în G putem construi o altă derivaţie a lui
x în G, după cum urmează:
De câte ori apare în derivaţia lui x în G o secvenţă de forma:
tA  tAj1 γ  tAj2j1  …  tAjpjp-1 γ  tijpjp-1…j1,
G G G G G

înlocuim întreaga secvenţă cu:

tA  tiZ  tijpZ  …  tijp.. j2Z  tijp…j2j1.
G1 G1 G1 G1 G1

Rezultă o derivaţie în G1, care nu este neapărat o derivaţie la stânga. Folosind acest
rezultat ori de câte ori într-o derivaţie se folosesc reguli cu recursie stângă, rezultă că
L(G)  L(G1).

b) Considerăm acum o derivaţie la stânga a lui x în G1. De câte ori Z apare într-o
derivaţie, reordonăm derivaţia astfel încât Z să fie imediat eliminat. Dacă într-o derivaţie la
stânga folosim regula Z  α Z, atunci α va genera un şir terminal şi va fi folosită altă regulă
cu Z în partea stângă. Este clar că în această secvenţă α poate fi lăsat neschimbat, temporar, şi
poate fi aplicată imediat o regulă de rescriere a lui Z. Desigur, derivaţia nu va fi mai lungă
decât derivaţia la stânga. În final o regulă Z  β i va fi folosită, unde β i nu are Z. Apoi
cuvintele α generate şi β pot să continue generarea normal. Rezultatul derivaţiei rearanjate
este acelaşi ca în derivaţia iniţială.
Înlocuim şirul rezultat de paşi din derivaţie care conţin variabila Z, şi anume:
tA α t βi Zγ  tβi α jp Zγ  ...  tβ i α jp… α j2Z γ  tβ i α jp… α j2 α j1 γ
G1 G1 G1 G1
prin
tAγ  tAα j1 γ  tAα j2 α j1 γ ...  tAα jp… α j1 γ  tβ i α jp… α j1 γ
G G G G
Rezultatul este o derivaţie a lui x în G. Rezultă L(G1)  L(G).
▲

Teorema 3.3.2 (Forma normală Greibach)

Fiecare limbaj I.D.C. poate fi generat de o gramatică pentru care fiecare regulă este de
forma A  aα cu A  VN, a  VT, α  VN ( α un şir de variabile, posibil vid).


▼Demonstraţie:
Fie G=(VN,VT,S,P) o gramatică în forma normală Chomsky generând limbajul L
independent de context.
Presupunem că VN = {A1,A2,…,Am}.

Pas I. În primul pas modificăm regulile astfel încât dacă Ai  Aj γ este o regulă atunci j > i.
Aceasta se poate face în modul următor, începând cu A1 şi terminând cu Am:

- 126 -
 Presupunem că producţiile au fost modificate astfel încât pentru orice i, 1  i  k,
Ai  Aj γ este o regulă numai dacă j > i.
Vom modifica acum Ak+1- regulile.
Dacă Ak+1  Aj γ este o regulă cu j < k+1, generăm o nouă mulţime de reguli,
înlocuind Aj cu partea dreaptă a tuturor Aj-regulilor conform Lemei 3.3.1. Repetând procedeul
de k-1 ori cel mult vom obţine reguli de forma Ak+1  Al γ cu l  k+1. Regulile cu l = k+1
sunt acum înlocuite în conformitate cu Lema 3.3.2, introducând noi variabile Zk+1.
Repetând procedeul pentru fiecare variabilă vom avea reguli de forma:
A k  Al  l  k

A k  a a  VT
Z   ,   (V N  {Z1 , Z 2 ,..., Z m }) *
 k

Pas II. Observăm că pentru Am membrul drept trebuie să înceapă cu un terminal. Partea
dreaptă a oricărei Am-l reguli este sau Am sau un terminal. Când este Am, putem genera noi
reguli înlocuind Am cu membrul drept al unei Am-reguli conform cu Lema 3.3.1. Atunci aceste
reguli trebuie să aibă membrul drept începând cu un terminal. Continuăm de această manieră
cu Am-2,…,A1 până când membrul drept al fiecărei reguli pentru un Ai, începe cu un terminal.

Pas III. La un ultim pas, examinăm regulile pentru noile variabile Z1,Z2,…,Zm. Aceste reguli
încep sau cu un simbol terminal sau cu o variabilă originală. Astfel încă o aplicare a Lemei
3.3.2 completează demonstraţia.
▲

Exemplul 2 Să se aducă la formă normală Greibach gramatica:

1) A 1  A 2 A 3
2) A  A A


2 3 1
G=({A1,A2,A3},{a,b},A1,P) unde P:
3) A 2  b
4) A  A A
 3 1 2


5) A 3  a
▼Rezolvare:

Pas I. Toate A1-regulile şi A2-regulile respectă forma cerută de Teorema 3.3.2 la

acest pas. Dintre A3-reguli, regula 4 are în membrul drept primul simbol pe A1,
deci de indice inferior, necesitând înlocuirea acestui prim simbol cu ajutorul A1-
regulilor (adică regula 1) aplicând Lema 3.3.1:
1) A 1  A 2 A 3
2) A  A A


2 3 1

3) A 2  b
4) A  A A A
 3 2 3 2


5) A 3  a
După înlocuirea lui A1 în regula 4, se vede că trebuie reaplicată Lema
3.3.1, deoarece A3-regula 4' obţinută anterior are în membrul drept primul simbol
pe A2, tot de indice inferior, necesitând înlocuirea acestui prim simbol cu ajutorul
A2-regulilor (adică regulile 2 şi 3). Se înlocuieşte deci regula 4' cu regulile
{4'',4'''}:

- 127 -
 1) A1  A 2 A 3
2) A  A A
 2 3 1

3) A 2  b

4)A 3  A 3 A1 A 3 A 2
4)A 3  bA3 A 2
5) A  a
 3

Pentru a avea toate A3-regulile în forma cerută de teorema anterioară la

acest pas, mai este necesară înlocuirea regulii recursive 4'' cu un nou set de
reguli, conform Lemei 3.3.2, introducând variabila Z3, astfel:
A 1  A 2 A 3
A  A A
 2 3 1

A 2  b
A 3  bA 3 A 2 Z 3

A  aZ
 3 3

A 3  bA 3 A 2

A 3  a
Z  A A A
 3 1 3 2


Z 3  A1A 3 A 2 Z 3
Astfel, toate regulile au ajuns de forma Ai  Aj γ , cu j > i.

Pas II. Toate A3-regulile au în membrul drept primul simbol un terminal.

Folosind setul de A3-reguli, obţinem aceeaşi proprietate şi pentru A2-reguli, prin
înlocuiri conforme cu Lema 3.3.1:

A 2  bA 3 A 2 Z 3 A 1
A  aZ A


2 3 1
A2-reguli:
A 2  bA 3 A 2 A 1
A  aA
 2 1


A 2  b
Similar, pentru A1-reguli, se înlocuieşte setul de A2-reguli în apariţiile din
membrii drepţi, obţinând:
A 1  bA 3 A 2 Z 3 A 1 A 3
A  aZ A A


1 3 1 3
A1-reguli:
A 1  bA 3 A 2 A 1 A 3
A  aA A
 1 1 3


A 1  bA 3
Astfel, toate regulile au ajuns să aibă membrul drept începând cu câte un
terminal.
Pas III. Pentru noua variabilă Z3 introdusă, Z3-regulile trebuie aduse şi ele la
aceeaşi formă cu celelalte (membrul drept să înceapă cu un terminal).
Regula Z 3  A 1 A 3 A 2 se înlocuieşte cu setul de reguli de mai jos (A1 se

- 128 -
înlocuieşte folosind A1-regulile existente):

Z 3  bA 3 A 2 Z 3 A 1 A 3 A 3 A 2
Z  aZ 3 A 1 A 3 A 3 A 2


3
(*) Z 3  bA 3 A 2 A 1 A 3 A 3 A 2
Z  aA 1 A 3 A 3 A 2
 3

Z 3  bA 3 A 3 A 2

Similar, regula Z 3  A 1 A 3 A 2 Z3 se înlocuieşte cu setul de reguli de mai

jos:

Z 3  bA 3 A 2 Z 3 A 1 A 3 A 3 A 2 Z 3
Z  aZ 3 A 1 A 3 A 3 A 2 Z 3


3

(**) Z 3  bA 3 A 2 A 1 A 3 A 3 A 2 Z 3
Z  aA 1 A 3 A 3 A 2 Z 3
 3

Z 3  bA 3 A 3 A 2 Z 3

Astfel, Ai-regulile ( i  1,3 ), obţinute la pasul II, împreună cu cele două

seturi (*) şi (**) de Z3-reguli, obţinute la pasul III, formează noua mulţime de
producţii, în forma normală Greibach. Se observă acum două aspecte importante:

 Pe de o parte, forma normală Greibach a unei gramatici permite ca la fiecare

pas al derivării unui cuvânt să se obţină câte exact un terminal, cunoscând
astfel cu exactitate numărul de paşi ai unei derivări.

 Pe de altă parte, aplicarea algoritmului din Teorema 3.3.2 se vede că

îmbogăţeşte extrem de mult mulţimea de reguli (de la doar 5 reguli iniţiale,
am obţinut anterior 26 reguli pentru forma normală Greibach).
▲

1. Să se elimine simbolurile neutilizabile şi cele inaccesibile din gramatica

G = ({S, A, B, C, D},{a, b, c, d}, S, P) cu regulile:
S  a| aA | B | C
A  aB | b
B  Aa
C  cCD
D  ddd

2. Considerăm gramatica G = ({S, T, L},{a, b, +, -, x, /, [, ]}, S, P) unde

mulţimea P este formată din regulile:

- 129 -
 ST+S TLxT L  [S]
ST–S TL/T La
ST TL Lb
a. Să se construiască o derivaţie şi un arbore de derivaţie pentru

cuvântul a + [a x b – b / a]

b. Să se aducă gramatica la forma normală Chomsky.

3. Considerăm gramatica G = ({L},{p, ~, [, ], }, L, P), unde mulţimea P =

{Lp, L~L, L[L  L]}. Să se construiască forma normală Chomsky
şi apoi forma normală Greibach.

Să ne reamintim...
Forma normală Chomsky
Orice limbaj I.D.C. poate fi generat de o gramatică în care toate
regulile sunt de forma A  BC sau A  a, cu A,B,C  VN şi a  VT.

Forma normală Greibach

Orice limbaj I.D.C. poate fi generat de o gramatică pentru care
fiecare regulă este de forma A  aα cu A  VN, a  VT, α  VN


( α un şir de variabile, posibil vid).

Test de evaluare a cunoştinţelor

I. Întrebări.
1. Cum arată o gramatică IDC în formă normală Chomsky? Descrieţi
algoritmul de construcţie a unei gramatici în formă normală
Chomsky echivalentă cu o gramatică IDC oarecare.

II. Exerciţii propuse.

1. Eliminaţi neterminalele inutilizabile din gramatica:
G=({S, A, B},{a, b}, S, P) cu regulile:
SaS
SAB
SabB
AbA
BAA
Bb

2. Fie gramatica G = ({S, A, B},{a, b}, S, P) cu regulile:

S  bA
S  aB
A  bAA

- 130 -
 A  aS
Aa
B  aBB
B  bS
Bb
Să se găsească o gramatică IDC, G‘, în formă normală Chomsky,
echivalentă cu G.
3. Fie gramatica G = ({x1, x2, x3},{a, b}, x1, P) cu regulile:
(a) x1  x2 x3
(b) x2  x3 x1 | b
(c) x3  x1 x2 | a
Să se determine o gramatică echivalentă cu G care este în formă
normală Greibach.

M2.U2.5 Rezumat
Unitatea de învăţare prezintă o serie de transformări care pot fi făcute asupra
gramaticilor indeprndente de context, fără a schimba limbajul generat, astfel încât
membrul drept al unei reguli de rescriere să semene cu cel al regulilor te tip 3. Asfel
în forma normală Chomsky membrul drept are lungimea 2 sau 1 iar în forma
normală Greibach membrul drept începe cu un terminal. Deşi prin aceste
transformări numărul variabilelor gramaticii iniţiale şi cel al regulilor creşte foarte
mult, aceste forme normale sunt deosebit de utile în demonstraţii, aşa cum vom
vedea în continuare.

- 131 -
 Unitatea de învăţare M4.U3. Lema de pompare pentru limbaje
independente de context
Cuprins
M4.U3.1. Introducere ............................................................................................... 132
M4.U3.2. Obiectivele unităţii de învăţare ................................................................ 132
M4.U3.3. Lema de pompare pentru limbaje I.D.C................................................... 132
M4.U3.4. Rezumat....................................................................................................137

M4.U3.1. Introducere
În unitatea de învăţare M4.U3 am arătat că se pot elimina dintr-o gramatică acele
reguli care nu conduc la cuvinte terminale. De fapt, se poate face mai mult. Putem
testa dacă un limbaj generat de un neterminal este finit sau nu şi să eliminăm acele
variabile (cu excepţia simbolului iniţial al gramaticii) din care se poate genera
numai un număr finit de cuvinte.
.

M4.U3.2. Obiectivele unităţii de învăţare

La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să:
 înţeleagă şi să explice lema de pompare pentru limbaje I.D.C. şi deosebirea
faţă de cazul limbajelor regulate;
 recunoască şi să demonstreze că un anumit limbaj nu este I.D.C., folosind
lema de pompare

Durata medie de parcurgere a unităţii de învăţare este de 3 ore.

M4.U3.3 Lema de pompare pentru limbaje I.D.C. (lema Bar-Hillel)

Teorema 3.4.1 (lema de pompare Bar-Hillel )

Fie un limbaj I.D.C., notat L. Atunci există constantele p şi q, depinzând de L, astfel
încât: dacă z L cu | z |  p , atunci z poate fi scris sub forma: z = uvwxy, unde
| vwx |  q
 astfel încât pentru fiecare întreg i  0 ,
| vx |  0 (v, x nu sunt ambele λ)
uv i wx i z  L .
▼Demonstraţie:
Fie G=(VN,VT,S,P) o gramatică I.D.C. în formă normală Chomsky, pentru L. Dacă G
are k variabile, atunci fie p=2k-1 şi q=2k. Este uşor de observat că, pentru o gramatică în formă
normală Chomsky, dacă un arbore de derivaţie nu are drumuri de lungime mai mare decât j,

- 132 -
atunci cuvântul derivat nu este mai lung decât 2j-1, această valoare reprezentând maximul de
frunze într-un astfel de arbore (binar, datorită formei Chomsky).

Deci, dacă z L şi | z |  p , atunci arborele unei derivaţii a lui z în gramatica G

conţine un drum de lungime mai mare decât k. Să considerăm cel mai lung drum, R, cu
lungimea mai mare decât k.

Atunci există două noduri n1 şi n2 în R astfel încât:

 n1 şi n2 sunt etichetate identic;

 n2 este subarborele lui n1;
 subarborele n1 nu are drumuri de lungime mai mare decât k+1.

Pentru a arăta că n1 şi n2 pot fi astfel găsite, parcurgem drumul R de la frunză înspre
rădăcină. Din primele k+2 noduri, numai o frunză are ca etichetă un simbol terminal. Cele
k+1 noduri rămase nu pot avea etichete distincte.

Subarborele T1, cu rădăcina n1, reprezintă derivaţia unui subcuvânt de lungime cel
k
mult 2 (şi deci de lungime cel mult q), pentru că în T1 nu există nici un drum de lungime mai
mare decât k+1, din cauză că R a fost drumul cel mai lung.

Fie z1 rezultatul subarborelui R. Dacă T2 este subarborele generat de nodul n2 şi z2 este

rezultatul lui T2, atunci z1 se poate scrie z3z2z4. În plus, z3 şi z4 nu pot fi ambele λ, pentru că
prima regulă folosită în derivaţia lui z1 e de forma A  BC , unde B,C  VN . Subarborele T2
trebuie să fie completat în interior sau de subarborele lui B sau de subarborele lui C.

| z3z 2 z 4 |  q .
* *
Avem atunci A  z 3 Az 4  z 3 z 2 z 4 , unde De aici rezultă că
G G
* *
A  z i3 Az i4  z i3 z 2 z i4 pentru i  0 .
G G

Evident şirul z poate fi scris sub forma uz 3 z 2 z 4 y , pentru anumiţi u şi y.

Vom pune acum v=z3, w=z2 şi x=z4, demonstraţia fiind astfel încheiată.
▲
Exemplul 1 Fie gramatica G=({A,B,C},{a,b},A,P), unde
P: A  BC
B  BA
C  BA
Aa
Bb
Fie un arbore de derivaţie în gramatica G de forma din figura 3.4.1. a).
Atunci se vede că există un drum marcat în care se repetă nodul A. Alegem
ultimile două apariţii alee lui A şi notăm
z3=bb z2=a z4=λ z=bbbaba
Putem obţine un nou arbore de derivaţie dacă înlocuim penultimul sum
arbore de etichetă A cu ultimul subarbore de etichetă A, ca în figura 3.4.1.b).
Repetând acest procedeu obţinem un nou arbore de derivaţie în figura 3.4.1.c),
arorae care nu mai prezintă nici un drum pe care se repete vreo variabilă.

- 133 -
 a)

A
Legendă: drum R
B C

B A n B A
1

b B C b a

b B A n
2

b a

b) c)

A n
1
A n
2
B C
a
b B A n
2 Figura 3.4.1
b a

Teorema 3.4.2
Există un algoritm pentru a determina dacă o gramatică G generează un număr finit
sau infinit de cuvinte.
▼Demonstraţie:

Fie p şi q constantele definite în Teorema 3.4.1. Deci dacă z  L(G) şi | z | > p, atunci z
poate fi scris ca uvwxy, unde pentru fiecare i  0, uviwxiy  L şi deasemenea | v | + | x | > 0.
Deci dacă există un astfel de cuvânt atunci L(G) este infinit.
Presupunem că L(G) este infinit. Rezultă că există cuvinte de lungime arbitrară deci şi
cuvântul z, cu | z | > p+q. Acest cuvânt poate fi scris ca uvwxy cu | vwx | < q şi | v |
+ | x | > 0 şi, conform teoremei de pompare,

uwy  L şi | uwy | > p şi | uwy | < | wwwxy |

Dacă | uwy | > p+q atunci repetăm procedura până găsim un cuvânt în L de lungime l
cu p < l  p+q.

Atunci L este infinit dacă şi numai dacă el conţine un cuvânt de lungime l,

p < l  p+q.

- 134 -
 Se poate testa dacă există un cuvânt de lungime mai mare decât p şi de cel mult p+q,
construind toţi arborii de derivaţie care conţin numai drumuri de lungime  p+q şi verificând
condiţia.

Deci dacă există un arbore cu un drum cu lungime mai mare decât p, atunci rezultă că
L este infinit (unde p=2k ).
▲

Observaţia 3.4.1 Teorema 3.4.1 se poate aplica pentru a demonstra că L={akbkck | k  0} nu

este I.D.C.

▼Demonstraţie:
Să presupunem, prin absurd, că limbajul L este I.D.C., ceea ce ar însemna că sunt
îndeplinite consecinţele Teoremei 3.4.1., care permit "pomparea" anumitor subcuvinte din
interiorul unor cuvinte suficient de lungi ale limbajului L.
Se observă, însă, că indiferent de lungimea cuvintelor alese din L, ele fiind de forma z
= akbkck (k  0), nu este posibilă alegerea vreunei descompuneri de forma z=uvwxy cu
proprietăţile specificate în teorema amintită şi astfel încât uv wx y  L .
i i

Să urmărim cazurile posibile. Fie m, n, p  0 ,  k  0). Atunci cuvintele v, w şi x pot fi

de una din următoarele forme:

z=u(vwx)y v w x Motiv uv wx z  L
i i

Grupul de simboluri "a" se

I.
a n1
a n2
a n3 alungeşte independent de grupurile
am(an)ak-m-nbkck
"b" şi "c".
Grupurile de simboluri "a" şi "b" se
alungesc în mod independent. În
a n1 a n2 a n3 b n plus, dacă n3,n  0 , simbolurile "a"
şi "b" se amestecă.
II. Grupurile de simboluri "a" şi "b" se
am(ak-mbn)bk-nck a n1 a n 2 b n3 b n4 alungesc în mod independent.
Grupul de simboluri "b" se
alungeşte independent de grupurile
a n1 b n 2 b n3 b n4 "a" şi "c". În plus, dacă n1,n2  0 ,
simbolurile "a" şi "b" se amestecă.
Grupul de simboluri "b" se
III.
b n1 b n2 b n3 alungeşte independent de grupurile
akbm(bn)bk-m-nck
"a" şi "c".
IV.
Similar cazului II. …
akbm(bk-mcn)ck-n
Grupul de simboluri "c" se
V.
c n1
c n2
c alungeşte independent de grupurile
n3
akbkcm(cn)ck-m-n
"a" şi "b".
În concluzie, prin pompare se va afecta cel puţin una din proprietăţile limbajului
considerat: numărul de simboluri a, b, respectiv c este acelaşi (deci nu se pot multiplica

- 135 -
subcuvinte formate dintr-unul din cele trei simboluri), iar ordinea caracterelor în cuvânt este
strict alfabetică (deci nu se pot multiplica subcuvinte formate din "îmbinarea" a două
simboluri distincte, ab sau bc, căci se amestecă).
Rezultă că {akbkck | k  0}L1 \ L2 deci clasa limbajelor independente de context este
diferită de cea a limbajelor dependente de context:
L1  L2 .
▲

Teorema 3.4.3
Fiind dată o gramatică I.D.C., G1, se poate găsi o gramatică echivalentă G2, pentru
care, dacă A este o variabilă în G2 alta decât simbolul iniţial, atunci există o infinitate
de cuvinte iniţiale derivate din A.

▼Demonstraţie:
Dacă L(G1) este finit atunci L={u1,u2,…,un} şi putem considera G2 cu mulţimea
regulilor P2={S  ui | i=1,n}.
Dacă L(G1) este infinit, G1=(VN,VT,S,P1), considerăm pentru fiecare A  VN gramatica
GA=(VN,VT,S,P1). Prin Teorema 3.4.2 se poate determina dacă L(GA) este finit sau nu.
Presupunem că A1,A2,…,Ak sunt variabilele care generează o infinitate de cuvinte şi că
B1,B2,…,Bm sunt variabilele care generează un număr finit de cuvinte.
Creem mulţimea de reguli P2 din P1 în modul următor:
Presupunem că C0  C1C2…Cr este o regulă din P1, iar C0  {A1,A2,…,Ak}. Atunci
regula C0  u1u2…un este o regulă din P2, unde:
1. Dacă Ci  VT  ui=ci
2. Dacă Ci  {A1,A2,…,Ak}  ui=ci
3. Dacă Ci  {B1,B2,…,Bm}  ui este unul din cuvintele (în număr finit) generate

de ci (ci  ui).
Rezultă că P2 nu conţine nici o regulă cu Bi la dreapta.
' '
Considerăm acum G2=( VN ,VT,S,P2) unde VN ={A1,A2,…,Ak}. Observăm că S trebuie
'
să aparţină lui VN pentru că L(GS) este infinit.
* 
a) Evident, dacă ( α  β ) atunci (α  β ) deci L(G1)  L(G2).
G2 G1

b) Pentru a demonstra L(G2)  L(G1), demonstrăm prin inducţie asupra numărului de

 
paşi din derivaţie că dacă Ai  w 1  i  k unde w VT atunci Ai  w.
*
G1 G2

Rezultatul este evident pentru o derivaţie într-un pas. Presupunem că este adevărat
pentru o derivaţie în cel mult j paşi. Considerăm o derivaţie în j+1 paşi şi presupunem că
prima regulă folosită este Ai  C1C2…Cr .

Putem astfel scrie w sub forma w1w2…wr unde Ci  wi , 1  i  r.
G1

Atunci există o regulă în G2 de forma Ai  u1u2…ur,

w i dacă C i  VT  {B1 ,..., B m }
unde u i   .
 i
C dacă C i  {A 1 ,..., A k }
 
Dar ci  wi în cel mult j paşi  (Ci  wi) .
G1 G2

- 136 -
 
Deci A  u1u2…ur  w1w2…wr .
G2 G2
▲
Exemplul 2 Fie gramatica G=({S,A,B},{a,b,c,d},S,P), unde P={S  ASB,
S  AB, A  a, A  b, B  c, B  d}). Să aplicăm Teorema 3.4.3.

▼Rezolvare:
Variabilele A şi B generează numai cuvintele a şi b respectiv c şi d, dar S
generează o infinitate de cuvinte. Atunci se construieşte G2=({S},{a,b,c,d},S,P2),
mulţimea regulilor fiind:

P2: S  aSc S  ac
S  aSd S  ad
S  bSc S  bc
S  aSd S  bd
▲

Să ne reamintim...
Lema de pompare Bar-Hillel spune că dacă într-un limbaj
independent de context există cuvinte suficient de lungi atunci pot
exista în acele cuvinte cel mult două subcuvinte care pot fi
“pompate”, adică repetate, de ori câte ori şi se obţin cuvite care
aparţin aceluiaşi limbaj.

Test de evaluare a cunoştinţelor

I. Întrebări.
1. Să se enunţe teorema de pompare pentru limabje IDC.

II. Exerciţii propuse.

1. Să se arate că limbajul L = {anbj | n = j2} nu este independent de
context.
2. Să se arate că limbajul L = {ww | w  {a, b}* } nu este independent
de context.

M4.U3.4. Rezumat. Această unitate de învăţare prezintă lema de pompare Bar-Hillel,

care spune ca dacă într-un limbaj independent de context există cuvinte suficient de
lungi, atunci limbajul este infinit.
Această lemă reprezintă un mod de caracterizare al limbajelor de tip 2, IDC, şi poate fi
folosită şi pentru a demonstra că există limbaje care nu sunt de tip 2 dar sunt de tip 1.
De asemenea acest rezultat se foate folosi într-un algoritm de decizie pentru a verifica
dacă un limbaj independent de context dat este infinit sau nu.

- 137 -
Unitatea de învăţare M4.U4. Automate push-down şi legătura lor
cu gramaticile independente de context
Cuprins
M4.U4.1. Introducere ............................................................................................... 138
M4.U4.2. Obiectivele unităţii de învăţare ................................................................ 138
M4.U4.3. Automate push-down ............................................................................... 139
M4.U4.4. Legătura dintre automate push-down şi gramatici de tip 2 ...................... 143
M4.U4.5. Rezumat ................................................................................................... 149

M4.U4.1. Introducere
Vom introduce un nou tip de dispozitiv care să accepte limbajele I.D.C., numit
automat push-down.

Un automat push-down are, pe lângă o bandă de intrare, şi o stivă (o listă LIFO).

Într-o astfel de stivă, intrarea şi ieşirea unui simbol se face numai la capul stivei.
Când un simbol intră în stivă, simbolul care anterior a fost capul stivei devine al
doilea, cel care a fost al doilea devine al treilea ş.a.m.d. În mod similar, când un
simbol este scos din stivă, simbolul care anterior acestei scoateri era al doilea,
ajunge în capul stivei, cel care era al treilea devine al doilea ş.a.m.d.

O astfel de stivă se poate compara cu un teanc de farfurii în care se ridică sau se

pune o farfurie deasupra teancului..

M4.U4.2. Obiectivele unităţii de învăţare

La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să:
 înţeleagă şi să explice funcţionarea unui automat push-down determinist şi
a unui nedeterminist;
 construiască propriul automat push-down pentru un anumit limbajdat;
 construiască o gramatică pentru un anumit limbaj, pornind de la un automat
push-down;
 construiască un automat push-down pentru un anumit limbaj, pornind de la
o gramatică I.D.C. în formă normală Greibach;
 construiască un program într-un limbaj oarecare care să simuleze
funcţionarea unui automat push-down;
 programeze construcţiile anterioare într-un limbaj de programare oarecare.

Durata medie de parcurgere a unităţii de învăţare este de 3-4 ore.

- 138 -
M4.U4.3 Automate push-down

Exemplul 1 Să utilizăm o stivă de "farfurii", cuplată cu un control finit pentru a

recunoaşte o mulţime neregulată.
▼ Fie limbajul I.D.C. L={ wcw ~ | w {0,1} }, care nu este regulat (posibil de
demonstrat acest lucru folosind lema de pompare) şi fie gramatica
G=({S},{0,1,c},S,P)
unde mulţimea regulilor este P= {S  0S0, S  1S1, S  c} .
Pentru a recunoaşte limbajul L, vom utiliza un control finit cu două stări
q1 şi q2 şi o memorie push-down pe care vom plasa "farfurii" albastre, roşii şi
verzi. Dispozitivul va opera după următoarele reguli:
1) Maşina porneşte cu o farfurie roşie pe stivă şi cu controlul finit în
starea q1.
2) Dacă simbolul de intrare este 0 şi starea este q1, dispozitivul
plasează o farfurie albastră pe stivă, iar dacă simbolul de intrare este 1 şi starea
q1, atunci plasează o farfurie verde pe stivă şi, în ambele cazuri, rămâne în starea
q1.
3) Dacă intrarea este c şi starea q1, îşi schimbă starea în q2 fără a
acţiona asupra stivei.
Dacă intrarea este 0, starea q2 şi pe stivă se află o farfurie albastră, scoate farfuria
şi rămâne în q2, iar dacă este 1, starea q2 şi pe stivă este o farfurie verde, scoate
farfuria şi rămâne tot în q2.
1) Dacă dispozitivul este în starea q2 şi pe stivă este o farfurie roşie, scoate
farfuria indiferent de intrare.
2) În alte situaţii dispozitivul nu face nici o mişcare.
Dispozitivul acceptă şirul de intrare dacă, după citirea lui, stiva devine goală.
▲
Vom defini un automat push-down ca fiind un dispozitiv format din: bandă de intrare, control
finit şi memorie push-down (stivă), precum în Figura 3.6.1..
Dispozitivul este nedeterminist, având un număr finit de şanse de mişcare în fiecare situaţie.
Mişcările vor fi de două tipuri:

ai … Banda de intrare

CONTROL Z Capul stivei

FINIT (Q)

Z0
Figura 3.6.1
I. - tranziţie cu simbol de intrare: în funcţie de simbolul de intrare, de capătul stivei şi de
starea controlului finit, sunt posibile anumite mişcări care constau fiecare din: o nouă stare a

- 139 -
controlului finit şi un şir (posibil vid) de simboluri care înlocuieşte capul stivei. După alegerea
unei mişcări posibile, dispozitivul avansează cu un simbol pe banda de intrare.

II. - "λ-tranziţie" : este similară cu mişcarea tip I., dar nu e utilizat nici un simbol de
intrare.

Limbajul acceptat de un automat push-down se poate defini în două moduri:

 mulţimea şirurilor de intrare care conduc la golirea memoriei push-down sau
 mulţimea şirurilor de intrare pentru care automatul intră într-o stare finală.

Cele două tipuri de acceptări sunt echivalente.

Formal, un automat push-down se defineşte prin:

Definiţia 3.6.1 Un automat push-down nedeterminist, M, este un sistem format din:

M = (Q, Σ, Γ, δ, q 0 , Z0 , F) ,
unde:
 Q este o mulţime finită de stări
 Σ este un alfabet finit al benzii de intrare
 Γ este un alfabet finit al memoriei push-down
 q 0  Q stare iniţială
 Z 0  Γ simbol de start al memoriei push-down
 F  Q mulţimea stărilor finale
 δ : Q  (Σ  λ)   P (Q  * )

Vom utiliza următoarele notaţii:

 litere mici de la începutul alfabetului pentru Σ
 litere mici de la sfârşitul alfabetului pentru şiruri din Σ*
 litere mari ale alfabetului pentru elemente din Γ
 litere greceşti pentru cuvinte din Γ*
Interpretarea expresiei δ(q, a, Z)  {(p1, γ1 ), (p 2 , γ 2 ),..., (p m , γ m )} , unde
q, pi  Q, a  Σ, Z  Γ, γ i  Γ* , i  1, m , este aceea că automatul push-down aflat în starea q, cu
a pe banda de intrare şi Z în capul stivei, poate trece într-una din stările pi înlocuind pe Z cu γ i
şi apoi avansează cu un simbol pe banda de intrare.

Interpretarea expresiei δ(q, λ, Z)  {(p1, γ1 ), (p 2 , γ 2 ),..., (p m , γ m )} , unde

q, pi  Q, Z  Γ, γ i  Γ* , i  1, m , este aceea că automatul push-down aflat în starea q şi având
pe Z în capul stivei, indiferent de simbolul aflat pe banda de intrare îşi schimbă starea într-una
din stările pi şi înlocuieşte pe Z cu γ i fără să avanseze pe banda de intrare.

- 140 -
 Exemplul 2 În exemplul anterior, automatul push-down acceptă limbajul
~ | w {0,1} } prin memorie vidă. Să descriem formal acest automat.
{ wcw

▼
M=({q1,q2},{0,1,c},{R,A,V},δ,q1,R,  )

δ(q1 ,0, R)  {(q 1 , AR)} δ(q1 , c, A)  {(q 2 , A)}

δ(q ,1, R)  {(q , VR)} 
 1 1 δ(q1 , c, V)  {(q 2 , V)}
δ(q
 1 ,0, A)  {(q 1 , AA)} δ(q1 , c, R)  {(q 2 , R)} 
 
δ(q1 ,0, V)  {(q 1 , AV)} δ(q 2 ,0, A)  {(q 2 , λ)} 
δ(q1 ,1, A)  {(q 1 , VA)} δ(q 2 ,1, V)  {(q 2 , λ)} 
 

δ(q1 ,1, V)  {(q 1 , VV)} δ(q 2 , λ, R)  {(q 2 , λ)} 

▲

Observaţia 3.6.1 Automatul din Exemplul 3.6.2 este determinist pentru că are o singură
posibilitate de mişcare la fiecare pas.

Un astfel de automat, indiferent dacă este determinist sau nedeterminist, se poate şi el

reprezenta printr-o diagramă de tranziţie[23], similară cu cea pentru automatul finit, cu
excepţia faptului ca una dintre etichetele unui arc între starea p şi starea q, este de forma:
(a, A→ BC) dacă (q, BC)  (p,a,A)
sau, folosind forma din [13]:
(a, A, BC) dacă (q, BC)  (p,a,A)
Să considerăm automatul push-down, definit printr-o diagramă de tranziţie, din figura
2.3.2, care recunoaşte cuvintele limbajului:
{anbn | n ≥ 0}.
0, A → AA
0, Z0 → AZ0
q p

1, A → λ

λ, Z0 → λ
r 1, A → λ
s
λ, Z0 → λ

Figura 3.2.2

Definiţia 3.6.2 O configuraţie instantanee este o pereche (q,), unde qQ şi *, unde cel
mai din stânga simbol al lui γ este vîrful stivei push-down, iar γ reprezintă conţinutul stivei.

- 141 -
 Dacă a  Σ  {λ} , γ, β  Γ* , Z  Γ şi (p, β)  δ(q, a, Z) , atunci scriem:
a : (q,Zγ)├ M (p,βγ) (Intrarea "a" trece automatul M din (q,Zγ) în (p,βγ).)
Dacă pentru fiecare a1..., a n  Σ  {λ} , q1 ,..., q n1  Q şi şirurile γ1 ,..., γ n 1  Γ* ,
avem:
ai : (qi,γi)├ M (qi+1,γi+1) i  1, n ,
atunci scriem:
*
a1… an : (q1,γ1)├ M (qi+1,γi+1)

Similar, se poate folosi descrierea instantanee, constituită din tripletul q, aw, Zα  şi
atunci scriem:
q, aw, Zα├ M (p,w,βα) dacă (p, β)  δ(q, a, Z) .
Definiţia 3.6.3 Limbajul acceptat prin stări finale de către automatul M este
L(M)  {w w  Σ* , (q 0 , w, Z0 ) ├ M p, λ, γ , γ  Γ* , p  F} .
*

Definiţia 3.6.4 Limbajul acceptat prin stivă vidă de către automatul M este
N(M)  {w w  Σ* , (q 0 , w, Z0 ) ├ M p, λ, λ , p  Q}.
*

Exemplul 3 Să construim automatul push-down care acceptă limbajul

~ | w {0,1} }.
{ ww

▼
M=({q1,q2},{0,1},{z0,A,B},δ,q1,Z0,  )

δ(q1 ,0, Z 0 )  {(q 1 , AZ 0 )} δ(q 2 ,0, A)  {(q 2 , λ)} 

δ(q ,1, Z )  {(q , BZ )} 
 1 0 1 0 δ(q 2 ,1, B)  {(q 2 , λ)} 
δ(q1 ,0, A)  {(q 1 , AA), (q 2 , λ)} 
 
δ(q1 ,0, B)  {(q 1 , AB)} δ(q1 , λ, Z 0 )  {(q 1 , λ)} 
δ(q1 ,1, A)  {(q 1 , BA)} δ(q 2 , λ, Z 0 )  {(q 2 , λ)}
 
δ(q1 ,1, B)  {(q 1 , BB), (q 2 , λ)} 

Spre exemplu, şirul de intrare 001100 este acceptat de automatul

push-down deoarece există un calcul de configuraţii care se finalizează prin
golirea memoriei push-down după citirea benzii de intrare:

(q1 ,001100, Z0 ) ├ M (q1 ,01100, AZ 0 ) ├ M (q1 ,1100, AAZ 0 ) ├ M

├ M (q1 ,100, BAAZ 0 ) ├ M (q 2 ,00, AAZ 0 ) ├ M (q 2 ,0, AZ 0 ) ├ M
(q 2 , λ, Z 0 ) ├ M
├ M (q 2 , λ, λ) ,

deci 001100  N(M) .

- 142 -
 Problema care apare în acest exemplu este de a determina mijlocul
cuvântului de pe banda de intrare. Pentru determinarea mijlocului, singura
condiţie cunoscută este de a avea pe banda de intrare doi de 0 consecutivi sau doi
de 1 consecutivi. Însă această condiţie nu determină în mod precis mijlocul
cuvântului de intrare, situaţia nefiind unică. Astfel, automatul push-down poate
"bănui" că a ajuns la mijlocul cuvântului de intrare ori de câte ori apar doi de 0
sau doi de 1 consecutivi. Deci, de câte ori automatul întâlneşte două simboluri
identice pe banda de intrare, are de ales între două variante: "bănuieşte" că aici
este mijlocul şi
trece în starea q2, care începe să şteargă stiva, sau "bănuieşte" că nu este la
mijloc şi continuă să memoreze în stivă. Dacă a "bănuit" corect atunci va reuşi
să-şi golească stiva.
De aici apare nedeterminismul.
▲

Observaţia 3.6.2

a) Un automat push-down este determinist dacă sunt îndeplinite următoarele condiţii:

- pentru fiecare qQ, a şi Z corespunzătoare, (q,a,Z) nu conţine mai mult de un
element;
- pentru fiecare qQ şi Z, dacă δ(q, λ, Z)   atunci δ(q, a, Z)  , a   (aceste
condiţii evită situaţia în care ar fi posibile atât o λ-mutare cât şi o mutare nevidă, generând
astfel nedeterminism).

b) Pentru automatele push-down în general, modelul determinist şi cel nedeterminist nu sunt

echivalente.

M4.U4.4 Legătura dintre automatele push-down nedeterministe şi limbajele

independente de context

În cele ce urmează vom discuta numai despre automate push-down nedeterministe, pe

care le vom numi simplu automate push-down, iar atunci când ele nu sunt nedeterministe vom
preciza acest lucru.

Teorema 3.7.1
Un limbaj L este acceptat prin stivă vidă de către un automat push-down M1, (L=N(M1)
) dacă şi numai dacă el este acceptat prin stări finale de către un automat push-down
M2, ( L=N(M2) ).
▼Demonstraţie:

I. Fie L=T(M2), unde M2= (Q, Σ, Γ, δ, q 0 , Z0 , F) .

Construim M1= (Q  {q λ , q0 }, Σ, Γ  {X}, δ, q0 , X, ) , unde δ este definit după cum
urmează:
1) (q 0 , Z0 X)  δ(q0 , λ, X)
2) δ(q, a, Z)  δ(q, a, Z) , q  Q, a  Σ  λ, Z  Γ
3) Pentru toţi q  F, Z  Γ  {X}  q λ , λ δ(q, λ, Z)
4) Pentru toţi Z  Γ {X}  q λ , λ δ(q λ , λ, Z)

- 143 -
 Regula 1) îl face pe M1 să intre în configuraţia iniţială a lui M2, dar simbolul iniţial al
stivei este X. Regula 2) simulează pe M2 până când intră într-o stare finală. Regulile 3) şi 4)
golesc stiva când M2 intră într-o stare finală.
Se observă că regulile 2) pot goli stiva lui M2 şi pentru un cuvânt care nu este în T(M2),
iar acesta este motivul pentru care M1 are propriul său simbol iniţial al stivei, X.
Să demonstrăm echivalenţa celor două automate:

a) Fie w  T(M 2 ) . Atunci:

q 0 , w, Z0  ├ *M 2
(q,λ,γ) pentru q  Q .
Fie acum w intrarea lui M1;
conform regulei 1), rezultă că q 0 , w, Z 0  ├ M1 (q0,w,Z0X)
*
-
conform regulei 2), rezultă că q 0 , w, Z0 X  ├ M1 (q,λ,γX) (M1 simulează pe M2)
*
-
conform regulilor 3) şi 4), rezultă în final că q, λ, γX ├ M1 (qλ,λ,λ)
*
-
Aşadar  w  N(M1 ) .

b) Dacă w  N(M1 ) , atunci se vede că stiva este complet ştearsă numai dacă sunt aplicate
regulile 3) şi 4), deoarece regulile lui M2 nu pot şterge pe X. Aşadar, este necesar ca M2 să
intre într-o stare finală cu aceeaşi intrare ca M1, ca să poată fi aplicate reguli de tip 3 şi 4.

II. Reciproc, fie M1= (Q, Σ, Γ, δ, q 0 , Z0 , ) astfel încât L=N(M1).

Definim M2= (Q  {q0 , q f }, Σ, Γ  {X}, δ, q0 , X, {q f }) , unde δ este definit după cum
urmează:
1) (q 0 , Z0 X)  δ(q0 , λ, X)
2) q  Q, a  Σ  λ, Z  Γ  δ(q, a, Z)  δ(q, a, Z)
3) q  Q  (q f , λ)  δ(q, λ, X)
Regula 1) îl face pe M2 să intre în configuraţia iniţială a lui M1. Regula 2) simulează pe
M1 până îşi goleşte stiva la citirea intrării. Regula 3) îl determină pe M2 să intre într-o stare
finală dacă M1 şi-a golit stiva iar în stiva lui M2 este doar X.
Demonstraţia este similară cu I.
▲

Teorema 3.7.2
Dacă L este un limbaj independent de context, atunci există un automat push-down M
astfel încât L=N(M).
▼Demonstraţie:
Fie o gramatică independentă de context G=(VN,VT,S,P) în formă normală Greibach,
astfel încât L=L(G). Presupunem că λ  L(G) (demonstraţia se poate adapta şi pentru cazul
contrar).
Construim M= ({q 1}, VT , VN , δ, q1 , S, ) , unde δ(q1, a, A) conţine (q1 , γ) pentru
fiecare regulă A  aγ  P .
Pentru a arăta că L(G)=N(M), observăm că:

(xAβ  xaα β)  q1, a, Aβ ├ M q1 , λ, αβ 

G

- 144 -
 Prin inducţie asupra numărului de paşi dintr-o derivaţie rezultă că:
*
(xAβ  xyα pentru x, y  VT* , A  VN , α, β  VN* )  (q1 , y, Aβ )├ M (q1 , λ, α)
*

G
Atunci :
*
S  x  (q1 , x, S) ├ M (q1 , λ, λ) .
*

G
Se observă că M nu face λ-mutări.
▲

Teorema 3.7.3
Dacă L este acceptat prin stivă vidă de către un automat push-down M (L=N(M)),
atunci L este un limbaj independent de context.

▼Demonstraţie:
Fie M un automat push-down, M= (Q, Σ, Γ, δ, q 0 , Z0 , ) .
Definim gramatica G= (VN , Σ, S, P) , unde:
VN  {[q, A, p] q, p  Q, A  Γ}  {S}
iar P este definit după cum urmează:
S  [q 0 , Z0 , q] pentru q  Q
-pentru fiecare tranziţie (q1, B1B2 ...Bm )  δ(q, a, A) se generează un set de reguli în
gramatică, astfel:
q 2 ,..., q m , p  Q  [q, A, p]  a[q1 , B1 , q 2 ][q 2 , B2 , q 3 ]...[q m , Bm , p]  P
Dacă m=0, atunci q1=p, (p, λ)  δ(q, a, A) şi apare doar regula [q, A, p]  a  P .
Regulile au fost astfel definite încât să simuleze funcţionarea lui M cu intrarea x. În
particular, variabilele gramaticii G corespund simbolurilor memoriei push-down când M a
văzut din şirul de intrare exact atât cât a derivat gramatica G.
Se demonstrează că L(G)=N(M) prin inducţie relativ la numărul de paşi dintr-o
derivaţie a lui G, respectiv numărul de mişcări ale lui M, adică:
 * 
 [q, A, p]  x   (q, x, A) ├ *M (p, λ, λ) (3.7.3)
 G 
Luând apoi q=q0 şi A=Z0, rezultă următoarele:
 * 
[q 0 , Z 0 , p]  x   (q 0 , x, Z 0 ) ├ *M (p, λ, λ)
 G 

Dar prima regulă din G este S  [q 0 , Z0 , p] pentru p  Q , de unde rezultă:

 * 
 S  x   x  N(M)  .
 G 
Rămâne doar să demonstrăm echivalenţa (3.7.3):

 i 
I. Să arătăm prin inducţie în raport cu i că (q, x, A) ├ iM (p, λ, λ)  [q, A, p] x  ,
 G 
a. Dacă i=1,
definitia δ
(q, x, A) ├ (p, λ, λ)  (p, λ)  δ(q, x, A) 

- 145 -
 |x|  1 (deoarece x  VT sau x  λ )

definitia G
 * 
 [q, A, p]  x  P   [q, A, p]  x  .
 G 

b. Presupunem afirmaţia I adevărată pentru i şi o demonstrăm pentru i+1:

Fie
(q, x, A) ├ iM1 (p, λ, λ) şi

există a VT , y  VT astfel încât x=ay, y=y1…yt şi

*

i
(q, ay, A) ├ (q1 , y, B1...B t ) ├ (p, λ, λ) .

Dar (q k , yi , Bi ) ├ (q k1 , λ, λ) în cel mult i paşi şi qi+1=p, deci:

*

* * *
(q, ay, A) ├ (q1 , y1...y t , B1...B t ) ├ (q 2 , y 2 ...y t , B 2 ...B t ) ├ …├ (p, λ, λ) .

Atunci, folosind regulile gramaticii G şi ipoteza inducţiei, vom obţine:

[q, a, p]  a[q1 , B1 , q 2 ][q 2 , B2 , q 3 ]...[q k , Bk , p]

*
şi [q k , Bk , q k 1 ]  y k k  1, t

*
rezultă că [q, A, p]  ay1 y 2 ...y t .
G
 * 
II. Reciproc, se arată că [q, A, p] x   (q, x, A) ├ M (p, λ, λ) , prin inducţie relativ la
*

 G 
lungimea unei derivaţii (demonstraţia este similară celei de mai sus).

Astfel, demonstraţia este încheiată.

▲
Exemplul 1 Fie automatul push-down:
M= ({q 0 , q1 ),{0,1}, {X, Z0 }, δ, q 0 , Z0 , )
δ(q0 ,0, Z 0 )  {(q 0 , XZ 0 )} δ(q1 ,1, X)  {(q 1 , λ)} 

unde δ(q ,0, X)  {(q , XX)} 
0 0
δ(q1 , λ, X)  {(q 1 , λ)} 
δ(q ,1, X)  {(q , λ)} δ(q1 , λ, Z 0 )  {(q 1 , λ)}
 0 1 
Să se construiască gramatica echivalentă acestui automat.
▼ Conform demonstraţiei teoremei 3.7.3, construim G=(VN,  ,S,P) care
generează chiar limbajul N(M) astfel:
VN  {S,[q 0 , X, q 0 ], [q 0 , X, q1 ], [q 1 , X, q 0 ], [q 1 , X, q1 ],
[q 0 , Z 0 , q 0 ], [q 0 , Z 0 , q1 ], [q 1 , Z 0 , q 0 ], [q 1 , Z 0 , q1 ]}

- 146 -
 S  [q 0 , Z 0 , q 0 ]
S  [q , Z , q ]
 0 0 1

[q 0 , Z 0 , q 0 ]  0[q 0 , X, q 0 ][q 0 , Z 0 , q 0 ]


[q 0 , X 0 , q 0 ]  0[q 0 , X, q 1 ][q 1 , Z 0 , q 0 ]
[q 0 , X, q 0 ]  0[q 0 , X, q 0 ][q 0 , X, q 0 ]

[q 0 , X, q 0 ]  0[q 0 , X, q 1 ][q 1 , X, q 0 ]

[q , Z , q ]  0[q 0 , X, q 0 ][q 0 , Z 0 , q 1 ]
P: 0 0 1
[q 0 , Z 0 , q 1 ]  0[q 0 , X, q 1 ][q 1 , Z 0 , q 1 ]
[q 0 , X, q 1 ]  0[q 0 , X, q 0 ][q 0 , X, q 1 ]

[q 0 , X, q 1 ]  0[q 0 , X, q 1 ][q 1 , X, q 1 ]
[q , X, q ]  1
 0 1

[q 1 , X, q 1 ]  1
[q , X, q ]  λ
 1 1


[q 1 , Z 0 , q 1 ]  λ
În final, putem urmări şi elimina regulile inutile şi, de asemenea,
simbolurile neterminale neutilizabile, obţinând următoarea variantă redusă:
VN  {S, [q 0 , X, q1 ], [q1 , X, q1 ], [q 0 , Z0 , q1 ], [q1 , Z0 , q1 ]}
S  [q 0 , Z 0 , q1 ]
[q , Z , q ]  0[q , X, q ][q , Z , q ]
 0 0 1 0 1 1 0 1
[q 0 , X, q1 ]  0[q 0 , X, q1 ][q 1 , X, q1 ]

P : [q 0 , X, q1 ]  1
[q , X, q ]  1
 1 1
[q1 , X, q1 ]  λ
[q , Z , q ]  λ
 1 0 1
▲

Observaţia 3.7.1 Din teoremele 3.7.1, 3.7.2 şi 3.7.3 rezultă că următoarele afirmaţii sunt
echivalente:
i) L este un limbaj independent de context;
ii) L=N(M1) pentru un automat push-down M1 nedeterminist;
iii) L=T(M2) pentru un automat push-down M2 nedeterminist.

1. Fie automatul push-down:

P = ({s0, s1, s2}, {a, b}, {z, a, b}, , s0, z, {s2})
cu funcţia  defintă astfel:
 (s0, a, z) = {(s0, az)}
 (s0, b, z) = {(s0, bz)}
 (s0, a, a) = {(s0, aa), (s1, )}
 (s0, a, b) = {(s0, ab)}
 (s0, b, a) = {(s0, ba)}
 (s0, b, b) = {(s0, bb), (s1, )}
 (s1, a, a) = {(s1, )}
- 147 -
  (s1, b, b) = {(s1, )}
 (s1, , z) = {(s2, )}
a. Să se arate că L(P) = {u ~u | u{a, b}+}, unde ~
u reprezintă
oglinditul lui u.
b. Ce fel de automat push-down este P?
2. Să se construiască automate push-down pentru fiecare dintre mulţimile
următoare:
a. {w | w  {0,1}* N0(w) = N1(w)}, unde N0(w) reprezintă numărul
de apariţii ale simbolului 0 în w;

b. Mulţimea cuvintelor generate de gramatica:

G = ({S,A}, {a,b}, S, { S → aAA, A → bBS, A → aS, A → a})
3. Să considerăm gramatica care generează expresiile artimetice cu
operatorii + şi *, parantezele (, ), şi operandul id, (unde operatorul este
cuprins între doi operanzi), dată de regulile gramaticale:
{ E → E + E, E → E * E, E → (E), E → id }
Gramatica cu regulile:
{ P→ + PP, P → * PP, P → id }
generează aceleaşi expresii aritmetice dar în forma poloneză prefixată,
scriere care permite eliminarea parantezelor. Să considerăm următoarea
expresie aritmetică:
id * (id + id) + id
În forma poloneză prefixată expresia devine:
+ * id + id id id
Să se construiască un program care să traducă o expresie de forma de mai
sus, e1, în forma poloneză prefixată, e2, utlizând următoarea tehnică:
 Se simuleză funcţionarea unui a.p.d. care analizează expresia
aritmetică e1 şi se construieşte un arbore de derivaţie pentru e1;
 Pentru fiecare vârf al arborelui de derivaţie, determină
acţiunea care defineşte traducerea în forma e2.

Să ne reamintim...
Un automat push-down nedeterminist, M, este asemănător cu un automat
finit dar conţine în plus şi o memorie de tip stivă.
Limbajul acceptat prin stări finale de către automatul M este
L(M)  {w w  Σ* , (q 0 , w, Z0 ) ├ *M p, λ, γ , γ  Γ* , p  F} .
Limbajul acceptat prin stivă vidă de către automatul M este
N(M)  {w w  Σ , (q 0 , w, Z0 ) ├
* *
M
p, λ, λ , p  Q} .

Test de evaluare a cunoştinţelor

I. Întrebări.
1. Să se definească automatele push-down deterministe şi
nedeterministe.
II. Exerciţii propuse.
- 148 -
 1. Să se construiască o gramatică IDC şi un automat push-down care să
recunoască limbajul L = { w {a, b}* | w conţine un număr egal de
a şi b}
2. Fie gramatica G=({S,A,B},{a,b}, S, {SaB, S bA, Aa, AaS,
AbAA, Bb, BbS, BaBB}).
a. Găsiţi o derivare stângă şi un arbore de derivaţie pentru
cuvântul w= aaabbabbbba
b. Construiţi un automat push-down care acceptă limbajul L(G).
3. Fie automatul push-down:
P = ({s0, s1, s2, s3}, {a, b, c}, {z, a}, , s0, z, {s3})
cu  dat prin:
 (s0, a, z) = {(s1, aaz)}
 (s1, a, a) = {(s1, aaa)}
 (s1, b, a) = {(s2, )}
 (s1, c, a) = {(s2, )}
 (s2, b, a) = {(s2, )}
 (s2, c, a) = {(s2, )}
 (s2, , z) = {(s3, )}
a. Să se arate că L(P) = {anw| w{b, c}+, |w| = 2n, n ≥ 1}.
b. Ce fel de automat push-down este P?

M4.U4.5 Rezumat
Unitatea de învăţare prezintă un alt tip de automat , automatul push-down cu
varianta deterministă şi cu cea nedeterministă şi legatura dintre automatele
push-down nedeterministe şi gramaticile de tip 2.
Spre deosebire de automatele finite, la automatele push-down cele două
variante nu sunt echivalente, automatele push-down deterministe
recunoscând o subclasă proprie a limbajelor Independente de context numită
clasa limbajelor deterministe. Aceasta clasă a limbajelor deterministe este
utilizată în construcţia compilatoarelr moderne şi anume pentru construcţia
analizoarelor sintactice.

- 149 -
Unitatea de învăţare M4.U4. Proprietăţi de închidere pentru
familia limbajelor de tip 2

Cuprins
M4.U5.1. Introducere ........................................................................................... 150
M4.U5.2. Obiectivele unităţii de învăţare ............................................................ 150
M4.U5.3. Proprietăţi de închidere pentru limbaje I.D.C. ................................... 150
M4.U5.4. Rezumat ............................................................................................... 159

M4.U5.1. Introducere
Vom considera întâi anumite operaţii cu limbaje care păstrează limbajele
independente de context. Apoi vom prezenta operaţii la care familia limbajelor
independente de context nu este închisă.
Aceste operaţii se pot folosi atât pentru a demonstra că un limbaj este I.D.C. cât
şi pentru a demonstra că un limbaj nu este I.D.C.
.

M4.U5.2. Obiectivele unităţii de învăţare

La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să:
 înţeleagă şi să explice proprietăţile de închidere ale familiei limbajelor
I.D.C.;
 construiască propria gramatică pentru un anumit limbaj, care poate fi
descompus în mai multe limbaje, folosind proprietăţile de închidere;
 construiască propriul automat push-down pentru un anumit limbaj, care
poate fi descompus în mai multe limbaje, folosind proprietăţile de
închidere;
 programeze construcţiile anterioare într-un limbaj de programare oarecare.

Durata medie de parcurgere a unităţii de învăţare este de 3-4 ore.

M4.U5.3 Proprietăţi de închidere pentru limbaje I.D.C.

Teorema 3.8.1
Limbajele independente de context sunt închise la reuniune, concatenare şi produs
Kleene.
▼Demonstraţie:

- 150 -
 Fie L1 şi L2 generate de G1  (V1, T1, S1, P1 ) şi G 2  (V2 , T2 , S2 , P2 ) . Presupunem că
V1  V2=  . Atunci putem realiza următoarele construcţii de gramatici I.D.C:

a) Limbajul L1  L 2 este generat de G 3  (V1  V2  {S 3}, T1  T2 , S3 , P3 ) , unde

P3  P1  P2  {S 3  S1 , S3  S2 } .
Să demonstrăm că L1  L 2  L(G 3 ) :
 Fie w  L1  L 2 ; înseamnă că w aparţine cel puţin unuia din cele două limbaje:
i {1,2} : w  Li , altfel spus i {1,2} : w  L(G i ) . Există deci o derivare a lui w în una
din cele două gramatici date, Gi, pornind de la simbolul iniţial al respectivei gramatici:

Si  w . Deoarece toate regulile din gramatica Gi sunt şi reguli ale gramaticii construite
Gi

G3, înseamnă că aceeaşi derivare are loc şi în gramatica G3. În plus, putem obţine simbolul
Si printr-o derivare într-un pas pornind de la S3, şi anume folosind una din cele două reguli
nou adăugate la P3, obţinând următoarea derivaţie în G3:


i {1,2} : S3  Si  w , deci w  L(G 3 ) .
G3 G3

Rezultă că L1  L 2  L(G 3 ) .

 Fie w  L(G 3 ) ; înseamnă că w poate fi generat cu regulile P3, pornind de la S3: S3  w .
G3
 Deoarece singurele S3-reguli sunt cele două redenumiri {S 3  S1 , S3  S2 } , rezultă că
primul pas al derivaţiei amintite nu poate fi decât rezultatul aplicării uneia din aceste două
reguli:
 
i {1,2} : S3  Si  w , deci Si  w .
G3 G3 G3
Putem observa faptul că, în afară de primul pas al acestei derivări, toate regulile
folosite în obţinerea lui w pornind de la S3 sunt chiar reguli din Pi, i  {1,2} , în funcţie de
simbolul Si obţinut în primul pas. Deoarece V1  V2=  , rezultă că

Si  w ,
Gi
deci w  L(G i ) =Li.
S-a arătat astfel că w  L1 sau w  L 2 , adică w  L1  L 2 .
Rezultă că L1  L 2  L(G 3 ) .
Ţinând cont de cele două implicaţii rezultă că limbajul L1  L 2 este generat de
gramatica G3.
Următoarele construcţii se demonstrează în mod asemănător, constituind un bun
exerciţiu:

b) Limbajul L1L 2 este generat de G 4  (V1  V2  {S 4 }, T1  T2 , S4 , P4 ) , unde

P4  P1  P2  {S 4  S1S2 } .

- 151 -
c) Limbajul L*1 este generat de G 5  (V1  {S 5 }, T1 , S5 , P5 ) , unde
P5  P1  {S 5  S5S1 , S5  λ} .
▲

Teorema 3.8.2
Familia limbajelor independente de context este închisă la substituţie.

▼Demonstraţie:
Fie L un limbaj I.D.C., L  Σ * şi pentru fiecare a  Σ fie La un limbaj I.D.C.
Fie o gramatică G care generează limbajul iniţial, L=L(G). De asemenea, pentru
fiecare simbol a  Σ considerăm câte o gramatică astfel încât La=L(Ga).
Presupunem că variabilele lui G şi ale lui Ga sunt distincte, oricare ar fi a  Σ .
Construim gramatica G  I.D.C. în felul următor:
 Variabilele lui G  sunt variabilele lui G şi cele ale lui Ga, pentru a  Σ ;
 Terminalele lui G  sunt terminalele lui Ga;
 Simbolul iniţial al lui G  este simbolul iniţial al lui G;
 Regulile lui G  sunt cele ale lui Ga, pentru a  Σ , şi regulile lui G în care fiecare a  Σ se
înlocuieşte cu Sa (simbolul iniţial al Ga).
▲

Exemplul 1 Fie L limbajul cuvintelor cu număr egal de a şi b. Să urmărim

aplicarea celor demonstrate în teorema anterioară.

▼
Avem gramatica generativă G  ({S}, {a, b}, S, P) , unde mulţimea
regulilor este P  {S  aSbS, S  bSaS, S  λ} . Se poate verifica faptul că
L=L(G). Să considerăm limbajele de substituţie:
 L a  {0 n1n | n  1} , generat de regulile P(Ga)= {S a  0Sa 1, Sa  01} ;
 L  {w w ~ | w {0,2}*} , limbaj generat de mulţimea de reguli
b

P(Gb)= {S b  0Sb 0, Sb  2Sb 2, Sb  λ} .

Atunci, conform construcţiei efectuate în demonstraţia Teoremei 3.8.2,

gramatica rezultată este G = ({S, Sa , Sb },{0,1,2}, S, P) , cu mulţimea de reguli:
S  Sa SSb S
S  S SS S
 b a

S  λ

Sa  0S a 1
P : 
Sa  01
S b  0S b 0

S b  2S b 2
S  λ
 b

- 152 -
 Să generăm un cuvânt la întâmplare cu aceste reguli:
S  Sa SSb S  01SS b S  01S b S  012S b 2S  0120S b 02S 
 012002S  012002
▲
Observaţia 3.8.1 Teorema 3.8.1 se poate obţine folosind Teorema 3.8.2 şi ţinând cont că
a, b  Σ avem:
 {a, b} este I.D.C.
 {a  b} este I.D.C.
 a  este I.D.C.
Dacă acum f(a)=La şi f(b)=Lb, atunci, datorită proprietăţii de închidere la substituţie,
rezultă că:
 L a  L b este I.D.C.
 L a  L b este I.D.C.
 La este I.D.C.
Pentru că homomorfismul este un caz special de substituţie, în care card(La)=1,
obţinem şi următorul corolar.

Corolar 3.8.1 Clasa limbajelor I.D.C. este închisă la homomorfism.

Teorema 3.8.3
Clasa limbajelor independente de context este închisă la homomorfismul invers.

▼Demonstraţie:
Fie h : Σ  Δ un homomorfism şi L un limbaj I.D.C.; atunci există un automat push-
down M  (Q, Δ, Γ, δ, q 0 , Z 0 , F) astfel încât L=T(M).
Construim un automat push-down M  care să accepte h 1 (L) , astfel:

Intrarea lui M'

Controlul
lui M' h
Buffer Stiva lui
Controlul
lui M M şi M'

Figura 3.8.1
Cu intrarea a pentru automatul M', acesta generează h(a) şi simulează execuţia lui M
cu această intrare h(a). Dacă M' ar fi un automat cu număr finit de stări, atunci M' şi-ar
schimba numai stările. În cazul automatului push-down, M' poate şi să pună o mulţime de
simboluri pe stivă şi, în plus, fiind nedeterminist are o mulţime de posibilităţi de mişcare.
De aceea, dotăm M' cu un buffer (o zonă tampon) în care el poate să memoreze h(a).
Atunci M' poate să simuleze orice λ-mutare a lui M, dacă doreşte, şi să consume simbolurile

- 153 -
lui h(a) câte unul la fiecare moment, la fel cum face M. Pentru ca buffer-ul să fie o parte a
controlului finit al lui M', el nu poate fi oricât de lung. Se poate realiza asta permiţându-i lui
M' să citească un simbol de intrare numai când buffer-ul este gol. Astfel, în buffer este păstrat
în fiecare moment un sufix al lui h(a), pentru un anume a preluat de pe banda de intrare a lui
M'.
Automatul push-down M' acceptă cuvântul de intrare w dacă buffer-ul este vid şi M
este într-o stare finală. În acest fel, M a acceptat h(a) pentru fiecare simbol de intrare a, deci a
acceptat h(w).
Astfel, L(M')= {w h(w)  L(M)} , adică:
L(M')= h 1 (L(M))
Construcţia formală este dată în continuare.

M  (Q, Σ, Γ, δ,[q 0 , λ], Z0 , F  λ) ,

unde:
Q’ = {[q,x] | q  Q, iar x este un suffix al lui h(a),a }

Funcţia de tranziţie δ :

1) ([p, x], γ)  δ([q, x], λ, Y) pentru fiecare (p, γ)  δ(q, λ, Y) .

Astfel, M' simulează λ-mutările lui M, indiferent de conţinutul din buffer.
2) ([p, x], γ)  δ([q, ax], λ, Y) dacă (p, γ)  δ(q, a, Y) .
Astfel, M' simulează mutările lui M pe intrarea a din Σ, eliberând a din capul buffer-ului.
3) ([q, h(a)], Y)  δ([q, λ], a, Y) pentru toţi a  Σ şi Y  Γ .
În acest mod, M' încarcă în buffer h(a), citind a de pe intrarea M', în timp ce starea şi stiva
lui M rămân neschimbate.

Să demonstrăm că L(M')= h 1 (L(M)) .

a) Mai întâi, să observăm că printr-o aplicare a regulii (3) urmată de o aplicare a

regulilor (1) şi (2),

dacă (q, h(a), α) ├ M (p, λ, β) ,


atunci ([q, λ], a, α) ├ M ([q, h(a)], λ, α) ├ M ([p, λ], λ, β) .


Astfel, dacă M acceptă h(a), adică dacă (q 0 , h(w), Z0 ) ├ M (p, λ, β) pentru p  F şi
β  Γ , atunci

([q 0 , λ], w, Z0 ) ├ M ([p, λ], λ, β) ,
astfel încât M' acceptă w.

Deci L(M')  h 1 (L(M)) .

b) Reciproc, să presupunem că M' acceptă intrarea w=a1a2…an. Atunci, pentru că regula (3)
poate fi aplicată numai cu buffer-ul vid (precum arată a doua componentă a stării lui M),
şirul de mişcări ale lui M' ce conduc la acceptare poate fi scris ca:
c)

- 154 -
 
([q 0 , λ], a1a 2 ...a n , Z0 ) ├ M
  
├ M ([p1 , λ], a1a 2 ...a n , α1 ) ├ M ([p1 , h(a 1 )], a 2 ...a n , α1 ) ├ M
  
├ M ([p 2 , λ], a 2 ...a n , α 2 ) ├ M ([p 2 , h(a 2 )], a 3 ...a n , α 2 ) ├ M
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .
  
├ M ([p n , λ], a n , α n ) ├ M ([p n , h(a n )], λ, α n ) ├ M
├ M ([p n 1 , λ], λ, α n 1 ) , unde pn+1 F.


Tranziţia din starea [pi , λ] în [p i , h(a i )] se face prin regula (3) iar celelalte tranziţii
prin regulile (1) şi (2).
Astfel,

(p1 , α1 )  δ(q 0 , λ, Z0 )
şi i : (p i 1 , αi 1 )  δ(pi , h(a i ), αi )

deci obţinem o recunoaştere şi din partea lui M:

 
(q 0 , h(a 1a 2 ...a n ), Z 0 ) ├ M ([p1 , λ], a1a 2 ...a n , α1 ) ├ M
   
├ M ([p 2 , λ], a 2 ...a n , α 2 ) ├ M …├ M ([p n , λ], a n , α n ) ├ M
├ M ([p n 1 , λ], λ, α n 1 ) , unde pn+1 F.


Există câteva proprietăţi ale mulţimilor regulate care nu se păstrează la mulţimile

I.D.C., şi anume proprietăţile de închidere la intersecţie şi complementare.

Teorema 3.8.4
Clasa limbajelor I.D.C. nu este închisă relativ la intersecţie.

▼Demonstraţie:
Să presupunem, prin absurd, că intersecţia oricăror limbaje I.D.C. este tot un limbaj
I.D.C. Să construim un contraexemplu:
Am demonstrat că limbajul L  {a i b i c i i  1} nu este independent de context (v.
Observaţia 3.4.1). Considerăm acum două limbaje care sunt I.D.C.:


L1  {a b c i  1, j  1}
i i j

L 2  {a b c i  1, j  1}
i j j


Pentru aceste limbaje este uşor să construim câte un automat push-down sau sau câte o
gramatică I.D.C.; spre exemplu, o gramatică pentru generarea limbajului L2 ar putea avea setul
de reguli:
{S  AB, A  aA, A  a, B  bBc, B  bc} .
Dar L  L1  L2 şi L nu este I.D.C., ceea ce contrazice presupunerea făcută.
▲

Corolar 3.8.2

- 155 -
 Clasa limbajelor I.D.C. nu este închisă relativ la complementare.

▼Demonstraţie:
Ştim că clasa limbajelor I.D.C. este închisă la reuniune. Presupunând că ar fi închisă şi
la operaţia de complementare, şi ţinând cont de relaţiile lui de Morgan privind
complementarea reuniunii ( C(A  B)=C(A)  C(B) ), am obţine concluzia că are loc
închiderea şi la intersecţie, ceea ce contrazice Teorema 3.8.4.
▲

Teorema 3.8.5
Dacă L este un limbaj I.D.C. iar R este o mulţime regulată, atunci L  R este un limbaj
I.D.C.

▼Demonstraţie:
Fie L=T(M), M fiind un automat push-down:
M = (QM, , , ,q0, Z0, FM)
Fie şi R=T(A), unde A este un automat finit nedeterminist:
A  (Q A , Σ, δ A , p 0 , FA )
Construim un automat push-down M' pentru limbajul L  R , într-un mod care să
simuleze funcţionarea în paralel a lui M şi A:

Intrarea lui A, M şi M'

Controlul
Controlul Controlul Stiva lui
lui M'
lui A lui M M şi M'

…
Figura 3.8.2

M' simulează mişcările lui M pe intrarea λ fără a schimba starea lui A. Când M face o mişcare
pe simbolul de intrare a, M' simulează această mişcare şi de asemenea simulează schimbarea
stării lui A pentru simbolul a. Automatul M' acceptă o intrare dacă şi numai dacă atât A cât şi
M o acceptă.
Construcţia formală a lui M' este următoarea:
M  (Q A  Q M , Σ, Γ, δ,[p 0 , q 0 ], Z0 , FA  FM ) ,
unde δ este definit astfel:
δ A (p, a)  p
([p, q], γ)  δ([p, q], a, X) atunci când 
(q, γ)  δ M (q, a, X)
Desigur, dacă a =  atunci p = p’.

Să demonstrăm acum faptul că L  R =T(M').

- 156 -
a) Se demonstrează uşor prin inducţie relativ la i că:
i
dacă ([p 0 , q 0 ], w, Z0 ) ├ M ([p, q], λ, γ) , atunci
i
(q 0 , w, Z 0 ) ├ M (q, λ, γ)
i
şi (p 0 , w) ├ A (p, λ)
 pentru i=0 rezultatul e trivial, deoarece luăm p=p0, q=q0, γ=Z0 şi w=λ.
 presupunem afirmaţia adevărată pentru i-1 şi fie
i -1
([p 0 , q 0 ], xa, Z0 ) ├ M ([p' , q' ], a, β) ├ M ([p, q], λ, γ) ,
unde w=xa şi a sau a=λ.
Conform ipotezei de inducţie, rezultă că:
δ A (p 0 , x)  p

(q 0 , x, Z 0 ) ├ M (q , λ, β)
În plus, conform definiţiei,
δ A (p, a)  p
şi (q , a, β) ├ M (q, λ, γ)

Utilizând toate acestea, obţinem:

δ A (p 0 , xa)  p

(q 0 , xa, Z 0 ) ├ M (q, λ, γ)
xa  T(A)
sau, altfel scris,  , ceea ce trebuia demonstrat.
xa  T(M)

b) Reciproc, se procedează într-o manieră similară, pentru a arăta că:

(q 0 , w, Z 0 ) ├ M (q, λ, γ)
i

dacă i
şi (p 0 , w) ├ A (p, λ)

atunci ([p 0 , q 0 ], w, Z0 ) ├ M ([p, q], λ, γ) ,
▲

Teorema 3.8.6
Clasa limbajelor independente de context este închisă în raport cu operaţia de
oglindire.

▼Demonstraţie:
Fie G o gramatică independentă de context de forma:
G = (VN, VT, S, P)
şi L = L(G).
Construim o nouă gramatică G’ = (VN, VT, S, P”), în care fiecare regulă din mulţimea
regulilor, P, este înlocuită cu o regulă similară în care membrul drept este oglinditul
membrului drept al regulei corespunzătoare din P:
P’ = {A → ~ u | A → u  P}

- 157 -
 Se observă că regulile din P’ sunt tot independente de context. Este uşor de demonstrat
că:
~
L(G’) = L
▲

Exemplul 2 Fie limbajul L  {ww w {a, b}} . Să se exemplifice proprietăţile

de închidere.

▼
Limbajul L este format din cuvintele ale căror jumătate stângă este
identică cu jumătatea dreaptă. Presupunem că acest limbaj ar fi I.D.C.
Din Teorema 3.8.5 rezultă că limbajul L1  L  a  b  a  b  ar fi şi el
I.D.C.; dar L1  {a i b ja i b j i  1, j  1} nu este de acest tip, fapt ce se poate vedea
cu ajutorul teoremei de pompare:
Fie p,q  N . Alegem z = a q b q a q b q = uvwxy, unde |v| + |x| > 0, |vwx| 
q. Posibilităţile de alegere ale subcuvântului vwx sunt multiple (aibj cu i+j  q , bi
cu i  q, bj-iai cu i  j  q), ele însă nu permit crearea de cuvinte uv i wx i y care să
fie tot din L1 (proprietatea egalităţii jumătăţilor nu se poate păstra prin pompare).
Din contradicţia obţinută rezultă că limbajul L considerat iniţial nu este
I.D.C.
Să mai observăm şi faptul că se poate demonstra că L1 nu este I.D.C. şi
fără a folosi teorema de pompare, reducând acest limbaj la limbajul
L 2  {a i b jc i d j i  1, j  1} .
Fie h(a)=h(c)=a şi h(b)=h(d)=b. Atunci h 1 (L1 ) este format din toate
cuvintele de forma x1x2x3x4, unde x1 şi x3 au aceeaşi lungime în {a, c} , iar x2 şi
x4 au aceeaşi lungime în {b, d} .
Atunci h 1 (L1 )  a *b*c*d*  L 2 .
Dacă L1 ar fi I.D.C., atunci (din Teoremele 3.8.3 şi 3.8.5) rezultă că L2 ar
fi şi el I.D.C., ceea ce ştim că este fals.
Astfel s-a arătat, din nou, faptul că L1 nu este I.D.C.
▲
Să ne reamintim...
Familia limbajelor independente de context este închisă la:
 reuniune,
 concatenare,
 produs Kleene,
 oglindire,
 substituţie,
 homomorfism,
 homomorfismul invers,
 intersecţia cu mulţimi regulate..
Familia limbajelor independente de context nu este închisă la:
 intersecţie,

- 158 -
  complementara relative la un alphabet.

Teste de evaluare/autoevaluare

I. Intrebări.
1. Să se enunţe şi să se demonstreze 4 proprietăţi de închidere
pentru limbajele de tip 2.
II. Exerciţii.
[Link] consideră limbajul L = {an bn | n ≥ 1}  {an b2n| n ≥ 1}. Să se
arate că L este un limbaj independent de context (se construieşte un
automat push-down nedeterminist sau o gramatică IDC folosind
proprietatea de închidere a limbajelor IDC la reuniune.)

M4.U5.4. Rezumat. Această unitate de învăţare prezintă proprietăţi de închidere ale

familiei limbajelor de tip2, adică independente de context. Datorită faptului că
limbajele independente de context pot fi generate de gramatici de tip 2 sau recunoscute
de automatele push-down nedeterministe, în demonstrarea acestor proprietăţi se va
folosi una sau alte dintre reprezentăti.
Spre deosebire de familia limbajelor de tip 3, limbajele regulate, familie limbajeor
independente de context nu este închisă la o serie de operaţii cum ar fi intersecţia şi
complementara faţa de un alfabet.
Proprităţile de închidere pot fi folosite în demonstrarea anumitor rezultate. În plus
construcţiile folosite în demonstrarea acestor proprietăţi se pot folosi în construirea de
gramatici, respective automate push-down pentru anumite limbaje particulare.

- 159 -
Soluţiile testelor de autoevaluare pentru modulul 4
M4U1

I. Întrebări.
1. Ce este un arbore de derivare într-o gramatică IDC G?
Răspuns: vezi definiţia 3.1.2

II. Exerciţii propuse.

2. Se consideră arborele din figura următoare. Să se construiască o gramatică IDC, G,
astfel încât arborele din imagine să fie arbore de derivaţie în G.

a S S b
S
 a

Rezolvare:
O gramatică pentru care arborele de mai sus să fie arbore de derivaţie este:
G=({S},{a,b},S,{SaSSb, Sa, S})

M4U2

I. Întrebări.
1. Cum arată o gramatică IDC în formă normală Chomsky? Descrieţi algoritmul de
construcţie a unei gramatici în formă normală Chomsky echivalentă cu o gramatică
IDC oarecare.

II. Exerciţii propuse.

1. Eliminaţi neterminalele inutilizabile din gramatica:
G=({S, A, B},{a, b}, S, P) cu regulile:
SaS
SAB
SabB
AbA
BAA
Bb
Rezolvare: Utilizăm algoritmul de eliminare a simbolurilor inutilizabile:
Pas1: V N1  
Pas2:
V N2  V N1  {B} ={B}
V N3  V N2  {S}  {S , B}

- 160 -
 V N4  V N3 ={S,B}
Rezultă gramatica:
G’=({S,B},{a,b},S,{SaS, SabB, Bb})

2. Fie gramatica G = ({S, A, B},{a, b}, S, P) cu regulile:

S  bA
S  aB
A  bAA
A  aS
Aa
B  aBB
B  bS
Bb
Să se găsească o gramatică IDC, G‘, în formă normală Chomsky, echivalentă cu G.

Rezolvare:
Observăm că gramatica nu conţine redenumiri. Se consideră neterminalele C şi D
pentru simbolurile a şi b. Regulile gramaticii devin:

S  DA Aa Ca
S  CB B  CBB Db
A  DAA B  DS
A  CS Bb

Se observă că regulile care nu sunt în formă normal Chomsky sunt A  DAA şi

BCBB.
Înlocuim regula A DAA cu regulile:
A DE
E  AA

Înlocuim regula BCBB cu regulile:

BCF
FBB

Obţinem astfel gramatica în formă normală Chomsky G’:

G‘=({S,A,B,C,D,E,F},{a,b},S,P‘)
P’:
SDA ADE ACS
SCB EAA Aa
BCF BDS Ca
FBB Bb Db

3. Fie gramatica G = ({x1, x2, x3},{a, b}, x1, P) cu regulile:

(a) x1  x2 x3
(b) x2  x3 x1 | b
(c) x3  x1 x2 | a

- 161 -
Să se determine o gramatică echivalentă cu G care este în formă normală Greibach.

Rezolvare:
Neterminalele sunt numerotate şi se consideră ordinea dată de această numerotare. Singura
regulă de forma xi  xj cu j<i este x3x1x2. Se elimină această regulă, prin înlocuirea cu:

x3x2x3x2.

Aceasta este tot de forma xi  xj cu j<i, deci se înlocuieşte cu:

x3x3x1x3x2.
x3bx3x2.
Se elimină recursia stângă din producţia x3x3 x1x3x2 prin adăugarea neterminalului nou y3 şi
înlocuirea producţiei cu:
x3bx3x2y3
x3ay3
şi adăugarea producţiilor:
y3x1x3x2y3
y3x1x3x2

Se obţin deci regulile:

x3bx3x2y3
x3ay3
x3bx3x2
x3a

x2  x3 x1
x2  b

x1  x2 x3

y3x1x3x2y3
y3x1x3x2

x2-regulile se înlocuiesc cu:

x2  bx3x2y3x1
x2  ay3x1
x2  bx3x2x1
x2  ax1
x2  b

x1-regulile se înlocuiesc cu:

x1  bx3x2y3x1x3
x1  ay3x1x3
x1  bx3x2x1x3
x1  ax1x3
x1  bx3

- 162 -
Se aduc la forma normală Greibach y3-regulile:

y3 bx3x2y3x1x3x3x2y3
y3 ay3x1x3x3x2y3
y3 bx3x2x1x3x3x2y3
y3 ax1x3x3x2y3
y3 bx3x3x2y3

y3 bx3x2y3x1x3x3x2
y3 ay3x1x3x3x2
y3 bx3x2x1x3x3x2
y3 ax1x3x3x2
y3 bx3x3x2

În final gramatica obţinută are regulile:

x1  bx3x2y3x1x3 x3ay3
x1  ay3x1x3 x3bx3x2
x1  bx3x2x1x3 x3a
x1  ax1x3
y3 bx3x2y3x1x3x3x2y3
x1  bx3 y3 ay3x1x3x3x2y3
y3 bx3x2x1x3x3x2y3
y3 ax1x3x3x2y3
x2  bx3x2y3x1 y3 bx3x3x2y3
x2  ay3x1 y3 bx3x2y3x1x3x3x2
x2  bx3x2x1 y3 ay3x1x3x3x2
x2  ax1 y3 bx3x2x1x3x3x2
x2  b y3 ax1x3x3x2
y3 bx3x3x2
x3bx3x2y3

M4U3
I. Întrebări.
1. Să se definească automatele push-down deterministe şi nedeterministe.
Răspuns: vezi definiţia 3.6.1
II. Exerciţii propuse.
1. Să se construiască o gramatică IDC şi un automat push-down care să recunoască
limbajul L = { w {a, b}* | w conţine un număr egal de a şi b}
Rezolvare:

Gramatica: G=({S},{a,b},S,{SSS, SaSb, SbSa, S})

Demonstrăm faptul că L(G)=L prin dublă incluziune:

L(G)  L: fie wL(G), deci w se obţine printr-un număr finit de aplicări de producţii
ale lui G, pornind de la S. Folosim inducţia după lungimea derivării n.
Pentru n=1: avem o singură producţie S, iar L.
- 163 -
 Pentru n=2 avem posibilităţile
SaSbab  L
Sau
SbSaba  L
Presupunem că pentru orice derivaţie de lungime n, cuvântul w obţinut este din L, deci
Na(w)=Nb(w).

n+1:
Se consideră un cuvânt de wL(G) obţinut printr-o derivaţie de lungime n+1.
Avem următoarele posibilităţi:
n k l
i. SSS  w1w2L(G), unde S  w1 şi S  w2 cu k+l=n şi k>0, l>0. Din ipoteza
inducţiei rezultă w1L(G) şi w2L(G), deci Na(w1)=Nb(w1) şi Na(w2)=Nb(w2) 
Na(w1w2)=Nb(w1 w2)  Na(w)=Nb(w)  wL
n n
ii. SaSb  aw1bL(G), cu S  w1. Din pasul de inducţie rezultă w1L, deci
Na(w1)=Nb(w1). Dar Na(w)=Na(w1)+1 = Nb(w1)+1=Nb(w)  wL
n n
iii. SbSa  bw1aL(G), cu S  w1. Din pasul de inducţie rezultă w1L, deci
Na(w1)=Nb(w1). Dar Na(w)=Na(w1)+1 = Nb(w1)+1=Nb(w)  wL

Astfel s-a demonstrat L(G)  L.

L  L(G). Fie wL, deci Na(w)=Nb(w). Vom demonstra prin inducţie după lungimea
lui w, că wL(G). Din relaţia Na(w)=Nb(w) rezulă faptul că lungimea n lui w este un
număr par.

n=0: atunci w=, dar L şi L(G).

n=2: atunci w=ab sau w=ba.
Pentru w=ab, SaSbab, deci abL(G);
Pentru w=ba, SbSaba, deci baL(G).
Presupunem că pentru orice cuvânt wL, de lungime pară cel mult n, wL(G).

n+2: Fie wL de lungime n+2, atunci avem următoarele posibilităţi:

i. w=aw1b, cu Na(w1)=Nb(w1) şi |w1|=n. Din presupunerea inductivă rezultă
*
w1L(G). Rezultă S  w1.
*
Cum w=aw1b putem deriva SaSb  w, deci wL(G).
ii. w=ax1x2...xn-1a cu xi  {a,b}. Se consideră 1  i primul indice pentru care
Na(ax1x2...xi)=Nb(ax1x2...xi). Indicele i  n-2, altfel s-ar contrazice
Na(w)=Nb(w). Putem astfel partiţiona cuvântul w=w1w2 cu w1=a ax1x2...xi şi
w3= xi+1x2...xn-1a. Din Na(w)=Nb(w) şi Na(w1)=Nb(w1) rezultă Na(w2)=Nb(w2) şi
* *
|w1|<n, |w2|<n. Din inducţie rezultă S  w1 şi S  w2. Putem atunci aplica
*
SSS  w1w2. Rezultă wL(G).
iii. w=bx1x2...xn-1b cu xi  {a,b} se rezolvă similar cu cazul ii.

Astfel s-a demonstrat şi a doua incluziune, deci L=L(G) şi gramatica generează limbajul
dorit.

- 163 -
Construcţia unui automat push-down care să accepte limbajul L.
Idee: deoarece avem acelaşi număr de a şi b în cuvintele acceptate, la început dacă
automatul citeşte de pe bandă un caracter ‚a’ se introduce pe stivă un caracter A iar dacă
întâlneşte un caracter b se introduce pe stivă un caracter B. Ȋn continuare de fiecare dată
când întâlneşte un caracter ‚b’ se şterge un caracter A din vârful stivei sau se memorează
încă un B dacă vârful stivei a fost B. Similar, de fiecare dată când întâlneşte un caracter ‚a’
se şterge un caracter B din vârful stivei sau se memorează încă un A dacă vârful stivei a
fost A.

Dacă s-a terminat cuvântul, iar stiva nu este vidă, atunci cuvântul nu e recunoscut.
Automatul:
M=({q0},{a,b},{Z0,A,B},, q0,Z0,)
Iar funcţia de tranziţie este dată de:
(q0,a,Z0) = {(q0,AZ0)}
(q0,b,Z0) = {(q0,BZ0)}
(q0,a,B) = {(q0,)}
(q0,a,A) = {(q0,AA)}
(q0,b,A) = {(q0,)}
(q0,b,B) = {(q0,BB)}
(q0, ,Z0) = {(q0, )}

2. Fie gramatica G=({S,A,B},{a,b}, S, {SaB, S bA, Aa, AaS, AbAA, Bb,

BbS, BaBB}).
a. Găsiţi o derivare stângă şi un arbore de derivaţie pentru cuvântul
w=aaabbabbbba
b. Construiţi un automat push-down care acceptă limgabjul L(G).

Rezolvare:
a. O derivaţie pentru cuvântul
w=aaabbabbbba:
SaBaaBBaaaB
BBaaabSBBaaab
bABBaaabbaBBa
aabbabbB
aaabbabbbS 
aaabbabbbbA
aaabbabbbba

Arborele de derivare
este prezentat în fig.
alăturată.

b. Construcţia unui automat push-down pentru L(G), utilizând teorema 3.7.2.

- 164 -
 Gramatica este în formă normală Greibach, deci se poate construi automatul push-
down M=({q1},VT,VN,,q1,S,)
cu funcţia  dată de:
(q1,a,S)={(q1,B)}
(q1,b,S)={(q1,A)}
(q1,a,A)={( q1,S),(q1,)}
(q1,b,A)={(q1,AA)}
(q1,b,B)={(q1,S),(q1,)}
(q1,a,B)={(q1,BB)}

3. Fie automatul push-down:

P = ({s0, s1, s2, s3}, {a, b, c}, {z, a}, , s0, z, {s3})
cu  dat prin:
 (s0, a, z) = {(s1, aaz)}
 (s1, a, a) = {(s1, aaa)}
 (s1, b, a) = {(s2, )}
 (s1, c, a) = {(s2, )}
 (s2, b, a) = {(s2, )}
 (s2, c, a) = {(s2, )}
 (s2, , z) = {(s3, )}
a. Să se arate că L(P) = {anw| w{b, c}+, |w| = 2n, n ≥ 1}.
b. Ce fel de automat push-down este P?

Rezolvare:
a. Din starea s0 având z pe stivă (adică la momentul iniţial) automatul push-down nu are
tranziţie decât cu caracterul a, plasând pe stivă două caractere a.
După prima tranziţie, automatul intră în starea s1.

Din starea s1, cât timp se citeşte pe bandă caracterul a, automatul rămâne în starea s1 şi
pentru fiecare a citit de pe bandă se plasează doi de a în stivă.

Atunci când din starea s1 se întâlneşte prima data un caracter b sau c, automatul trece
în starea s2, deci nu vor mai fi acceptate caractere de a. Rezultă faptul că toate
cuvintele acceptate încep cu o secvenţă de tip an, cu n>0. În plus se şterge primul
caracter a din vârful stivei.

Din starea q2, pentru fiecare caracter b sau c citit de pe bandă se şterge un caracter a de
pe stivă.

Cuvântul este acceptat de către automat, dacă în stivă se află exact atât de multe
caracterea a câte caractere b ce se găsesc în cuvânt, trecându-se atunci în starea finală
s3. Dar numărul de caractere a de pe stivă este exact dublul numărului de caractere din
cuvântul w.

- 165 -
 Rezultă afirmaţia din enunţ.
b. Automatul push-down este determinist.

M4U4

I. Intrebări.
1. Să se enunţe şi să se demonstreze 4 proprietăţi de închidere pentru limbajele de tip 2.
Răspuns: vezi teoremele 3.8.1, 3.8.2, 3.8.3, 3.8.4, 3.8.5, 3.8.6
II. Exerciţii.
1. Se consideră limbajul L = {an bn | n ≥ 1}  {an b2n| n ≥ 1}. Să se arate că L este un
limbaj independent de context (se construieşte un automat push-down nedeterminist
sau o gramatică IDC folosind proprietatea de închidere a limbajelor IDC la reuniune.)

Rezolvare:
Se construieşte gramatica IDC:
G=({S,S1,S2},{a,b},S,P) cu
P:
SS1
SS2
S1aS1b
S1ab
S2aS2bb
S2abb

Demonstrăm faptul că L(G)=L.

L(G)L: fie wL(G), deci există o derivaţie în G pentru w. Dacă prima producţie care s-a
aplicat pentru obţinerea lui w a fost SS1, atunci din acel moment nu mai pot fi aplicate decât
producţiile
S1aS1b
S1ab
Aceste producţii generează în mod evident cuvinte de forma anbn cu n>0.

Dacă prima producţie care s-a aplicat pentru obţinerea lui w a fost SS2, atunci din acel
moment nu mai pot fi aplicate decât producţiile
S2aS2bb
S2abb
Aceste producţii generează în mod evident cuvinte de forma anb2n cu n>0.

Rezultă wL.

LL(G): fie wL, atunci ori w= anbn, ori anb2n cu n>0.

Dacă anbn, atunci se aplică:

- 166 -
 SS1aS1baaS1bb…anbn.

Dacă anb2n, atunci se aplică:

SS2aS2bbaaS2bbbb…anb2n.
Rezultă wL(G). S-a demonstrate şi a doua incluziune, deci L=L(G).

Construcţia unui automat push-down care să accepte L.

M=({ q0, q1, q2, q3},{a,b},{Z0,A},, q0, Z0,)
(q0,a,Z0)={(q1,AZ0),(q2,AAZ0)}
(q1,a,A)={(q1,AA)}
(q1,b,A)={(q3,)}
(q2,a,A)={(q2,AAA)}
(q2,b,A)={(q3,)}
(q3,b,A)={(q3,)}
(q3,,Z0)={(q3,)}

- 167 -