3.1.Automate Pushdown
-
Upload
alexandra-danci -
Category
Documents
-
view
212 -
download
0
description
Transcript of 3.1.Automate Pushdown
3
3.1. Automate Push-down
Vom introduce un nou tip de dispozitiv care s accepte limbajele I.D.C., numit automat push-downxe "automat:push-down determinist".
Un automat push-downxe "automat:push-down determinist" are, pe lng o band de intrare, i o stivxe "stiv" (o list LIFO). ntr-o astfel de stiv, intrarea i ieirea unui simbol se face numai la capul stivei. Cnd un simbol intr n stiv, simbolul care anterior a fost capul stivei devine al doilea, cel care a fost al doilea devine al treilea .a.m.d. n mod similar, cnd un simbol este scos din stiv, simbolul care anterior acestei scoateri era al doilea, ajunge n capul stivei, cel care era al treilea devine al doilea .a.m.d.
O astfel de stivxe "stiv" se poate compara cu un teanc de farfurii n care se ridic sau se pune o farfurie deasupra teancului.
Exemplul 3.1.1 S utilizm o stivxe "stiv" de "farfurii", cuplat cu un control finit pentru a recunoate o mulime neregulat.
Fie limbajul I.D.C. L={}, care nu este regulat (posibil de demonstrat acest lucru folosind lema de pompare) i fie gramatica
G=({S},{0,1,c},S,P)
unde mulimea regulilor este P=.
Pentru a recunoate limbajul L, vom utiliza un control finit cu dou stri q1 i q2 i o memorie push-down pe care vom plasa "farfurii" albastre, roii i verzi. Dispozitivul va opera dup urmtoarele reguli:
Maina pornete cu o farfurie roie pe stivxe "stiv" i cu controlul finit n starea q1.
Dac simbolul de intrare este 0 i starea este q1, dispozitivul plaseaz o farfurie albastr pe stivxe "stiv", iar dac simbolul de intrare este 1 i starea q1, atunci plaseaz o farfurie verde pe stiv i, n ambele cazuri, rmne n starea q1.
Dac intrarea este c i starea q1, i schimb starea n q2 fr a aciona asupra stivei.
Dac intrarea este 0, starea q2 i pe stivxe "stiv" se afl o farfurie albastr, scoate farfuria i rmne n q2, iar dac este 1, starea q2 i pe stiv este o farfurie verde, scoate farfuria i rmne tot n q2.
Dac dispozitivul este n starea q2 i pe stivxe "stiv" este o farfurie roie, scoate farfuria indiferent de intrare.
n alte situaii dispozitivul nu face nici o micare.
Dispozitivul accept irul de intrare dac, dup citirea lui, stiva devine goal.
Vom defini un automat push-downxe "automat:push-down determinist" ca fiind un dispozitiv format din: band de intrare, control finit i memorie push-down (stivxe "stiv"), precum n Figura 3.1.1..
Dispozitivul este nedeterminist, avnd un numr finit de anse de micare n fiecare situaie. Micrile vor fi de dou tipuri:
- tranziie cu simbol de intrare: n funcie de simbolul de intrare, de captul stivei i de starea controlului finit, sunt posibile anumite micri care constau fiecare din: o nou stare a controlului finit i un ir (posibil vid) de simboluri care nlocuiete capul stivei. Dup alegerea unei micri posibile, dispozitivul avanseaz cu un simbol pe banda de intrare.
- "-tranziie" : este similar cu micarea tip I., dar nu e utilizat nici un simbol de intrare.
Limbajul acceptat de un automat push-downxe "automat:push-down determinist" se poate defini n dou moduri:
mulimea irurilor de intrare care conduc la golirea memoriei push-down sau
mulimea irurilor de intrare pentru care automatul intr ntr-o stare final.
Cele dou tipuri de acceptri sunt echivalente.
Formal, un automat push-downxe "automat:push-down determinist" se definete prin:
Definiia 3.1.1 Un automat push-downxe "automat:push-down determinist" nedeterministxe "automat:push-down nedeterminist", M, este un sistem format din:
M = ,
unde:
Q este o mulime finit de stri
este un alfabet finit al benzii de intrare
este un alfabet finit al memoriei push-down
stare iniial
simbol de start al memoriei push-down
mulimea strilor finale
Interpretarea expresiei , unde , este aceea c automatul push-down aflat n starea q, cu a pe banda de intrare i Z n capul stivei, poate trece ntr-una din strile pi nlocuind pe Z cu i apoi avanseaz cu un simbol pe banda de intrare.
Interpretarea expresiei , unde , este aceea c automatul push-down aflat n starea q i avnd pe Z n capul stivei, indiferent de simbolul aflat pe banda de intrare i schimb starea ntr-una din strile pi i nlocuiete pe Z cu fr s avanseze pe banda de intrare.
Exemplul 3.1.2 n exemplul anterior, automatul push-down accept limbajul {} prin memorie vid (v.definiia 3.1.4). S descriem formal acest automat.
M=({q1,q2},{0,1,c},{R,A,V},,q1,R,)
Observaia 3.1.1 Automatul din Exemplul 3.1.2 este determinist pentru c are o singur posibilitate de micare la fiecare pas.
Un astfel de automat, idiferent dac este determinist sau nedeterminist, se poate i el reprezenta printr-o diagram de tranziie[23], similar cu cea pentru automatul finit, cu excepia faptului ca una dintre etichetele unui arc ntre starea p i starea q, este de forma:
(a, A BC) dac
(q, BC) ( ((p,a,A)
sau, folosind forma din [13]:
(a, A, BC) dac
(q, BC) ( ((p,a,A)
S considerm automatul push-down, definit printr-o diagram de tranziiexe "diagram:de tranziie", din figura 2.3.2, care recunoate cuvintele limbajului:
{anbn | n 0}.
Definiia 3.1.2 O configuraie instantanee este o pereche , unde i , unde cel mai din stnga simbol al lui este vrful stivei push-down, iar reprezint coninutul stivei.
Dac , , , i , atunci scriem:
a : (q,Z) (p,) (Intrarea "a" trece automatul M din (q,Z) n (p,).)
Dac pentru fiecare , i irurile , avem:
ai : (qi,i) (qi+1,i+1) , atunci scriem: a1 an : (q1,1) (qi+1,i+1)
Similar, se poate folosi descrierea instantaneexe "descrierea instantanee", constituit din tripletul i atunci scriem:
(p,w,) dac (p, ).
Definiia 3.1.3 Limbajul acceptat prin stri finalexe "Limbajul acceptat:prin stri finale" de ctre automatul M este
EMBED Equation.3.
Definiia 3.1.4 Limbajul acceptat prin stivxe "stiv" vid de ctre automatul M este
EMBED Equation.3.
Exemplul 3.1.3 S construim automatul push-down care accept limbajul {}.
M=({q1,q2},{0,1},{z0,A,B},,q1,Z0,)
Spre exemplu, irul de intrare 001100 este acceptat de automatul pushdown deoarece exist un calcul de configuraii care se finalizeaz prin golirea memoriei push-down dup citirea benzii de intrare:
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3+
,
deci 001100. Problema care apare n acest exemplu este de a determina mijlocul cuvntului de pe banda de intrare. Pentru determinarea mijlocului, singura condiie cunoscut este de a avea pe banda de intrare doi de 0 consecutivi sau doi de 1 consecutivi. ns aceast condiie nu determin n mod precis mijlocul cuvntului de intrare, situaia nefiind unic. Astfel, automatul push-down poate "bnui" c a ajuns la mijlocul cuvntului de intrare ori de cte ori apar doi de 0 sau doi de 1 consecutivi. Deci, de cte ori automatul ntlnete dou simboluri identice pe banda de intrare, are de ales ntre dou variante: "bnuiete" c aici este mijlocul i trece n starea q2, care ncepe s tearg stiva, sau "bnuiete" c nu este la mijloc i continu s memoreze n stivxe "stiv". Dac a "bnuit" corect atunci va reui s-i goleasc stiva. De aici apare nedeterminismul.
Observaia 3.1.2
a) Un automat push-downxe "automat:push-down determinist" este deterministxe "automat:push-down determinist" dac sunt ndeplinite urmtoarele condiii:
- pentru fiecare corespunztoare, nu conine mai mult de un element;
- pentru fiecare , dac atunci (aceste condiii evit situaia n care ar fi posibile att o -mutare ct i o mutare nevid, genernd astfel nedeterminism).
b) Pentru automatele push-down n general, modelul determinist i cel nedeterminist nu sunt echivalente. Acest lucru se demonstreaz n 3.9., seciune dedicat limbajelor independente de context deterministe
aiBanda de intrare
ZCapul stiveiZ0Figura 3.1.1
CONTROL
FINIT (Q)
Figura 3.2.2
q
pq
0, A AA
1, A
srpq
rpq
1, A
, Z0
0, Z0 AZ0
, Z0
_1264673499.unknown
_1264673515.unknown
_1264673523.unknown
_1264673527.unknown
_1264673531.unknown
_1264673533.unknown
_1264673534.unknown
_1264673535.unknown
_1264673532.unknown
_1264673529.unknown
_1264673530.unknown
_1264673528.unknown
_1264673525.unknown
_1264673526.unknown
_1264673524.unknown
_1264673519.unknown
_1264673521.unknown
_1264673522.unknown
_1264673520.unknown
_1264673517.unknown
_1264673518.unknown
_1264673516.unknown
_1264673507.unknown
_1264673511.unknown
_1264673513.unknown
_1264673514.unknown
_1264673512.unknown
_1264673509.unknown
_1264673510.unknown
_1264673508.unknown
_1264673503.unknown
_1264673505.unknown
_1264673506.unknown
_1264673504.unknown
_1264673501.unknown
_1264673502.unknown
_1264673500.unknown
_1264673483.unknown
_1264673491.unknown
_1264673495.unknown
_1264673497.unknown
_1264673498.unknown
_1264673496.unknown
_1264673493.unknown
_1264673494.unknown
_1264673492.unknown
_1264673487.unknown
_1264673489.unknown
_1264673490.unknown
_1264673488.unknown
_1264673485.unknown
_1264673486.unknown
_1264673484.unknown
_1264673474.unknown
_1264673478.unknown
_1264673481.unknown
_1264673482.unknown
_1264673479.unknown
_1264673476.unknown
_1264673477.unknown
_1264673475.unknown
_1264673470.unknown
_1264673472.unknown
_1264673473.unknown
_1264673471.unknown
_1264673468.unknown
_1264673469.unknown
_1264673467.unknown