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 σ .)
Top Related