CAPITOLUL 4

AUTOMATE PUSH-DOWN

4.1. DEFINIREA UNUI AUTOMAT PUSH-DOWN

Am văzut în capitolul 4 că există gramatici independente de

context G pentru care nu există o maşini cu stări finite care recunosc

limbajul ( )L G . Exemplul dat a fost limbajul {0 1 | 1, 2, }n nL n= = K , el se

compune din n 0-uri urmaţi de n 1-uri. Motivul pentru care nu există o

MSF care să recunoască pe L este, că orice maşină care întâlneşte un şir

din acest limbaj ar trebui să „memoreze” câţi de 0 apar în faţa şirului, iar

atunci să verifice dacă numărul de 1-uri, care urmează, este acelaşi.

Aşadar, orice maşină care recunoaşte L va avea nevoie de o memorie

suplimentară capabilă să stocheze o cantitate arbitrară de informaţii.

Deoarece, prin definiţie maşinile cu stări finite au doar un număr finit de

stări, ele nu pot recunoaşte limbajul L. Demonstraţia completă este dată în

paragraful 3.1. Vom introduce acum un nou tip de dispozitiv, care poate

memora imput-urile precedente şi comportamentul anterior. Aceste

dispozitive se numesc automate push-down (APD); ele au avantajul de a

fi uşor implementate pe calculator. Vom constata că orice limbaj

independent de context poate fi recunoscut de o astfel de maşină.

Un automat push-down se compune dintr-un număr finit de stări,

un dispozitiv de intrare (împreună cu un cap de citire) şi o stivă cu un

pointer de stivă. Figura 4.1. ilustrează o reprezentare schematică a lui.

Automatul push-down funcţionează în felul următor: În orice moment dat

maşina se află într-o stare Q, pointer-ul de intrare (IP – input pointer sau

cap de citire) punctează spre un simbol a de pe banda de intrare iar

pointer-ul de stivă (SP – stack pointer) punctează spre un simbol Z de pe

stivă. Locaţia simbolului Z se numeşte vârful stivei (TOS – top of the

stack) Locaţiile sub vârful stivei sunt populate cu simboluri de stivă

admise iar cele deasupra vârfului se consideră goale. Mărimea stivei nu

este limitată, dar întotdeauna finită.

Figura 4.1. Automat push-down.

Pe baza acestor informaţii (Q, a şi Z) maşina poate efectua una sau mai

multe dintre următoarele acţiuni:

1. Schimbă starea.

2. Deplasează pointer-ul de intrare cu o unitate spre dreapta.

3. Înlocuieşte simbolul Z din vârful stivei printr-un număr finite de

simboluri de stivă acceptate şi poziţionează pointer-ul de stivă

pe vârful stivei.

4. Se opreşte.

Reamintim, că decizia care va fi luată este în exclusivitate

determinată de Q, a şi Z. În acţiunea de tip 3 este permisă înlocuirea lui Z

Stiva

Banda de intrare

Vârful stivei

Baza stivei

cu şirul vid λ . Caz în care acţiunea 3 înseamnă eliminarea simbolului Z

din stivă şi deplasarea pointer-ului de stivă cu o poziţie în jos. Operaţia se

numeşte POP. După ce una sau mai multe dintre acţiunile 1 – 3 au avut

loc, maşina se va află într-o stare nouă Q , cu pointer-ul de intrare

punctând spre noul simbol de intrare a iar pointer-ul de stivă la noul

simbol Z din vârful stivei. Întregul proces se repetă până la oprirea

maşinii. Simbolurile inferioare vârfului stivei sunt salvate de la o mişcare

la alta; ele formează „memoria” maşinii. Odată ce s-au citite simbolurile

benzii de intrare, ele se pierd – pointer-ul de intrare se deplasa numai la

dreapta. În schimb pointer-ul de stivă se poate deplasa în sus şi în jos.

Simbolurile de intrare se salvează, în momentul citirii, prin trecerea lor pe

stivă. Pentru o descriere completă a acestei maşini trebuie să specificăm:

configuraţia ei, deci stare iniţială, conţinutul iniţial al benzii de intrare şi

conţinutul stivei. Pentru simplificare, introducem următoarele convenţii

referitoare la automatele push-down:

C.1. În configuraţia iniţială stiva conţine un singur simbol – #.

Acest simbol nu poate fi niciodată eliminat din stivă (stiva nu va

fi vidă); el apare o singură dată pe stivă. Locaţie lui # se numeşte

baza stivei.

C.2. Orice şir de intrare σ se termină în partea dreaptă cu simbolul

$, astfel încât 1$σ σ= ; acest simbol este unic în şirul de input.

Motivul introducerii acestor simboluri speciale este ca maşina să poată

detecta sfârşitul input-ului şi baza stivei.

Ca şi maşinile cu stări finite, automatele push-down pot fi

deterministe sau nedeterministe. În cazul determinist, fiind date Q, a şi Z,

este permis doar un singur rând de acţiuni; în cazul nedeterminist există

cel puţin două alternative pentru anumite situaţii. Un automat push-down

are unele dintre stările sale desemnate ca stări acceptate sau stări finale.

Fie acum Σ un alfabet care nu conţine simbolul $, şi fie L un

limbaj peste Σ . Spunem că un automat push-down determinist P acceptă

L dacă sutn adevărate următoarele: Fiind dat un şir σ , setăm maşina P în

starea ei iniţială 0Q ; introducem şirul $σ pe banda de intrare şi pointer-ul

de intrare îl plasăm pe cel mai din stânga simbol din $σ . De asemenea,

punem simbolul # pe baza stivei şi fixăm pointer-ul de stivă pe el. După

un număr finit de paşi maşina P se opreşte. Dacă σ este în limbaj, P se

va opri într-una din stările acceptate iar pointer-ul de intrare va puncta la

simbolul $ (indicând că întregul input a fost citit). Dacă nu este în

limbajul L, atunci P se va opri într-o altă configuraţie, adică, fie într-o

stare neacceptată fie fără a scana întregul input σ (sau amândouă).

Observăm, că pentru acceptarea şirului σ , nu facem specificaţii

referitoare la conţinutul stivei. Definiţia modului de acceptare a unui

limbaj de către un automat push-down nedeterminist este similară cu

definiţia de acceptare a maşinii cu stări finite nedeterministe. Spunem că

un şir σ este în limbajul generat de un automat push-down nedeterminist

P, dacă şi numai dacă, începând din configuraţia iniţială, P poate ajunge,

printr-o secvenţă de mişcări legale, într-o configuraţie acceptată. Înainte

de a da definiţia formală a conceptelor discutate, să considerăm un

exemplu.

Simbol de intrareStare

0Q 0 1 $

A OpritOpri

tOprit

S

t

i

v

ă

#

1. Schimbă starea în 1Q .

2. Pune simbolul A în vârful

stivei.

3. Deplasează pointer-ul de intrare

cu o poziţie la dreapta.

Opri

t

Schimbă starea în

3Q , pointerii rămân

neschimbaţi.

Simbol de intrareStare

1Q 0 1 $

A

1. Rămâne în starea 1Q .

2. Pune simbolul A în vârful

stivei.

3. Deplasează pointer-ul de intrare

la dreapta.

Schimbă starea în

2Q ; pointerii rămân

neschimbaţi.

Opri

t

S

t

i

v

Ă# Oprit Oprit

Opri

t

Simbol de intrareStare

2Q 0 1 $

A Oprit

1. Schimbă starea în 2Q .

2. Scoate A în vârful stivei.

3. Deplasează pointer-ul de

intrare la dreapta.

OpritS

t

i

v

ă # Oprit Oprit

Schimbă starea în

3Q , pointerii rămân

neschimbaţi.

Stare 3Q : Se opreşte în toate cazurile.

Figura 4.2. Un automat push-down pentru limbajul {0 1 | 0,1, 2, }n nL n= = K .

Figura 4.3. Mişcările unui APD la input-ul 000111.

Exemplu 4.1. Considerăm un automat push-down care acceptă

limbajul {0 1 | 0,1,2, }n nL n= = K . Acest APD va avea patru stări 0Q (= starea

iniţială), 1Q , 2Q şi 3Q (starea acceptată). Alfabetul de intrare este {0,1}Σ = .

Fie, în afară de #, un simbol de stivă adiţional admis A. Maşina va opera

în felul următor. De fiecare dată când simbolul de intrare este 0, se

Configuraţia iniţială Pasul 1

Pasul 2 Pasul 3

Pasul 4 Pasul 5

Pasul 6 Pasul 7

Configuraţia finală

adăugat un simbol A pe stivă. Aşadar, după ce toate 0-urile au fost citite

maşina „ştie” câţi de 0 se află în input – pentru fiecare 0 din input se

salvează câte un A pe stivă. Pentru fiecare simbol de 1 întâlnit, maşina

şterge câte un A. În final, când ajunge la simbolul $ de pe banda te intrare,

pointer-ul de stivă va puncta spre simbolul # din baza stivei – numărul de

1-uri este egal cu numărul de A-uri salvate. Orice deviere de la această

formă indică că şirul σ nu aparţine limbajului. Descrierea exactă a

mişcărilor lui P este dată in tabelul din figura 4.2. Maşina se va opri în

starea 3Q cu capul de citire pe $ dacă şi numai dacă şirul de intrare σ se

compune din simboluri de 0 urmate de un număr egal de simboluri de 1.

În orice altă situaţie el se va opri într-o altă stare cu (eventual) o parte a

input-ului necitită. În figura 4.3. dăm secvenţa de mişcări a acestui APD

cu input-ul 000111.

Evident, înainte de a trece la definiţii matematice formale, avem

nevoie de unele notaţii pentru a descrie configuraţia unui automat

push-down în orice moment dat. Desenarea de diagrame schematice de

genul celor din figura 4.3. nu este convenabilă. Aşadar, descriem

configuraţia unui APD printr-un triplet:

1 1 1$, , # $, , #k k p t tQ x x x Q Z Z Zσ γ + −= K K

Figura 4.4. Un APD în configuraţia 1 1 1$, , #k k k t tx x x Q Z Z Z+ −K K .

Partea necitită a input-ului este dată prin 1$ $k k px x xσ += K iar capul de

citire punctează pe simbolul kx . Starea curentă este Q. Conţinutul stivei

este dat de 1 1# #t tZ Z Zγ −= K , unde tZ este vârful stivei iar # este baza

stivei. O maşină în configuraţia (4.1) corespunde figurii 4.4. Cu această

convenţie, mişcările maşinii din figura 4.3., por fi descrise astfel:

0 1 1

1 2 2

2 2 3

000111$, , # 00111$, , # 0111$, , #111$, , # 111$, , # 11$, , #1$, , # $, , # $, , # oprit

Q Q A Q AAQ AAA Q AAA Q AA

Q A Q Q

→ → →→ → → →→ → → −

Vom nota pointer-ul de intrare cu IP (input pointer) iar pointer-ul de stivă

cu SP (stack pointer).

Definiţia 4.1. Un automat push-down (APD) se compune din

următoarele şase obiecte:

1. O mulţime nevidă Σ de simboluri de intrare admise. Această

mulţime se numeşte alfabet de intrare şi nu conţine simbolul $.

2. O mulţime nevidă Γ de simboluri de stivă admise. Această

mulţime este numită alfabetul stivei şi nu conţine simbolul #.

3. O mulţime finită de stări 0 1Q { , , , }nQ Q Q= K .

4. O stare dedicată, notată 0Q ( Q∈ ), numită stare iniţială.

5. O mulţime nevidă F de stări, numite stări finale sau acceptate.

6. O funcţie de tranziţie ( , , )Q x Zδ . Argumentele lui δ sunt: x – un

simbol din Σ sau $; Q – o stare din Q, Z – un simbol din Γ sau #.

Valorile lui ( , , )Q x Zδ sunt mulţimi finite (sau vide) de triplete de

forma ˆ( , , )N Q γ unde

a) N este unul dintre simbolurile ↑ sau → (stă sau se mişcă).

b) Q este o stare din Q.

c) γ este un şir de caractere (eventual vid) din Γ , care poate fi

urmat de simbolul #.

În final avem:

*: Q ( {$}) ( {#}) ({ , } Q { {# }})δ λ× Σ∪ × Γ∪ → ↑ → × × Γ +B

unde ( )EB desemnează mulţimea tuturor submulţimilor finite a unei

mulţimi E, şi *D mulţimea tuturor şirurilor posibile de simboluri din D.

Aşadar, folosind notaţia pentru expresii regulare, *{# }λΓ + este

mulţimea de şiruri de simboluri din Γ urmate fie de şirul vid λ fie de

simbolul #. În plus, funcţia δ satisface următoarele condiţii:

C1. Pentru orice QQ∈ şi orice Z ∈Γ , ( , $, )Q Zδ trebuie să

conţină doar triplete de forma ˆ( , , )Q γ↑ . Aceasta corespunde

cerinţei ca pointer-ul de intrare să nu poată trece de simbolul $.

C2. Pentru orice x∈Σ şi orice QQ∈ , ( , , #)Q xδ conţine doar

triplete de forma ˆ( , , #)N Q γ , unde γ este un şir de elemente din Γ .

Aceasta corespunde cerenţei că simbolul # nu poate fi eliminat din

baza stivei: dacă înlocuim # prin #γ , simbolul stivei # rămâne în

baza stivei.

C3. Pentru orice x∈Σ , QQ∈ şi Z ∈Γ ( #Z ≠ ), ( , , )Q x Zδ conţine

doar triplete de forma ˆ( , , )N Q γ , unde γ este un şir din *Γ care nu

se termină cu #. Aceasta corespunde cerinţei ca # să apară numai la

baza stivei.

Un automat push-down cu Σ , Γ , Q, 0Q , F şi δ de genul celui de

mai sus se va nota 0{ , , Q, , F, }P Q δ= Σ Γ .

Funcţia δ din definiţia anterioară descrie mişcările posibile ale

maşinii. Argumentele x, Q şi Z din δ reprezintă input-ul curent, starea

curentă şi conţinutul vârfului stivei. Maşina definită prin definiţia 4.1.

este nedeterministă, deci valoarea lui δ este mulţimea mişcărilor posibile

dintr-o configuraţie dată (pot fi mai multe). Fiecare astfel de mişcare

posibilă este descrisă de un triplet ˆ( , , )N Q γ . Dacă N =↑ atunci pointer-ul

de intrare nu se schimbă – la mişcarea următoarea va fi citit acelaşi

simbol de intrare; dacă N =→ atunci pointer-ul de intrare se va muta cu o

poziţie la dreapta. Q desemnează următoarea mişcare a maşinii. γ este

înţeles astfel: Dacă ˆ( , , )N Q γ este un triplet din ( , , )Q xδ γ , atunci

simbolul Z din vârful stivei este înlocuit cu şirul γ . (Cel mai din stânga

caracter din γ va fi noul vârf al stivei.) Condiţia C1 precizează că

pointer-ul de intrare nu va trece de simbolul $. Condiţia C2 asigură că #

nu va fi eliminat niciodată din baza stivei iar C3 garantează că # nu apare

în altă locaţie de pe stivă decât în bază. Maşina se opreşte dacă

( , , )Q x Zδ =∅ – mulţimea vidă. Un automat push-down se numeşte

determinist dacă, pentru fiecare x, Q şi Z, valoarea lui ( , , )Q x Zδ este

mulţimea vidă sau conţine doar un singur triplet. Descriem în continuare,

formal, mişcările unui automat push-down.

Definiţia 4.2 Fie P un automat push-down. O configuraţie a lui P

este tripletul $, , #Qσ γ , unde σ este un şir de caractere din Σ iar γ este

un şir de caractere din Γ . (Amândouă pot fi vide.) Fie $, , #xy Q ZWK K

o configuraţie pentru P şi fie ˆ( , , )N Q γ un triplet din ( , , )Q x Zδ .

Dacă N =↑ atunci spunem că ˆ$, , #xy Q WγK K este următoarea

configuraţie legală, iar

ˆ$, , # $, , #xy Q ZW xy Q Wγ→K K K K

şi o numim mişcare legală.

Dacă N =→ atunci spunem că ˆ$, , #y Q WγK K este următoarea

configuraţie legală şi

ˆ$, , # $, , #xy Q ZW y Q Wγ→K K K K

o numim de asemenea mişcare legală.

Dacă ( , , )Q x Zδ =∅ , vom spune că P se opreşte. Dacă

1 $, , #C Qσ γ= şi 2ˆˆ ˆ$, , #C Qσ γ= sunt două configuraţii astfel încât este

posibilă trecerea din 1C în 2C , printr-o secvenţă legală de mişcări, atunci

notăm aceasta

* ˆˆ ˆ$, , # $, , #Q Qσ γ σ γ→ .

O mişcare specială şi cu nume propriu pentru un APD este plasarea

unui simbol A, în vârful stivei fără a elimina ceva din stivă. Funcţiile de

tranziţie pentru astfel de mişcări sunt de forma ˆ( , , ) ( , , )Q x Z N Q AZδ = :

Simbolul Z din vârful stivei a fost şters şi înlocuit cu şirul AZ; efectul

obţinut este plasarea lui A în vârful stivei. Această mişcare se numeşte

push – spunem că plasăm A în vârful stivei printr-o operaţie de push.

Exemplu 4.2. Considerăm APD-ul discutat anterior, care

recunoaşte limbajul {0 1 | 0,1, }n nL n= = K . Descrierea formală este

următoarea: Mulţimea {0,1}Σ = , alfabetul stivei este { }AΓ = , mulţimea

stărilor Q este 0 1 2 3{ , , , }Q Q Q Q şi mulţimea de stări acceptate este 3F { }Q= .

Starea iniţială este 0Q iar funcţia δ este dată prin:

Pentru starea 0Q :

0 0 0( , 0, ) ( , 1, ) ( , $, )Q A Q A Q Aδ δ δ= = =∅

0 1( , 0, #) ( , , #)Q Q Aδ = →

0( , 1, #)Qδ =∅

0 3( , $, #) ( , , #)Q Qδ = ↑

Pentru starea 1Q :

1 1( , 0, ) ( , , )Q A Q AAδ = →

1 2( , 1, ) ( , , )Q A Q Aδ = ↑

1 1 1( , 0, #) ( , 1, #) ( , $, #)Q Q Qδ δ δ= = =∅

Pentru starea 2Q :

2 2( , 0, ) , $, )Q A Q Aδ δ= ( = ∅

2 2( , 1, ) ( , , )Q A Qδ λ= →

2 2( , 0, #) ( , 1, #)Q Qδ δ= =∅

2 3( , $, #) ( , , #)Q Qδ = ↑

Pentru starea 3Q : 3( , , )Q x Zδ =∅ pentru toate valorile lui {$}x∈Σ∪

şi {#}Z ∈Γ∪ .

În exemplul de mai sus, pentru fiecare x, Q şi Z valoarea lui

( , , )Q x Zδ este un singur triplet sau mulţimea vidă. Aşadar,

comportamentul maşinii este complet determinat la fiecare configuraţie.

Aceste de maşini se numesc deterministe.

Definiţia 4.3. Fie 0{ , , Q, , F, }P Q δ= Σ Γ un automat push-down.

Dacă pentru fiecare {$}x∈Σ∪ , QQ∈ şi {#}Z ∈Γ∪ valoarea lui ( , , )Q x Zδ

este un singur triplet sau mulţimea vidă, spunem că P este determinist.

Dacă P nu este determinist, spunem că P este nedeterminist.

Fiind dat un automat push-down P, definiţia limbajului ( )L P

generat (recunoscut sau acceptat) de P este identică cu acea dată pentru

maşinile cu stări finite (definiţia 2.2.). Un şir σ aparţine limbajului ( )L P

dacă şi numai dacă, P pornit în configuraţia iniţială 0$, , #Qσ , trece

printr-o secvenţă de mişcări legale şi se opreşte în configuraţia $, , Q γ ,

QQ∈ . Se cere ca întregul şir σ să fie citit iar ultima stare să fie una

acceptată, dar nu se cere, cum o fac unii, ca stiva să fie vidă. Formal

avem următoarele.

Definiţia 4.4. Fie 0{ , , Q, , F, }P Q δ= Σ Γ un automat push-down.

Limbajul ( )L P generat (recunoscut sau acceptat) de P este definit prin

**

0( ) { | , $, , # $, , }L P Q Q Zσ σ σ γ= ∈Σ →

unde FQ∈ şi ( , $, )Q Zδ =∅ .

Exemplu 4.3. Fie Σ un alfabet; pentru fiecare şir *σ ∈Σ fie Rσ

inversul lui σ . Adică, dacă abcdσ = , R dcbaσ = , dacă aabσ = , R baaσ = .

Un palindrom peste Σ este un şir de forma Rσσ unde *σ ∈Σ . Exemple de

palindroame sunt abcddcba ( abcdσ = ) şi aabbaa ( aabσ = ). Observăm că

această definiţie este diferită de cea obişnuită „un cuvânt care se citeşte la

fel în ambele sensuri”. De exemplu, conform definirii noastre, abcbaσ =

nu este un palindrom. Arătăm în continuare cum se construieşte un

automat push-down P care recunoaşte limbajul de palindroame peste un

alfabet dat Σ . În lini mari, maşina P va citi şirul de intrare şi va insera

acest input, caracter cu caracter, pe stivă. La un moment dat, P „ghiceşte”

că a ajuns la mijlocul şirului iar atunci compară conţinutul stivei, din vârf

până în bază, cu restul input-ului. Dacă alegerea a fost bună şi input-ul

este un palindrom, pointer-ul de intrare ajunge la simbolul $ în acelaşi

timp când pointer-ul stivei ajunge la baza stivei marcată cu #. Definiţia

exactă a lui P este următoarea:

1. Σ este o mulţime nevidă, finită dată.

2. Γ = Σ (alfabetul stivei şi alfabetul de intrare este aceleaşi).

3. 0 1 2 3Q { , , , }Q Q Q Q= .

4. Starea acceptată este 3Q ( 3F { }Q= ).

5. Funcţia de tranziţie este definită ca:

i. 0 1( , , #) {( , , #)}Q x Q xδ = → pentru toţi x∈Σ .

ii. 0 3( , $, #) {( , , #)}Q Qδ = ↑

iii. 1 1 2( , , ) {( , , ), ( , , )}Q x Z Q xZ Q Zδ = → ↑ pentru toţi x∈Σ şi

Z ∈Γ .

iv. 2 2( , , ) {( , , )}Q x x Qδ λ= → pentru toţi x∈Σ .

v. 2 3( , $, #) {( , , #)}Q Qδ = ↑ .

vi. ( , , )Q x Zδ =∅ în toate cazurile nedefinite de i – v.

Mişcările se explică după cum urmează:

i. P porneşte în starea iniţială 0Q şi începe să insereze caracterele de

intrare în vârful stivei. Majoritatea inserărilor sunt făcute în timpul

stării 1Q .

ii. Asigură că şirul vid λ este în ( )L P .

iii. P continuă să insereze simbolul de intrare pe stivă sau „ghiceşte”

dacă mijlocul cuvântului a fost ajuns şi este timpul să compare

conţinutul stivei cu restul input-ului. Aceasta este partea operaţiei în

care maşina are un comportament nedeterminist.

iv. Simbolurile stivei sunt comparate, unul câte unul, cu restul

input-ului.

v. Cuvântul este găsit palindrom, deci P trece în starea acceptată.

Observăm că din cauza lui iii, APD-ul este nedeterminist. Considerăm

acum, ca exemplu, comportamentul lui P la input-ul abccbaσ = :

0 1 1

1 2 2

2 2 3

$, , # $, , # $, , #, , # $, , # $, , #

$, , # $, , # $, , # oprit

abccba Q bccba Q a ccba Q bacba Q cba cba Q cba ba Q baa Q a Q Q

→ → →→ → →

→ → −(4.1)

Subliniem faptul că maşina ar fi putut să „ghicească” greşite. De

exemplu, ar fi putut să aştepte prea mult mijlocul şirului:

0 1 1

1 1 2

$, , # , , # $, , #$, , # $, , # $, , # oprit

abccba Q bccba Q a ccba Q bacba Q cba ba Q ccba ba Q ccba

→ → →→ → −

Aici maşina se opreşte, într-o configuraţie neacceptată, deoarece

2( , , )Q b cδ =∅ . Aceasta însă nu însemnă că σ nu este în ( )L P ; criteriul

este să existe o posibilitate pentru P de a citi σ şi să se oprească într-o

stare acceptată. Că există este demonstrat în (4.1).

Evident că dacă automatele push-down sunt folosite pentru

recunoaşterea limbajelor de programare, acest tip de comportament nu

poate fi admis (sau cel puţin să fie strict controlat) – cu alte cuvinte,

APD-ul să fie determinist. În cazul maşinilor cu stări finite maşinile

deterministe şi nedeterministe se dovedesc a fi echivalente: Dat fiind o

MSF nedeterministă 1M , există o MSF 2M astfel încât 1 2( ) ( )L M L M= .

Aceasta însă nu este adevărat pentru automatele push-down. De fapt,

limbajul palindroamelor din exemplul 4.3. nu poate fi generată de orice

APD determinist.

Teorema 4.1. Fie L limbajul *{ | {0,1} }RL σσ σ= ∈ – mulţimea tuturor

polindroamelor compuse din simbolurile 0 şi 1. Nu există un automat

push-down determinist P astfel încât ( )L L P= .

Demonstraţie. Demonstraţia completă a acestei teoreme nu face

parte din scopul acestei lucrări. Vom arăta doar că L nu poate fi

recunoscut de un APD determinist care satisface următoarele trei condiţii:

1. Maşina se opreşte în orice stare dacă input-ul este gol, adică,

( , $, )Q Zδ =∅ pentru toate stările Q şi simbolurile de stivă Z. Cu alte

cuvinte, după ce input-ul a fost citit în întregime, maşina nu poate face

nici o mişcare.

2. Maşina acceptă şiruri doar cu stiva vidă. Acesta înseamnă că un şir

este acceptat dacă şi numai dacă maşina se opreşte într-o stare finală iar

stiva conţine numai simbolul #.

3. Maşina are doar o singură stare acceptată.

Presupunând că o maşină deterministă 0{ , , Q, , F, }P Q δ= Σ Γ

serveşte drept acceptor pentru limbajul L din ipoteză, şi mai presupunem

că L satisface condiţiile 1 – 3 de mai sus. Din ipoteză, F are doar o stare

acceptată, Q . Fie σ şi τ două şiruri din *{0,1} astfel încât R Rσσ ττ să nu

fie în L, de exemplu 101σ = şi 11τ = . Maşina P acceptă şirul Rσσ ,R Rσσ σσ , Rττ şi R Rττ ττ dar nu şi R Rσσ ττ . După citirea lui Rσσ maşina

trebuie să se afle în starea acceptată Q iar stiva trebuie să fie vidă (adică

să conţină numai #). Aşadar, la input-ul R Rσσ σσ maşina trece prin

următoarea secvenţă de configuraţii:

* *

0ˆ ˆ$, , # , , # $, , #R R RQ Q Qσσ σσ σσ→ → (4.2)

Ca urmare, dacă P este pornit în starea Q cu input-ul Rσσ , se va opri în

configuraţia acceptată. În acelaşi mod, la input-ul R Rττ ττ maşina va

executa secvenţa de mişcări:

* *

0ˆ ˆ$, , # , , # $, , #R R RQ Q Qττ ττ ττ→ → (4.3)

Starea Q din mijlocul configuraţilor (4.2) şi (4.3) este aceeaşi deoarece

este stare acceptată, iar noi am presupus că există doar una singură. Dar

acum să vedem ce se întâmplă când şirul R Rσσ ττ este trimis lui P. După

citirea primei părţi a şirului, Rσσ , maşina se va afla în starea Q şi stiva va

conţine doar #. (Din teorema (4.2.).) În acest moment, P se află în

configuraţia ˆ, , #R Qττ şi conform cu (4.3) el va trece în ˆ$, , #Q ,

adică, acceptă R Rσσ ττ , despre care am presupus că nu este în limbaj. Deci

( )L L P≠ .

Pentru o demonstraţie completă, trebuie arătat că dat fiind un APD

determinist P există alt APD determinist P astfel încât ˆ( ) ( )L P L P= şi P

să aibă 1 – 3 de mai sus. Pentru detalii vezi [13]. Q.E.D.

4.2. LEGĂTURI CU GRAMATICILE INDEPENDENTE DE

CONTEXT

Abordăm în continuare o discuţie detaliată a rolului jucat de

automatele push-down în recunoaşterea limbajelor independente de

context. În capitolele 2 şi 3 am studiat conceptul de maşină cu stări finite.

Aceste maşini au fost uşor de implementat; cu toate acestea, ele puteau să

recunoască doar limbaje simple – limbaje regulare. Ne-a fost uşor să dăm

un exemplu de limbaj nerecunoscut de nici una dintre aceste maşini.

Automatele push-down sunt similare maşinilor cu stări finite exceptând

un punct esenţial – APD-urile au o memorie nelimitată sub forma de

stivă. Este surprinzător faptul cum această mică facilitate face dintr-un

APD un instrument atât de puternic, capabil să genereze limbaje

independente de context arbitrare. De fapt, limbajele independente de

context sunt chiar acele limbaje pentru care există un APD care le

recunoaşte.

Teorema 4.2. Fie L un limbaj, adică, o mulţime de şiruri peste un

alfabet Σ . Atunci L este generat de un automat push-down dacă şi numai

dacă L are o gramatică independentă de context.

Demonstraţie. O demonstraţie completă a acestei teoreme nu este

prea dificilă, dar oarecum lungă. Din acest motiv vom prezenta doar o

schiţă într-o singură direcţie: Dată fiind o gramatică independentă de

context { , , , }G N S P= Σ , să arătăm cum se construieşte un APD P astfel

încât ( )L P L= . Pentru demonstraţia completă şi detalii suplimentare,

cititorul este invitat să consulte [13] sau [7].

Reamintim că o gramatică G este independentă de context dacă

toate producţiile ei sunt de forma X γ→ , unde X este un neterminal iar γ

este un şir, eventuala vid, de terminale sau neterminale ( *{ }Nγ ∈ Σ∪ ).

APD-ul de construit P va simula în esenţă derivarea cea mai din stânga

pentru orice şir din ( )L G . Alfabetul de intrare pentru P va fi Σ , identic cu

alfabetul lui G iar alfabetul stivei Γ pentru P va fi NΣ∪ . Presupunem că

simbolurile speciale $ şi # nu aparţin lui NΣ∪ . Maşina va avea trei stări:

0Q (starea iniţială), 1Q şi 2Q (starea acceptată). Majoritatea timpului

maşina va rămâne în 1Q . P acţionează în felul următor: Fie σ un şir din

( )L G şi fie 1 1S τ τ σ⇒ ⇒ ⇒ ⇒L derivarea cea mai din stânga a lui σ –

tranziţia între formele propoziţionale 1i iτ τ += fiind rezultatul înlocuirii

neterminalului cel mai din stânga X a formei propoziţionale iτ , cu partea

dreaptă a producţiei X γ→ . Maşina va face o mişcare la fiecare astfel de

tranziţie. Presupunem că primele mişcări sunt

*

1 2 1 2 kS x x x Aτ τ τ σ→ → → → →L K

unde 1 2, , , kx x xK sunt terminale iar următoarea producţia din derivare

este A α→ . Ca urmare şirul σ este de forma 1 2 1 2k nx x x y y yσ = K K ,

deoarece orice altă aplicare a unei reguli de producţie nu va afecta

1 2 kx x xK . În acest moment maşina P se va afla în configuraţia

1 2 1$, , #ny y y Q AτK . (Pointer-ul de intrare punctează la 1y , primul simbol

al părţii lui σ care urmează a fi derivat şi pointer-ul de stivă punctează pe

A, următorul neterminal de înlocuit în derivarea ceea mai la stânga a lui

σ ). Maşina va înlocui acum vârful stivei, adică, simbolul A, cu şirul α –

partea dreaptă a producţie A α→ . Dacă α începe cu un neterminal 'A ,

avem aceeaşi situaţie, deci înlocuim 'A cu 'α – partea dreaptă a

producţiei ' 'A α→ . Repetăm procedura până când apare un terminal în

vârful stivei. Aşadar, putem presupune că α începe cu un terminal. Acest

terminal trebuie să fie 1y , altminteri A α→ nu poate fi producţia corect

aleasă. Prin urmare, după ce A este înlocuit cu α , pointer-ul de intrare şi

pointer-ul de stivă punctează amândouă spre acelaşi simbol 1y . În

continuare eliminăm pe 1y din stivă şi deplasăm pointer-ul de intrare la

dreapta, iar atunci repetăm procedeul. Evident că continuând în acest

mod, maşina P va trece din configuraţia 1$, , #Qσ în 1$, , #Q , punct în

care schimbăm starea în 2Q şi ne oprim. Definiţia completă a funcţiei de

tranziţie este următoarea:

1. 0 1( , , #) {( , , #)}Q x Q Sδ = ↑ pentru toate terminalele x. Aceasta are

ca efect plasarea simbolului de start în vârful stivei şi trecerea în

starea „activă” 1Q .

2. 0 1( , $, #) {( , , #)}Q Q Sδ = ↑ . Această tranziţie particulară este

necesară pentru cazul în care şirul vid λ este în limbajul ( )L G .

Simbolul de start S va fi plasat pe stivă; dacă ( )L Gλ∈ eventual

el va „dispare”.

3. 1 1( , , ) {( , , )}Q x x Qδ λ= → pentru toate terminalele x. Pointer-ul de

intrare şi pointer-ul de stivă punctează amândouă spre acelaşi

simbol x. Se elimină x de pe stivă şi se citeşte următorul simbol.

4. Dacă x este terminal sau simbolul $, şi dacă A este un

neterminal, atunci

1 1 1 1 2 1 p( , , ) {( , , ), ( , , ), , ( , , )}Q x A Q Q Qδ α α α= ↑ ↑ ↑K

unde 1 2| | | pA α α α→ K sunt toate producţiile având A în partea

stângă. Această regulă se aplică atunci când un neterminal se

află în vârful stivei, şi maşina „alege” care dintre producţii va fi

în continuare aplicată pentru a se potrivi cu simbolul curent de

intrare x (precum şi restul input-ului).

5. 1 2( , $, #) {( , , #)}Q Qδ = ↑ . Întregul input a fost citit, stiva este

vidă, deci maşina trece în starea acceptată.

6. ( , , )Q x Zδ =∅ pentru restul de x, Q şi Z.

Maşina P astfel construită este evident nedeterministă: Când regula

4 de mai sus este pe punctul de a fi aplicată, P „alege” producţia corectă

care se va folosi. Este limpede, că dacă există o secvenţă de alegeri

corecte (adică, dacă input-ul σ este în limbaj), P va accepta input-ul. De

asemenea este adevărat că dacă P poate trece din configuraţia iniţială în

ceea acceptată, atunci σ este derivabil în gramatica G. Demonstraţia

completă a acestor consideraţii poate fi uşor construită, şi se bazează pe

inducţia după lungimea şirului σ . Q.E.D.

Configuraţia lui M Forma

propoziţională

corespunzătoare,

vârful stivei este

subliniat

Comentarii

0*( )$, , #a a a Q+ Configuraţia iniţială

1*( )$, , #a a a Q E+ E E plasat în vârful stivei

1*( )$, , #a a a Q T+ T aplicat E T→

1*( )$, , * #a a a Q T F+ *T F aplicat *T T F→

1*( )$, , * #a a a Q F F+ *F F aplicat T F→

1*( )$, , * #a a a Q a F+ *a F aplicat F a→

1*( )$, , * #a a Q F+ *a F a eliminat din vârful

stivei

1( )$, , #a a Q F+ *a F * eliminat din vârful

stivei

1( )$, , ( ) #a a Q E+ * ( )a E aplicat ( )F E→

1)$, , ) #a a Q E+ *( )a E ( eliminat din vârful

stivei

1)$, , ) #a a Q E T+ + *( )a E T+ aplicat E E T→ +

1)$, , ) #a a Q T T+ + *( )a T T+ aplicat E T→

1)$, , ) #a a Q F T+ + *( )a F T+ aplicat T F→

1)$, , ) #a a Q a T+ + *( )a a T+ aplicat F a→

1)$, , ) #a Q T+ + *( )a a T+ a eliminat din vârful

stivei

1)$, , ) #a Q T *( )a a T+ + eliminat din vârful

stivei

1)$, , ) #a Q F *( )a a F+ aplicat T F→

1)$, , ) #a Q a *( )a a a+ aplicat F a→

1)$, , ) #Q *( )a a a+ a eliminat din vârful

stivei

1$, , #Q *( )a a a+ ) eliminat din vârful

stivei

2$, , #Q oprit şi acceptat Configuraţia finală

Figura 4.5. Mişcări ale uni APD.

Exemplu 4.4. Fie gramatica expresiilor algebrice:

|E E T T→ + * |T T F F→ ( ) |F E a→

Regulile de tranziţie pentru automatul push-down corespunzător sunt

următoarele:

0 1( , , #) {( , , #)}Q x Q Eδ = ↑ pentru toţi { , ,*, (, )}x a∈Σ = +

0 1( , $, #) {( , , #)}Q Q Eδ = ↑

1 1( , , ) {( , , )}Q x x Qδ λ= → pentru toţi x∈Σ

1 1 1( , , ) {( , , ), ( , , )}Q x E Q E T Q Tδ = ↑ + ↑ pentru toţi {$}x∈Σ∪

1 1 1( , , ) {( , , * ), ( , , )}Q x T Q T F Q Fδ = ↑ ↑ pentru toţi {$}x∈Σ∪

1 1 1( , , ) {( , , ( )), ( , , )}Q x F Q E Q aδ = ↑ ↑ pentru toţi {$}x∈Σ∪

1 2( , $, #) {( , , #)}Q Qδ = ↑

Secvenţa de mişcări a APD-ului la input-ul *( )a a a+ este arătată în figura

4.5. Reamintim de natura nedeterministă a acestui APD. De exemplu, în

configuraţia 1)$, , ) #a Q F (marcată cu în figura 4.5.), M alege

valoarea „corectă” pentru 1( , , )Q a Fδ , adică tripletul 1( , , )Q a↑ . Dacă ar

alege cealaltă posibilitate 1( , , ( ))Q E↑ , APD-ul s-ar opri imediat într-o

configuraţie neacceptată: 1 1)$, , ) # )$, , ( )) # oprita Q F a Q E→ − .

Exemplu 4.5. În acest exemplu prezentăm construcţia şi

funcţionarea unui APD plecând de la o gramatică G:

| | ||

|

S abA B baB CA bS bB aSC aA λ

→→→→

Regulile de tranziţie rezultate sunt:

0 1( , , #) {( , , #)}Q x Q Sδ = ↑ pentru toţi { , }x a b∈Σ =

0 1( , $, #) {( , , #)}Q Q Sδ = ↑

1 1( , , ) {( , , )}Q x x Qδ λ= → pentru toţi x∈Σ

1 1 1 1 1( , , ) {( , , #), ( , , ), ( , , ), ( , , )}Q x S Q abA Q B Q baB Q Cδ = ↑ ↑ ↑ ↑ pentru toţi

{$}x∈Σ∪

1 1 1( , , ) {( , , ), ( , , )}Q x A Q bS Q bδ = ↑ ↑ pentru toţi {$}x∈Σ∪

1 1( , , ) {( , , )}Q x B Q aSδ = ↑ pentru toţi {$}x∈Σ∪

1 1 1( , , ) {( , , ), ( , , )}Q x C Q aA Qδ λ= ↑ ↑ pentru toţi {$}x∈Σ∪

1 2( , $, #) {( , , #)}Q Qδ = ↑

Ca de obicei, 0Q este starea iniţială iar 2Q este starea acceptată. În această

gramatică şirul vid λ aparţine limbajului ( )L G , derivarea lui fiind

S C λ⇒ ⇒ . APD-ul îl acceptă şi pe λ (cum ar trebui s-o şi facă);

secvenţa de configuraţii este:

0 1 1

1 2

$, , # $, , # $, , #$, , # $, , # opritQ Q S Q C

Q Q→ → →

→ → −

Şirul baaa face parte din limbajul ( )L G ; derivarea lui cea mai din stânga

este S baB baaS baaaS baaaC baaa⇒ ⇒ ⇒ ⇒ ⇒ . Mişcările corespunzătoare

ale APD-ului sunt:

0 1 1

1 1 1

1 1 1 1

1 2

$, , # $, , # $, , #$, , # $, , # $, , #

$, , # $, , # $, , # $, , #$, , # $, , # oprit

baaa Q baaa Q S baaa Q baBaaa Q aB aa Q B aa Q aSa Q S a Q aS Q S Q C

Q Q

→ → →→ → → →→ → → → →→ → −

Cu acelaşi input baaa maşina ar fi putut să execute următoarea

secvenţă de mişcări

0 1 1$, , # $, , # $, , # opritbaaa Q baaa Q S baaa Q abA→ → −

deoarece 1( , , )Q b aδ =∅ . Ca urmare, dacă σ este derivabil în ( )L G , atunci

un APD poate efectua o secvenţă legală de mişcări rezultând în

acceptarea lui σ . În capitolele 6 – 8 vom prezenta unele metodele pentru

a face aceste maşini deterministe. Evident, aceasta nu este întotdeauna

posibil (vezi teorema 4.1.).

Aşadar, orice limbaj independent de context poate fi generat de un

automat push-down. Reciproca este de asemenea adevărată: Dat fiind un

automat push-down P, există o gramatică independentă de context G

astfel ca ( ) ( )L P L G= ; nu vom da o demonstraţie a acestui rezultat. Ea nu

este dificilă, însă incomodă şi lungă (vezi [13] sau [7]).

4.3. EVALUAREA EXPRESIILOR ARITMETICE

Automatele push-down pot fi utilizate pentru evaluarea automată a

expresiilor aritmetice. Problema se pune în felul următor: Vrem să

programăm un calculator în aşa fel încât dacă introducem o expresie

aritmetică, el o va evalua corect. De exemplu, dacă expresia este

2*(3 2*5) 8*2+ + maşina execută mai întâi înmulţirea 2*5 , adună

rezultatul la 3, înmulţeşte acesta cu 2, etc. Ea ar trebui programată astfel

încât să ştie ce are de făcut şi în ce ordine. Reamintim că maşina primeşte

expresia secvenţial: Adică, citeşte mai întâi simbolul 2, atunci simbolul *,

(, 3 etc. În momentul în care ajunge la sfârşitul input-ului ea să

„înţeleagă” input-ului şi execută operaţiile necesare în ordinea corectă.

Pentru simplificare, ne vom limita la expresii cu doar două operaţii

binare, * şi +. Odată înţeleasă, metoda poate fi uşor de extinsă şi pentru

alte operaţii (scădere, împărţire, ridicare la putere sau operaţii unare ca

a− ). Mai întâi prezentăm soluţia problemei în cazul în care expresia este

introdusă în aşa numita notaţie postfixată (numită şi notaţia poloneză

inversă). În această notare operaţia nu este scrisă între numere, ci după

ele. Deci 3 7+ se scrie ca 37 + , 8*4 ca 84* , etc. În general, dacă & denotă

o operaţie binară (adunare, înmulţire sau altceva), atunci &a b se scrie ca

&ab . Fiecare operaţie acţionează asupra primilor două operanzi

precedenţi. De exemplu, notaţia postfixată *ab c+ este înţeleasă ca

( )* (( ) )*ab c ab c+ = + , deci * acţionează asupra lui c şi lui ab + . Observăm

că în notaţia postfixată nu sunt necesare parantezele: Expresia *ab c+ este

unic descifrată dacă cerem ca fiecare operator să acţionează asupra celor

doi operanzi precedenţi. Acum putem construi uşor un automat

push-down care va evalua automat orice expresie aritmetică σ ,

presupunând că expresia este scrisă în forma postfixată. Maşina va avea

numai o singură stare şi va acţiona conform următoarelor reguli:

1. Dacă simbolul de intrare este un număr, APD-ul plasează acest

simbol în vârful stivei şi deplasează pointer-ul de intrare cu o

unitate la dreapta.

2. Dacă input-ul este un operator, maşina scoate primele două numere

din stivă, execută operaţia indicată, şi plasează rezultatul obţinut în

vârful stivei.

3. Când marcajul de intrare $ este ajuns, stiva va conţine numai

valoarea corectă a expresiei (presupunând că input-ul a fost

gramatical corect).

Considerăm de pildă expresia 2*(3 2*5) 8*2+ + . Forma ei postfixată

este 2325* *82*+ + . Mişcările APD-ului cu acest input sunt:

2325* *82* $, # 325* *82* $, 2#25* *82* $, 32# 5* *82* $, 232#* *82* $, 5232# *82* $, 1032#*82* $, 132# 82* $, 26# 2* $, 826#* $, 2826# $, 1626# $, 42#

+ + → + + →→ + + → + + →→ + + → + + →→ + → + → + →→ + → + →

Am omis simbolul de start deoarece a fost întotdeauna acelaşi. Prin

subliniere am vrut să diferenţiem între numărul 16 şi 1 urmat de 6.

Această metodă, deşi funcţionează destul de bine, nu rezolvă în întregime

problema noastă, deoarece de regulă expresiile aritmetice nu sunt

exprimate în notaţia postfixată ci în foram „normală” cu operatorul scris

între operanzi – notaţia infixată. Deci avem nevoie de o modalitate

automată (deterministă) pentru transcrierea expresiei aritmetice din

notaţia uzuală în notaţia postfixată. Descrierea formală a notaţie

postfixate este următoarea:

Definiţia 4.5. Fie Σ mulţimea operanzilor (adică, numerele) şi fie

∆ mulţimea operatorilor (adică, +, *, –, etc.). Atunci au loc:

1. Reprezentarea postfixată a fiecărui operand a este chiar a.

2. Dacă A este o expresie scrisă în forma infixată şi A este

reprezentarea ei în notaţia postfixată, atunci reprezentarea

postfixată a lui (A) este A .

3. Dacă A şi B sunt expresii în notaţia infixată, şi A , B sunt

transcrierile corespunzătoare în notaţia postfixată, atunci pentru

orice operator &, transcrierea postfixată pentru A&B este ˆ ˆ &AB .

Punctul 2 se înţelege astfel: Fiind dată o notaţie postfixată A

pentru A, notaţia postfixată pentru (A) este A (omitem parantezele).

Similar, 3 spune că dacă ştim cum să reprezentăm A şi B în notaţie

postfixată (ca A şi ca B ), atunci ştim cum să reprezentăm A&B: anume

ca ˆ ˆ &AB . Ceea ce dorim în continuare este să construim o schemă

deterministă care va converti o notaţie infixată dată în transcrierea ei

postfixată. Deci să convertească şirurile *a b c+ , *( )a b c+ în *abc + ,

*abc + etc. În general, dacă 1σ , 2σ , 3σ şi σ sunt expresii aritmetice în

notaţie infixată iar reprezentările lor postfixate sunt 1σ , 2σ , 3σ şi σ atunci

această schemă efectuează transcrieri indicate în (4.4). Primul lucru de

remarcat despre această schemă este că operanzii în notaţia postfixată

apar în aceeaşi ordine ca în notaţia infixată, singurele schimbări sunt că

parantezele au fost eliminate iar operatorii * şi + sunt interschimbaţi.

1 2 1 2

1 2 1 2

1 2 3 1 2 3

1 2 3 1 2 3

ˆˆ ˆ

ˆ ˆ( )*( ) *ˆ ˆ ˆ*( ) *

ˆ ˆ ˆ( )*( ) *

σ σσ σ σ σσ σ σ σσ σ σ σ σ σσ σ σ σ σ σ

→+ = +

=+ = +

+ = +

(4.4)

Schema trebuie să ţină cont de „priorităţile” operatorilor. Astfel, în

expresia *a b c+ , înmulţirea *b c se execută înaintea adunării, deci în

notaţia postfixată simbolul * apare la dreapta lui +. Evident dacă o astfel

de schemă are toate proprietăţile listate în (4.4), atunci ea va funcţiona

corect în toate cazurile. Se observă că schema poate fi realizată

determinist cu ajutorul unui automat push-down cu output. Mai întâi,

explicăm cum funcţionează o astfel de maşină iar apoi vom da indicaţii

pentru demonstrarea corectitudinii ei. Acest translator push-down va fi un

automat push-down, descris în paragraful 4.1, împreună cu un dispozitiv

de ieşire. Schematic el poate fi reprezentat ca în figura 4.6.

Figura 4.6. Un APD care traduce o notaţie infixată într-o notaţie

postfixată.

Output

Stiva

Şir de intrare

Automatul push-down are doar o singură stare Q şi acţionează în felul

următor. Iniţial, input-ul conţine o expresie aritmetică în notaţie infixată;

stiva este vidă (adică, conţine doar marcajul #); banda de ieşire este

goală; şi pointer-ul de ieşire punctează la cea mai din stânga poziţie a

benzii. Presupunem că input-ul este delimitate în partea dreaptă de

simbolul $ astfel ca T să poată detecta sfârşitul input-ului. La un moment

dat maşina examinează simbolul curent din vârful stivei şi simbolul de

intrare curent, putând efectua una din următoarele operaţii:

1. Emite unul sau mai multe simboluri pe banda de ieşire. Aceste

simboluri pot fi luate fie din stivă fie de pe banda de intrare.

Pointerii relevanţi sunt ajustaţi corespunzător (pointer-ul de intrare

este deplasează la dreapta iar pointer-ul de stivă coboară).

Pointer-ul de ieşire se deplasează la dreapta la următoarea poziţie

liberă disponibilă.

2. Plasează simbolul de intrare curent în vârful stivei, ajustând ambii

pointeri (Această operaţie se numeşte push).

Simbolurile de intrarea admise sunt operanzii (adică, numerele) a,

b, c, ..., simbolurile de operatori sunt * şi +, parantezele ), ( şi simbolul de

delimitare $. Simbolurile de stivă admise sunt +, * paranteza stângă ( şi

simbolul din baza stivei #. Fiecărui simbol de stivă Z îi asociem două

numere – prioritatea de input ( )I Z şi prioritatea de stivă ( )S Z – conform

tabelului din figura 4.7.

Z ( )I Z ( )S Z

* 2 2

+ 1 1

( 3 0

# – 0

Figura 4.7. Funcţii de prioritate.

Maşina se comportă în felul următor:

1. Dacă simbolul de intrare este unul dintre operanzii a, b, c, ..., el

este trimis spre output şi se citeşte următorul simbol. Pointer-ul de

intrare şi cel de ieşire sunt ajustaţi corespunzător; stiva nu se

schimbă.

2. Dacă simbolul de intrare x este (, +, sau *, adică, este şi simbol de

stivă, atunci se compară valorile pentru ( )I x şi ( )S Z , unde Z este

vârful curent al stivei. Vor avea loc următoarele:

i. Dacă ( ) ( )I x S Z> simbolul x este plasat în vârful stivei şi se

citeşte următorul simbol. Pointerii de input şi de stivă sunt

ajustate corespunzător, nu are loc un output.

ii. Dacă ( ) ( )I x S Z≤ se emite ca output simbolul Z din vârful

stivei, pointerii de stivă şi de ieşire sunt ajustaţi iar simbolul x

este citit din nou (pointer-ul de intrare rămâne neschimbat).

3. Dacă simbolul de intrare este paranteza dreaptă ) stiva este trimisă

la output, unul câte unul, până ce apare paranteza stângă (. Iar

atunci se elimină paranteza stângă ( din stivă – nu este trimisă la

ieşire; pointerii de stivă şi de output se ajustează corespunzător iar

pointer-ul de intrare se deplasează la stânga.

4. Dacă simbolul de intrare x este $, atunci se trimite, începând din

vârf, unul câte unul, conţinutul stivei spre ieşire până la marcajul

de bază #.

Descriem configuraţia maşinii T într-un moment dat printr-un

triplet de şiruri astfel:

1 1 1 1 2 $, #,

i i n j j k

INP TOS OUT

x x x Z Z Z y y y

C C C

+ −

↑ ↑ ↑

K K K(4.5)

Unde INPC este simbolul de intrarea curent, TOSC vârful curent al stivei iar

OUTC este pointer-ul de ieşire curent. APD-ul din figura 4.6. se află în

configuraţia (4.5). Cu aceste notaţii, dăm în continuare unele exemple de

mişcări ale lui T la diferite input-uri.

Exemplu 4.6. Comportamentul maşinii T la diverse input-uri.

Cu input-ul *a b c+ maşina se mişcă astfel:

* $, #, * $, #, * $, #, * $, #, $, * #, $, * #, $, #, * $, #, *

a b c b c a b c ac ab c abc abc

abc abc

λ+ → + → +→ + → + → +→ + → +

Cu input-ul ( )*a b c+ mişcările lui T sunt:

( )* $, #, )* $, (#, )* $, (#, )* $, (#, )* $, (#, * $, #, $, *#, $, *#, $, #, *

a b c a b c b c ab c a c ab c abc ab ab c ab c

λ λ+ → + → +→ + → + → + +→ + → + → +

Dacă input-ul este ( * )*( )a b c d e+ + , mişcările sunt:

( * )*( )$, #, * )*( )$, (#, * )*( )$, (#, * )*( )$, (#,

* )*( )$, (#, )*( )$, * (#, )*( )$, * (#, *( )$, #, *( )$, *#, *

a b c d e a b c d eb c d e a b c d e ac d e ab c d e ab

d e abc d e abcd e abc d e

λ λ+ + → + +→ + + → + +→ + + → + +→ + + → + +→ + + → + )$, (*#, *

)$, (*#, * )$, (*#, *)$, (*#, * $, *#, *$, #, * *

abce abc d e abc d

abc de abc deabc de

+→ + + → + +→ + + → + +→ + +

Evident maşina funcţionează corect în aceste exemple. De fapt, ea o va

face în toate cazurile.

Teorema 4.3. Fie T un automat push-down descris în figurile 4.5. şi

4.6. Dacă σ este o expresie aritmetică oarecare bine formată în notaţie

infixată, atunci T va transforma σ în σ – traducerea corectă a lui σ în

notaţia postfixată.

Demonstraţie. (O schiţă) Vom folosi inducţia după lungimea

şirului de intrare. Singurele expresii aritmetice (în notaţia infixată) de

lungime mai mică sau egală cu teri sunt: a, (a), a b+ şi *a b . Se observă

uşor că T va traduce corect toate acestea. Presupunem acum că T

funcţionează corect pentru toate expresiile de lungime cel mult 3n ≥ şi fie

σ o expresie, de lungime 1n + , scrisă în notaţia infixată. Atunci σ este

într-una din următoarele forme:

i. ( )σ τ=

ii. 1 2σ τ τ= +

iii. 1 2*σ τ τ=

unde toţi τ sunt de lungime mai mică decât n. În fiecare caz T îl va

traduce corect pe σ :

i. Iniţial, T va trece din configuraţie ( )$, #, τ λ în )$, (#, τ λ . Iar

atunci va opera asuprea lui τ , producând output-ul τ – traducerea

postfixată a lui τ – fără a influenţa simbolul ( de pe stivă. Aşadar,

la un moment dat va ajunge în configuraţia ˆ)$, (#, τ şi va trece în

ˆ$, #, τ producând rezultatul corect.

ii. T porneşte în configuraţia 1 2$, #, τ τ λ+ . Din ipotezele inducţiei,

el va traduce 1τ corect, deci după ce ultimul simbol din 1τ a fost

citit, T se va afla în configuraţia 2 1$, #, τ τ+ . De aici va trece în

2 1$, #, τ τ iar conform ipotezelor inducţiei el va continua să treacă

în 1 2ˆ ˆ$, #, τ τ+ . Simbolul + din stivă va rămâne nedistribuit

deoarece 2τ trebuie să înceapă cu un operand x sau paranteză

stângă (; în ambele cazuri + rămâne pe stivă. Din această ultimă

configuraţie, T va trece în 1 2ˆ ˆ$, #, τ τ + , producând din nou

traducerea corect.

iii. Analog cu ii. Q.E.D.

Trebuie să menţionăm aici că T nu detectează greşeli în input-ul

original. Astfel, de exemplu, dacă input-ul σ este *a b+ output-ul lui T va

fi *ab + , amândouă fiind secvenţe fără înţeles. În capitolele 6 şi 8 vom

construi analizatoare deterministe care nu vor evalua doar aceste expresii

aritmetice, ci chiar vor putea decide dacă şirurile de intrare sunt corect

formate. Maşina T, dată aici, nu este un analizator adevărat deoarece nu

reconstruieşte arborele de derivare a input-ului.

4.4. LEMA DE POMPARE PENTRU APD-URI

În paragrafele 4.1. şi 4.2. am văzut că automatele push-down sunt

mult mai adaptabile decât maşinile cu stări finite. Mai exact, am găsit un

limbaj acceptat de un APD dar nu de o maşină cu stări finite (exemplul

4.1.). Din acest motiv ne putem întreba dacă orice limbaj este recunoscut

de un APD, sau (din teorema 4.2.) ce se întâmplă în cazul limbajelor cu

gramatică independentă de context? Vom utiliza în mod special teorema

4.4., care este analoagă cu lema de pompare pentru maşini cu stări finite

(teorema 3.1.).

Teorema 4.4. (Lema de pompare pentru automate push-down). Fie

{ , , , }G N S P= Σ o gramatică independentă de context. Atunci există un

număr k, care depinde numai de G, cu următoarea proprietate: Orice

propoziţie σ din ( )L G de lungime mai mare decât k poate fi scrisă ca

1 2σ ατ βτ γ= , unde α , β , γ , 1τ şi 2τ sunt şiruri din *Σ şi astfel încât pentru

fiecare 0,1,2,3,n = K şirul 1 2n nσ ατ βτ γ= aparţine de asemenea lui ( )L G . Mai

mult, unul din şirurile 1τ şi 2τ (sau amândouă) est diferit de şirul vid λ .

Motivul pentru care teorema se referă la automate push-down este

că limbajele cu gramatici independente de context sunt chiar acele

limbaje care sunt recunoscute de automate push-down (teorema 4.2.).

Înainte de a trece la demonstraţie vom arăta cum se aplică această

teoremă.

Exemplu 4.7. Fie 0L limbajul 0 { | 0,1, 2, }n n nL a b c n= = K . Aşadar, L se

compune din şiruri având un număr egal de simboluri a, b şi c urmate

succesiv. Vrem să arătăm că 0L nu este acceptat de un APD, sau

echivalent, nu are gramatică independentă de context. Presupunem deci,

că L are o gramatică independentă de context G astfel ca 0 ( )L L G= şi fie k

numărul corespunzător lui G din teorema 4.4. Dacă m k> , şirulm m ma b cσ = are lungimea 3m k> , deci σ poate fi scris ca 1 2

m m ma b c ατ βτ γ= ,

unde sau 1τ λ≠ sau 2τ λ≠ , şi pentru fiecare 1,2,n = K şirul 1 2n nατ βτ γ este în

limbajul L. Vom arăta că aceasta este imposibil. Presupunem că 1τ λ≠ .

Atunci 1τ trebuie să fie un şir format dintr-un singur tip de simboluri,

adică, a, b, sau c. Într-adevăr, dacă de exemplu, τ conţine a-uri şi b-uri,

atunci 2τ ττ= va avea a-uri (în al doilea τ ) care se află în dreapta b-urilor

(în primul τ ). Dar aceasta implică că 2 21 2ατ βτ γ nu este în 0L – contradicţie

cu alegerea lui 1τ . Analog se procedează pentru 1τ conţinând a-uri şi c-uri

sau b-uri şi c-uri. În acelaşi mod arătăm că dacă 2τ λ≠ , atunci 2τ trebuie

să fie un şir format fie numai din a-uri fie numai din b-uri sau c-uri. Dar

atunci, considerăm din nou şirul 2 21 2ρ ατ βτ γ= care este garantat, prin

teorema 4.4., a fi din 0L . Dacă 1τ se compune doar din a-uri iar 2τ numai

din b-uri, atunci ρ are prea puţini de c. Dacă 1τ are numai b-uri şi 2τ

numai c-uri, atunci ρ are prea puţini de a, etc. În toate cazurile posibile

şirul ρ nu poate fi o propoziţie în limbajul L. Deci, într-adevăr, L nu

poate avea o gramatică independentă de context.

Continuăm acum cu demonstraţia teoremei 4.4. Pentru

simplificare, facem ipoteza că G nu are producţii vide, adică, producţii de

forma A λ→ . Fiind dată o gramatică G, vom construi un număr ( )k k G=

astfel încât pentru orice şir σ din ( )L G de lungime mai mare decât k,

există o derivare a lui σ de forma

* * *

1 2 1 2S X Xα γ ατ τ γ ατ βτ γ σ⇒ ⇒ ⇒ = (4.6)

unde X este un neterminal oarecare şi fie 1τ fie 2τ este un şir nevid.

Într-adevăr, dacă (4.6) este adevărată, atunci

*

1 2X Xτ τ⇒ şi *

X β⇒

sunt derivări valide în G. Aşadar, toate dintre derivările următoare pot fi

făcute în G:

* *

* * *

1 2 1 2* * * *

2 2 2 21 2 1 2 1 2

S X

S X X

S X X X

α γ αβγ

α γ ατ τ γ ατ βτ γ

α γ ατ τ γ ατ τ γ ατ βτ γ

⇒ ⇒

⇒ ⇒ ⇒

⇒ ⇒ ⇒ ⇒L

şi se obţine teorema.

Fie r lungimea celui mai lung şir din partea dreaptă a unei producţii

din G, şi fie n numărul de neterminale din G; 0 1n n= + . Punem 0 1nk r= + .

Fie acum σ un şir oarecare din ( )L G a cărui lungime este mai mare decât

k şi considerăm arborele lui de derivare ca în figura 4.8. Definim un drum

într-un astfel de arbore ca fi secvenţa de noduri şi de segmente de drum

care le leagă, începând din rădăcina S şi mergând prin neterminale până la

o frunză (adică, un terminal în σ ). Lungimea drumului este numărul

acestor segmente de drum. Definim adâncimea arborelui ca fiind

lungimea cea mai mare a acestor drumuri.

Figura 4.8. Schemă de arbore de derivare pentru σ .

Considerăm, de exemplu, gramatica 0G a expresiilor aritmetice (exemplul

1.3.). Şirul ( )*a a aσ = + are arborele de derivare din figura 4.9. Exemple

de drumuri în acest arbore sunt: E-T-F-a, (de lungime 3), E-T-T-F-), (de

lungime 4), E-T-T-F-E-E-T-F-a (de lungime 8), etc. Adâncimea arborelui

este 8. Observăm că dacă şirul σ are un arbore de derivare de adâncime

d, atunci σ nu poate avea mai mult de dr simboluri (pe orice nivel,

fiecare nod poate avea cel mult r fii). Aşadar rădăcina S poate avea cel

mult r fii, 2r fii de gradul 2, etc. Cu alte cuvinte, dacă numărul de frunze

în arborele de derivare a unui şir σ este mai mare decât dr , atunci

arborele de derivare trebuie să conţină un drum de lungime mai mare

decât d.

Figura 4.9. Exemplu de arbore de derivare.

Figura 4.10. Demonstraţia teoremei 4.4. 1 2σ ατ βτ γ=

Presupunem acum că şirul σ este mai lung decât 0 1nk r= + şi considerăm

un arbore de derivare pentru σ care are cel mai mic număr de noduri. (σ

poate avea mai mult decât un singur arbore de derivare. Dacă există mai

mulţi astfel de arbori de derivare minimali, se alege unul oarecare dintre

ei.) Din cele spuse adineauri, arborele de derivare pentru σ trebuie să

conţină un drum de lungime mai mare decât 0n , adică, de lungime

0 1 2n n+ = + sau chiar mai mult (n este numărul de neterminale din G).

Acest drum conţine exact un termina, toate celelalte noduri (cel puţin 1n +

dintre ei) sunt neterminale. Aşadar, există un neterminal X care apare de

două ori în acest drum, deci arborele de derivare a lui σ este de forma

celui din figura 4.10. Unul dintre şirurile 1τ sau 2τ trebuie să fie diferit de

λ , deoarece altfel am putea elimina întreaga porţiune a arborelui de

derivare între primul X şi al doilea X, şi obţinem un arbore de derivare cu

mai puţine simboluri. Dar aceasta ne arată că (4.6) este adevărat, deci am

terminat demonstraţia. Q.E.D.

4.5. PROPRIETATEA DE ÎNCHIDERE A LIMBAJELOR

INDEPENDENTE DE CONTEXT

Am văzut în capitolul 3 (teorema 3.6) că dacă L, 1L şi 2L sunt limbaje

regulare atunci *L , L , 1 2L L+ , 1 2L L şi 1 2L L∩ sunt de asemenea regulare.

Unele, dar nu toate, dintre aceste proprietăţi sunt adevărate şi pentru

limbajele independente de context. Reamintim că *L este limbajul tuturor

şirurilor de forma 1 2 n Lσ σ σ ∈K ; L este mulţimea şirurilor care nu aparţin

lui L; 1 2L L+ este reuniunea dintre 1L şi 2L ; 1 2L L este mulţimea şirurilor de

forma 1 2 i iLσ σ σ ∈K şi 1 2L L∩ este mulţimea şirurilor care se află atât în 1L

cât şi în 2L .

Teorema 4.5. Fie L, 1L şi 2L limbaje independente de context.

Atunci limbajele *L , 1 2L L+ şi 1 2L L sunt de asemenea independente de

context.

Demonstraţie. Presupunem că L are o gramatică independentă de

context { , , , }G N S P= Σ . Definim o nouă gramatică *G astfel: Terminalele

din Σ corespund celor din G. Neterminalele sunt aceleaşi ca pentru G,

plus încă un simbol nou *S . Simbolul de start va fi atunci *S iar

producţiile vor fi tot cele din G, plus * * |S S S λ→ . Evident că* *( ) ( ( ))L G L G= şi *G este o gramatică independentă de context.

Pentru a arăta că reuniunea şi concatenarea a două gramatici

independente de context este din nou independentă de context procedăm

astfel. Fie { , , , }i i i i iG N S P= Σ o gramatică independentă de context pentru

limbajul iL , 1, 2i = . Presupunem că neterminalele din 1L sunt disjuncte

faţă de cele din 2L ; 1 2N N∩ =∅ . Pentru a construi o gramatică

{ , , , }G N S P= Σ pentru limbajul 1 2L L+ luăm 1 2Σ = Σ ∪Σ , 1 2N N N= ∪ plus

încă un simbol nou S, care este şi noul simbol de start din G, iar

producţiile sunt 1 2|S S S→ plus toate producţiile din 1P şi 2P . Evident

1 2( ) ( ) ( )L G L G L G= + . Pentru a obţine o gramatică pentru limbajul 1 2L L ,

procedăm în exact aceeaşi manieră, însă introducem producţia 1 2S S S→ în

loc de 1 2|S S S→ . Q.E.D.

Exemplu 4.8. Intersecţie a două limbaje independente de context

nu trebuie să fie independentă de context. Într-adevăr, limbajul

1 { | 0,1, 2, }n nM a b n= = K este independent de context, fie gramatica lui

|S aSb λ→ . Limbajul 2 { | 0,1, 2, }kM c k= = K este de asemenea independent

de context. Analog, limbajele 3 { | 0,1, }iM a n= = K şi 4 { | 0,1, 2, }j jM b c j= = K

sunt independente de context. Din teorema 4.5. avem că limbajele

1 1 2L M M= şi 2 3 4L M M= sunt independente de context. Limbajul, însă,

1 2L L∩ nu este independent de context. Observăm că 1 2L L∩ este limbajul

0 { | 0,1, 2, }n n nL a b c n= = K care, după cum am arătat în exemplul 4.7., nu

este independent de context.

Complementara unui limbaj independent de context nu trebuie să

fie independentă de context. Pentru aceasta, presupunem că

complementara fiecărui limbaj independent de context este independentă

de context. Atunci, date fiind două limbaje independente de context 1L şi

2L , limbajul 1 2 1 2L L L L∩ = + ar trebui să fie independent de context, ceea

ce, cum am văzut adineauri, nu este cazul. Acest raţionament este corect,

însă nu furnizează un exemplu concret. Pentru a construi un astfel de

exemplu, vom arăta că complementara limbajului 0L de mai sus este

independentă de context. Aceasta este suficient, deoarece orice limbaj

este complementara complementarei sale: L L= . Considerăm acum

limbajul 0L . Un şir σ va aparţine lui 0L (adică, nu aparţine lui 0L ) dacă

este satisfăcută una dintre următoarele condiţii:

1. σ nu este de forma i j ka b c .

2. σ este de forma i j ka b c , dar i j≠ sau j k≠ .

Fie 1K mulţimea şirurilor din *{ , , }a b c care satisfac 1 şi fie 2K mulţimea

şirurilor din *{ , , }a b c care satisfac 2; evident 0 1 2L K K= + . Este suficient să

arătăm că amândouă 1K şi 2K sunt independente de context, deoarece

limbajele independente de context sunt strâns legate de operaţia +

(teorema 4.5.). Limbajul 1K este chiar complementara unui limbaj

regular descris de expresia regulară * * *a b c . Deoarece complementara unui

limbaj regular este tot un limbaj regular (teorema 3.7.), 1K este un limbaj

regular, deci este şi independent de context. Fie 2K reuniunea a două

limbaje, aK şi bK , unde { | }i j kaK a b c i j= ≠ şi { | }i j k

bK a b c j k= ≠ :

2 1 2K M M= + . Raţionamentul ar fi complet dacă am putea arăta că ambele

limbaje aK şi bK sunt independente de context: Produce o gramatică

independentă de context pentru aK :

|||||

S AC BCA aA aPB Bb PbC cCP aPb

λλ

→→→→→

Idee este simplă: Neterminalul A va produce şiruri de forma i ja b cu i j>

iar neterminalul B va produce şiruri de foram i ja b cu i j< . Neterminalul

C produce şiruri formate doar din c-uri iar neterminalul P şiruri de foramm ma b . Deci, aK este independent de context. Raţionamentul pentru bK

este analog.

Deseori se afirmă că una dintre limitele automatelor push-down

este că ele nu pot ţine cont de mai mult decât două secvenţe infinite.

Faptul că limbajul 0L , de mai sus, nu este un limbaj independent de

context, şi astfel neacceptat de vreun automat push-down, este motivul

acelei descrieri neformale. Orice automat push-down care acceptă 0L ar

trebui să ţină cont de trei secvenţe cu lungimi arbitrare: a-uri, b-uri şi

c-uri.

PROBLEME

Construiţi în fiecare dintre problemele 1 – 7 un automat push-down

determinist care recunoaşte limbajul dat. Daţi o descriere verbală

neformală şi formală. În fiecare problemă arătaţi mişcările maşinilor

efectuate asupra şirului indicat.

1. 2{ | 0,1, 2, }n nL a b n= = K ; 1 aaaabbσ = , 2 aaabbσ =

2. { | 0,1,2, }n nL a bc n= = K ; 1 aaabcccσ = , 2 aabccσ =

3. *{ {0,1} | are mai multe 0-uri decât 1-uri}L σ σ= ∈ ; 1 0110010σ = ,

2 110010σ =

4. 2 3{ | 0,1, 2, }n nL a b n= = K ; 1 aabbbσ = , 2 ababbσ =

5. *{ { , } | are acelaşi număr de -uri şi -uri}L a b a bσ σ= ∈ ; 1 abbaabσ = ,

2 bbabaσ =

6. { | }n mL a b n m= ≠ ; 1 aaabbσ = , 2 aabaσ = , 3 aabbσ =

7. { | }i j kL a b c i j k= + = ; 1 abbcccσ = , 2 aabbcccσ =

În fiecare dintre problemele 8 – 12 construiţi un APD nedeterminist care

acceptă limbajele cu gramatica dată. Arătaţi mişcările acceptate ale

acestui APD efectuate asupra şirurilor indicate.

8. 0 1S A→ , 00 1|A A λ→ ; 00011σ =

9. 0 | 1S AB B A→ , | 0A BB→ , |1B AA→ ; 10001σ =

10. S ABC→ , |A BB λ→ , |B CC a→ , |C AA b→ ; aaabσ =

11. |E E T T→ + , * |T T F F→ , ( ) |F E a→ ; ( )*a a aσ = +

12. |S Aa bB→ , |A aA S→ , | |B b Aa λ→ ; abaσ =

13. Construiţi un APD care va traduce corect expresii aritmetice din

notaţia infixată în notaţia postfixată şi care în plus permite ridicarea

la putere. Adică, ba este denotat prin a b↑ . Exponenţiala are

precedenţa mai mare decât + şi *, adică, expresia (3 7)*5 8+ ↑ ,

însemnând în notaţia obişnuită 8(3 7)*5+ , să fie tradusă în

37 58 *+ ↑ .

14. Scrieţi următoarele expresii în notaţia postfixată:

a. (7 3*5)*(8 7*2) 1+ + +

b. (3 2)*(3*7 8)+ +

15. Convertiţi următoarele expresii în notaţia infixată (toate numerele

implicate sunt numere simple).

a. 357 *4*5+ +

b. 12 3*4 5*+ +

16. Arătaţi că următoarele limbaje nu au gramatici independente de

context.

a. 2

{ | 1, 2,3, }nL a n= = K

b. { | 0 }n m kL a b c n m k= < < <

c. { | este număr prim}pL a p=

d. { | }n n mL a b c m n= ≤

e. *{ { , , } | are un număr egal de -uri, -uri şi -uri}L a b c a b cσ σ= ∈

f. *{ | {0,1} }RL σσ σ σ= ∈ ; Rσ înseamnă inversul lui σ

17. a. Arătaţi că limbajele 21 { | , 0,1, 2, }i j jL a b c i j= = K şi

22 { | , 0,1, 2, }j i iL a b c i j= = K sunt independente de context.

b. Arătaţi că limbajul 1 2L L∩ nu este independent de context.

18. Fie L un limbaj independent de context şi fie { | }R RL Lσ σ= ∈ .

Arătaţi că RL este de asemene un limbaj independent de context.

( Rσ este inversul şirului σ .)