1

Formális nyelvek

Széchenyi István Egyetem

6. előadás Környezetfüggetlen nyelvtanok/1.

Dr. Kallós Gábor

2013–2014 11

Formális nyelvek


Tartalom

Bevezetés

Nyelvek és nyelvtanok egy- és többértelműsége Bal- és jobboldali levezetések Levezetési fák

A fák magassága és határa A derivációk és a levezetési fák kapcsolata

Veremautomaták

CF nyelv példák

Felépítés, konfigurációk és átmenetek Szavak felismerése, felismert nyelv Az elfogadó állapottal és az üres veremmel felismerő automaták ekvivalenciája

Feladatok

2

Formális nyelvek


Bevezetés, példa

Eml.: környezetfüggetlen (CF) nyelvtan: 2-típusú, csak A → α alakú levezetési szabályai lehetnek

A helyettesítési szabály a környezettől függetlenül bárhol alkalmazható

Itt nagyobb a szabadság a helyettesítési szabályoknál, mint a reguláris nyelveket generáló nyelvtanoknál

Példa

Ez viszont több olyan problémát is felvet, amivel eddig még nem találkoztunk Legyen Gar = (N, T, P, S), ahol N = {E, T, F} T = {+, *, (, ), a} S=E P = {E → E + T | T, T → T *F | F, F → (E) | a} Megj.: Itt megszegtük a korábbi konvenciót a nemterminális és terminális jelek használatáról, de ez „szándékos”, a szimbólumoknak itt fontos szerepük van, ezek kellenek (E – expression, T – term, F – factor; az a pedig egy azonosító) A nyelvtan egy additív és egy multiplikatív operátort tartalmazó, és a zárójelezést megengedő aritmetikai kifejezéseket generálja (van precedencia) Be lehetne vezetni hasonlóan a –, / és ^ műveleteket, ill. előjeleket is, egy igazi számítástechnikai nyelv aritmetikai kifejezéseket generáló CF nyelvtana tartalmazza ezeket is (de a mi céljainkra most ez kissé szegényes nyelv is elég)

3

Formális nyelvek


CF nyelv példa Példa (folyt.) (Eml.: P = {E → E + T | T, T → T *F | F, F → (E) | a}) A nyelvnek eleme az a + a*a jelsorozat, hiszen egy levezetése

E ⇒ E + T ⇒ E + T*F ⇒ E + T*a ⇒ E + F*a ⇒ E + a*a ⇒ T + a*a ⇒ F + a*a ⇒ a + a*a

Okoz-e a több levezetés megléte zavart? A levezetéseket egy rendezett, irányított gráffal (fával) ábrázoljuk

E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ a + T ⇒ a + T*F ⇒ a + F*F ⇒ a + a*F ⇒ a + a*a

De a kifejezést másként is le lehet vezetni

A fa gyökere a mondatszimbólum Minden csomópontból annyi él (olyan sorrendben) fut ki, amennyi a szabály jobboldalán található szimbólumok száma, és a kifutó élek végén a jobboldal megfelelő szimbólumai találhatók Az egy csomópontból kiinduló élek sorrendje kötött, nem változtatható meg Minden levezetésnek egy levezetési fa felel meg, de egy levezetési fához több levezetés is tartozhat (!)

Ha egy kifejezéshez pontosan egy levezetési fa tartozik, akkor a nyelvtant egyértelműnek mondjuk

Nevezetes levezetések: mindig a legbaloldalibb nemterminális szimbólumot helyettesítjük (bal (oldali) levezetés); hasonlóan – jobb (oldali) levezetés (lásd fent) 4

Formális nyelvek


CF nyelv példa, elemzés

Megjegyzések

Vigyázat, a levezetési fa nem a nyelvtanhoz tartozik egyértelműen, hanem a levezetéshez! (Egy nyelvtannak sok levezetési fája van/lehet) Az egyes csomópontokhoz tartozó részfákat (a leveleket is) szintaktikai egységeknek nevezzük

Példa (folyt.) (Eml.: P = {E → E + T | T, T → T *F | F, F → (E) | a}) Most módosítjuk a nyelvtant, legyen P = {E → E + E | E *E | (E) | a}

Ez a nyelvtan (Gar2) ugyanazt a nyelvet generálja, mint fenti párja

Két különböző levezetés az a + a*a jelsorozatra E ⇒ E + E ⇒ E + E*E ⇒ a + E*E ⇒ a + a*E ⇒ a + a*a E ⇒ E*E ⇒ E*a ⇒ E + E*a ⇒ E + a*a ⇒ a + a*a

Itt azonban két különböző levezetési fa adható meg!

A két levezetés tehát lényegesen eltérő

5

Formális nyelvek


Egy- és többértelműség

A természetes nyelvekre nagyon jellemző a többértelműség/többalakúság Például: „Láttam Zsókát egy távcsővel”, lehet

Zsóka vitt egy távcsövet, és én láttam Én néztem Zsókát távcsővel messziről

Itt a szövegkörnyezet vagy a beszédhelyzet segít eldönteni a helyes jelentést

Egyszerű példák, amikor a Word helyesírás-ellenőrzője nem jelez:

A fordítóprogramoktól ilyet nem nagyon várhatunk… Be nem fejezet, fejezett Jelenjen megy, meg Nem sok szó eset, esett

Feladatok

Mutassuk meg, hogy a G2 = ({S}, {2, +, *}, {S → S + S, S → S*S, S → 2}, S) nyelvtanban a 2 + 2*2 szónak két lényegesen különböző levezetése és két levezetési fája van! Milyen eredményt ad a kifejezésre ezekben az esetekben a fordító? A „csellengő else” probléma (nem egyértelmű, hogy az else melyik feltételehez tartozik): if a then if b then do else print

Milyen megoldásokat kínálnak erre a problémára az általunk használt programozási nyelvek?

6

Formális nyelvek



Ha pusztán csak azt vizsgálnánk, hogy generálható-e valamely jelsorozat egy adott nyelvtannal, akkor az eredeti és a módosított nyelvtan egyenértékű (lenne) De a számítástechnikai nyelvészet szempontjából nem közömbös, hogy milyen szintaktikai egységeken keresztül jutottunk el a levezetés során a mondathoz (!)

A számítástechnikai nyelvészetben (automatizált működés) a nem egyértelmű nyelvtanok lényegében használhatatlanok Gar2-nél az egy- és többértelműséget nyelvtanhoz, és nem a nyelvhez kapcsoltuk Vajon mindig ez a helyzet, vagy lehet a többértelműség nyelvi tulajdonság?

Utolsó példáinkban (Gar2 és G2) nagyon fontos lenne tudni, hogy melyik műveletet kell előbb elvégezni, az összeadást vagy a szorzást!

Vá.: Léteznek olyan nyelvek, amelyekről bizonyítható, hogy nem lehet egyértelmű nyelvtannal generálni Ekkor a többértelműség nyelvi tulajdonság (azaz: nincs minden CF nyelvnek egyértelmű nyelvtana)

Tehát: az egy- és többértelműség tartozhat nyelvhez és nyelvtanhoz is Példa (nem egyértelmű nyelv; csak a helyettesítési szabályokat soroljuk):

S → aAbX | YbCc A → aAb | ab C → bCc | bc X → cX | c Y → aY | a Ez a nyelvtan az L = aibicj ∪ ajbici nyelvet generálja Ezzel a nyelvtannal az aibici alakú kifejezések két lényegesen különböző levezetéssel állíthatók elő Igazolható, hogy nincs olyan egyértelmű CF nyelvtan, ami ezt a nyelvet generálja 7

Formális nyelvek



Az egyértelműség eldöntése: Sajnos nincs olyan módszer, amelynek segítségével általánosan, minden esetre alkalmazhatóan meg lehetne mondani, hogy egy CF nyelvtan vagy nyelv egyértelmű-e Persze ettől még sok konkrét esetben a probléma megoldható (egyedi tulajdonságok vagy szerencsés ötletek felhasználásával)

Visszatekintés: Felmerül-e egyáltalán az egyértelműség/többértelműség kérdése a reguláris nyelveknél? Itt a levezetési fa nagyon egyszerű, csupán egy szárból áll, amelynek jobb- ill. baloldalán vannak levelek attól függően, hogy bal- vagy jobbreguláris nyelvtanról van-e szó Egy levezetési fához itt csak egy levezetés tartozik, ami abból nyilvánvaló, hogy minden mondatszerű formában csak egyetlen nemterminális szimbólum szerepel

Például a Gar nyelvtan egyértelműsége igazolható

(Nemdeterminisztikus automaták mintájára lehet: nemdet. nyelvtan, ekkor egy kifejezésnek több, lényegesen eltérő levezetése van; de: minden reguláris, nemdet. nyelvtanhoz szerkeszthető vele egyenértékű, determinisztikus nyelvtan – automatákkal)

Tehát: Minden reguláris nyelv egyértelmű, és szerkeszthető hozzá egyértelmű nyelvtan 8

Formális nyelvek


Bal- és jobboldali levezetések

Legyen G = (N, T, P, S) egy tetszőleges környezetfüggetlen nyelvtan Definíciók Az α0 ⇒ α1 ⇒ α2 ⇒ … ⇒ αn alakú kifejezéseket levezetéseknek (derivációknak) hívjuk Ha a deriváció során minden i = 1, 2, …, n esetén αi-t úgy kapjuk, hogy αi – 1-ben a bal oldalról nézve legelső nemterminálist helyettesítjük egy rá vonatkozó szabály jobb oldalával, akkor a derivációt bal (oldali) derivációnak hívjuk, és rá az α0 ⇒l α1 ⇒l α2 ⇒l … ⇒l αn jelölést használjuk. Ha egy deriváció minden lépésében a jobbról nézve legelső nemterminálist helyettesítjük, akkor jobb (oldali) derivációról beszélünk, ennek jelölése α0 ⇒r α1 ⇒r α2 ⇒r … ⇒r αn. Továbbá, ha α olyan, hogy S ⇒* α, akkor α-t mondatformának nevezzük Hasonlóan, ha S ⇒l* α (ill. S ⇒r* α) áll fent, akkor α-t bal (ill. jobb) mondatformának nevezzük Megj.: Minden mondatforma egy speciális (N ∪ T)*-beli szó (lásd még: 1. slidesor.) Feladat: Nézzük meg az előző fóliákon, hogy melyik levezetés milyen típusú, ill. milyen mondatformát állít elő!

Vigyázzunk arra, hogy a bal oldalról első, második, … szabály következetes alkalmazása általában nem eredményez bal (oldali) levezetést

A CF nyelvek (nyelvtanok) fontos tulajdonsága, hogy a levezetések fa alakban ábrázolhatók

Ez népszerűségükben is központi szerepet játszik 9

Formális nyelvek


Levezetési fák

Definíció Legyen X ∈ (N ∪ T). Az X gyökerű derivációs fák halmazán címkézett, rendezett fák legszűkebb olyan DX halmazát értjük, amelyre teljesülnek az alábbi feltételek:

Ha X ∈ T, akkor a 2. és 3. feltételek soha nem teljesülnek, ekkor tehát DX = {X} Megjegyzések

Az a fa, amelynek egyetlen szögpontja (csak gyökere) van, és annak címkéje X, eleme DXnek (ezt a fát X-szel jelöljük) Ha X → λ ∈ P, akkor az a fa, amelynek gyökere X-szel van címkézve, és gyökerének egyetlen leszármazottja van, aminek címkéje λ, eleme DX-nek (ezt a fát X[λ]-val jelöljük) Ha X → X1X2 … Xn ∈ P és t1 ∈ DX1, t2 ∈ DX2, …, tn ∈ DXn (gyermek fák), akkor az a fa, amelynek gyökere X-szel van címkézve, és a gyökérből n él indul rendre a t1, t2, …, tn fák gyökeréhez, eleme DX-nek (ezt a fát X[t1, t2, …, tn]-nel jelöljük)

A derivációs fa levélelemeihez terminális vagy nemterminális szimbólumokat, közbülső csúcsaihoz pedig nemterminális jeleket rendelünk Ha minden levélelem terminális, akkor befejezett levezetésről beszélünk A levezetési fákat szintaxisfának is nevezzük (szintaktikai elemzés)

Feladatok

Rajzoljuk le a definícióban szereplő levezetési fákat! Rajzoljuk le a következő módon adott levezetési fákat (a Gar nyelvtanhoz): t1 = E[T[T[F], *, F[(, E, )]]] t2 = F[(, E[E[T[F[a]]], + , T[F[a]]], )] Rajzoljuk le ugyanezen nyelvtanhoz az a*(a + a) + a levélelemeket tartalmazó levezetési fát! (Cs. Z. 32. old.) 10

Formális nyelvek


Levezetési fák

Definíció Legyen t egy X gyökerű levezetési fa. A t fa magasságát h(t)-vel, határát pedig fr(t)-vel jelöljük és az alábbi módon definiáljuk:

Azaz: Egy t levezetési fa esetén h(t) a t-ben levő olyan utak hosszának a maximuma, amelyek t gyökerétől annak valamely leveléig vezetnek, fr(t) pedig az az (N ∪ T)*beli szó, amelyet t leveleinek balról jobbra történő leolvasásával kapunk Megj.: h(t)-t a levezetési gráf mélységének is nevezzük Példa Az előző feladatban szereplő t1 és t2 fákra h(t1) = 3, fr(t1) = F*(E), h(t2) = 5 és fr(t2) = (a + a) Feladatok

Ha t = X, akkor h(t) = 0 és fr(t) = X Ha t = X[λ], akkor h(t) = 1 és fr(t) = λ Ha t = X[t1, t2, …, tn], akkor h(t) = 1 + max{ h(ti) | 1 ≤ i ≤ n} és fr(t) = fr(t1) fr(t2) … fr(tn).

Határozzuk meg az előző oldalakon szereplő további levezetési fák határát és magasságát! Térjünk vissza az 1. slidesor levezetési fáira (41. old.), és ott is végezzük el ugyanezt a feladatot (2-es, 2.5-es, 3-as típusú nyelvtanok) Adjunk meg az előző példák alapján 0, 1 és 2 magasságú levezetési fákat!

A levezetések és a levezetési fák közötti szoros kapcsolatot mutatja a következő tétel 11

Formális nyelvek


Levezetési fák

Tétel: Tetszőleges X ∈ (N ∪ T) és α ∈ (N ∪ T)* esetén X ⇒* α akkor és csak akkor áll fent, ha van olyan t ∈ DX levezetési fa, amelyre fr(t) = α

Bizonyítás a) ⇒ A feltétel szerint ekkor X ⇒n α teljesül valamely n ≥ 0-ra. A jobb oldal igazolása: n szerinti indukcióval. Az n = 0 esetben X = α. Itt az egyetlen szögpontú t = X fa megfelelő, mert erre t ∈ DX és fr(t) = X (= α). Legyen most n ≥ 1, és tfh. az állítás minden n-nél nem nagyobb számra teljesül. Tegyük fel továbbá, hogy X ⇒n + 1 α. Ekkor X ⇒ X1X2 … Xk ⇒n α1α2…αk = α, ahol teljesülnek a következők: X → X1X2 … Xk egy P-beli szabály, és minden 1 ≤ i ≤ k esetén Xi ⇒ni αi, ahol ni ≤ n (ezen felül n = n1 + n2 + … + nk is teljesül). Mivel ni ≤ n, az indukciós feltevés miatt minden 1 ≤ i ≤ k-ra van olyan ti ∈ DX, hogy fr(ti) = αi. Legyen t = X[t1, t2, …, tk]. A levezetési fa definíciója miatt t ∈ DX, a magasság és a határ definíciója miatt pedig fr(t) = fr(t1) fr(t2) … fr(tk) = α1α2…αk = α. b) ⇐ Tfh. az X gyökerű t derivációs fára teljesül, hogy fr(t) = α. A bal oldal igazolása: t magassága szerinti indukcióval. Legyen h(t) = 0. Ekkor t = X, tehát fr(t) = α = X. Így X ⇒* α (= X) teljesül. Legyen most h(t) = n + 1, és tfh. az állítás minden n-nél nem magasabb derivációs fára teljesül. A magasság és a határ definíciója miatt ekkor t = X[t1, t2, …, tn], valamilyen k ≥ 1-re és t1 ∈ DX1, t2 ∈ DX2, …, tn ∈ DXn levezetési fák esetén, és a derivációs fa definíciója miatt X → X1X2 … Xk ∈ P is teljesül. Vezessük be az αi = fr(ti) jelölést minden 1 ≤ i ≤ k-ra. Ekkor egyrészt α = α1α2…αk, másrészt az indukciós feltevés szerint minden 1 ≤ i ≤ k-ra Xi ⇒* αi. Így X ⇒ X1X2 … Xk ⇒* α1α2…αk = α.

12

Formális nyelvek


Levezetési fák

Megjegyzések

Az előző tételben szereplő X ⇒* α levezetéshez általában nem csak egy olyan X gyökerű levezetési fa létezik, amelynek határa α. Példa: Legyenek az A → aB | Ab A→a B→b szabályok egy CF nyelvtan szabályai. Ekkor A ⇒* ab. Ugyanakkor a t1 = A[a, B[b]] és t2 = A[A[a], b] fákra fr(t1) = ab és fr(t2) = ab.

Feladat: Rajzoljuk le ezeket a fákat!

A tételben szereplő t fából az persze következik, hogy X ⇒* α fennáll, de az nem, hogy a levezetés lépései egyértelműen meghatározottak Példa: A t1 = E[T[T[F], *, F[(, E, )]]] fa határa F*(E); ez kétféle módon is megkapható E ⇒ T ⇒ T*F ⇒ F*F ⇒ F*(E) E ⇒ T ⇒ T*F ⇒ T*(E) ⇒ F*(E)

Egy derivációs fa által reprezentált levezetések egy ekvivalencia-osztályt alkotnak

Mindegyikben ugyanaz a mondatforma (szó) van levezetve Az ugyanott megjelenő ugyanolyan nemterminálisra ugyanazt a szabályt alkalmazzák

A szabályalkalmazások sorrendje lehet különböző

Ez a példákban jól látható

13

Formális nyelvek


Levezetési fák

Célunk a továbbiakban: minden ekvivalencia-osztályból kiemelni egy reprezentánst, legyen ez például a legbaloldalibb levezetés (ez jó, és mindig létezik)

Egy „legbaloldalibb” levezetés persze mindig kijelölhető a fában…

Gond: A legbaloldalibb levezetés nem biztos, hogy tényleg bal (oldali) levezetés! (És ugyanaz persze a legjobboldalibbra is érvényes)

Készen vagyunk? …

Ha X ⇒l* α, akkor X ⇒* α is fennáll, mivel minden bal (oldali) levezetés egyúttal levezetés is Ugyanaz érvényes a jobb (oldali) levezetésekre is De fordítva ez már nem igaz, X ⇒* α-ból nem következik, hogy X ⇒l* α is fenáll

Példa: A Gar nyelvtan esetén E ⇒* E + F + T teljesül, de E ⇒l* E + F + T és E ⇒r* E + F + T nem áll fent Feladat: Ellenőrizzük a példát!

Ha csak terminális szavakat engedünk meg a levezetési fa leveleiben, akkor a kijelentés már megfordítható

Azaz: teljes, befejezett fa kell!

14

Formális nyelvek


Levezetési fák

Állítás: Tetszőleges X ∈ (N ∪ T) és w ∈ T* esetén a következő három állítás ekvivalens: X ⇒* w X ⇒l* w X ⇒r* w

Bizonyítás A bal és a jobb (oldali) levezetések között fennálló szimmetria miatt elegendő az első és a második állítás ekvivalenciáját igazolni. (Tudjuk: Ha X ⇒l* w, akkor X ⇒* w is fennáll, mivel minden bal (oldali) levezetés egyúttal levezetés is.) Fordítva, tfh. X ⇒* w. Ekkor X ⇒n w teljesül valamely n ≥ 0-ra. A másik oldal igazolása: n szerinti indukcióval. Az n = 0 esetben X = w, ami csak úgy lehet, hogy X ∈ T. Így nyilvánvaló, hogy X ⇒l* w. Tegyük fel most, hogy a következtetés teljesül minden n-nél nem nagyobb számra, és legyen X ⇒n + 1 w. Ekkor ez a deriváció felírható X ⇒ X1X2 … Xk ⇒n w1w2…wk = w alakban, ahol k ≥ 1, X → X1X2 … Xk ∈ P és minden 1 ≤ i ≤ k-ra teljesül Xi ⇒ni wi, ahol ni ≤ n. Így az indukciós feltevés miatt Xi ⇒lni wi is fennáll. Ekkor viszont X ⇒l X1X2X3 … Xk ⇒l w1X2X3 … Xk ⇒l w1w2X3 … Xk ⇒l … ⇒l ⇒l w1w2w3 … wk = w.

A G nyelvtan által generált nyelv fogalma a jelen részben definiált fogalmak segítségével is megadható

L(G) = {w ∈ T* | S ⇒* w} = {w ∈ T* | S ⇒l* w} = {w ∈ T* | S ⇒r* w} L(G) = {fr(t) | t ∈ DS, fr(t) ∈ T*} 15

Formális nyelvek


Veremautomaták

Célunk a CF nyelveket felismerő automaták bevezetése Ha a véges automata definíciójában elhagyjuk az állapothalmaz végességére vonatkozó feltételt, akkor a (véges ábécéjű) végtelen automata fogalmához jutunk

Verem használata az automatáknál

Így ez túl általános, ezért speciális fajtájú végtelen automatákat vezettek be Veremautomata eredetileg: aritmetikai kifejezések számítógéppel történő kiértékelése (1960-as évek) (Az implementáló szoftvert levédték szabadalommal, ez volt az első védett szoftvertermék az USA-ban)

Máshol is használjuk: verem, mint programozási adatszerkezet

Példa: Hanoi tornyai (C-szerű pszeudokód)

Tipikusan rekurzív programozási feladatoknál A forráspálcáról (source) a célpálcára (target) kell pakolni Megoldás: Segédpálcát (help) vetünk be

Az egyes rudakhoz mint veremhez tudunk hozzáférni A rekurzív hívások szintén egy verem segítségével hajtódnak végre

16

Formális nyelvek


Veremautomaták Logikai felépítés Veremmemória: pozíciókra felosztott, egyirányban végtelen szalag

Minden pozícióba egy-egy jel írható A kiolvasás (amely egyúttal törlés is) a bevitelhez képest fordított sorrendben történik (LIFO: Last In First Out)

A verem alján kezdetben csak egy speciális szimbólum van (kezdőszimbólum) A vermet legtöbbször függőleges elrendezésűnek képzeljük

Vízszintes elrendezésnél a legelső betű a legfelső, a szalag egyik irányba végtelen

Input szalag: ezen kapja meg az automata a véges bemenő szót

A belső tartalomhoz közvetlenül nem férünk hozzá, mindig csak a verem tetején levő elemet tudjuk kiolvasni Szintén a verem tetejére helyezhetünk el újabb elemet

Ezt betűnként tudja leolvasni Az input szalag lehet üres is (λ szó)

Véges, iniciális nemdeterminisztikus (kimenő jel nélküli) automata

Ez a veremautomata véges vezérlője Diszkrét időskála mentén haladva történik a működés 17

Formális nyelvek


Veremautomaták

A működés kezdetén…

A veremben csak a kezdő veremszimbólum van Az input szalag olvasófeje a szalag első betűjére mutat

A (veremautomatához tartozó) véges automata a kezdő állapotában van

A mozgás során

Új állapotba kerülünk (ez a régivel megegyező is lehet), Az olvasófej egy szimbólummal továbblép (kivéve λ szó), A verem tetejére új jelsorozat íródik be

A verem tetején eddig levő szimbólum „megsemmisül” (ha meg akarjuk tartani: vissza kell írni a verembe)

Ha a véges automata a teljes input elolvasásával eljut egy végállapotba, akkor a veremautomata megáll

Ha a szalagon csak az üres szó van, akkor ezt érzékeli

Ekkor a veremautomata az input szót elfogadta (ugyanez az üresszóra is lehet) (Lehetséges elfogadás üres veremmel is, lásd később)

A veremautomata akkor is megáll, ha a véges automata olyan állapotban van, amelyhez nem tartozik egyetlen alkalmas átmenet sem

Nincs lehetséges átmenet a verem tetején levő jel figyelembe vételével és az input olvasásával a véges automatában

18

Formális nyelvek


Veremautomaták

A nemdeterminisztikus veremautomata egy input szót elfogad, ha van olyan futása, hogy a bemenő szót elfogadja (emellett lehet persze olyan is, amellyel nem) Egy veremautomata kétféleképpen ismerhet fel egy nyelvet: végállapotokkal vagy üres veremmel

Elfogadó állapotok kellenek ill. nem kellenek (lásd később)

Veremautomata belső állapota: egy pár, ami a verem tartalmát és a véges automata belső állapotát tartalmazza (a veremautomata végtelen)

Az elvileg végtelen (pontosan: véges, de nem korlátos) befogadóképességű veremmemória összes lehetséges tartalma eredményez végtelen sok állapotot

CF nyelvet nem lehet korlátos befogadóképességű veremmemóriával elemezni (a mondat első fele nagyon hosszú lehet, lásd példák lent)

A veremautomata kifejező ereje nagyobb a véges automatákénál

Megj.: A veremautomatának több definíciója is ismert

Push-down automaton: az új infót a régi tetejére írjuk, a régi „lenyomódik”, csak a legfelső adatot lehet kiolvasni – ekkor ki is vesszük (Ezt az automatát tanuljuk) Stack automaton: az új infót itt is a régi tetejére írjuk, de kivétel nélkül lehet olvasni belőle, és nemcsak a verem tetejéről (Nem ezt az automatát tanuljuk; ennek jelentősége kisebb)

De: a stack memory a veremmemória angol neve…

19

Formális nyelvek


Veremautomaták

Definíció: Veremautomatának (push-down automatának) nevezzük a P = (Q, Ʃ, Γ, δ, q0, Z0, F) rendszert, ahol Q egy nem üres, véges halmaz, az állapotok halmaza, Ʃ az input ábécé (szalag ábécé), Γ a veremábécé, q0 ∈ Q a kezdőállapot, Z0 ∈ Γ a verem kezdőszimbólum (kezdőjel), F ⊆ Q a végállapotok halmaza, δ : Q × (Ʃ ∪ {λ}) × Γ → P(Q × Γ*) az átmenetfüggvény (mozgási szabályok halmaza) Megjegyzések

Valamennyi fenti halmaz véges, hiszen egyébként nem lehetne véges módon leírni a nyelvet Ʃ helyett T, Γ helyett Z, δ helyett d jelölés is használatos; a P = (Q, T, Z, q0, Z0, δ, F) megadás is szokásos A végállapot halmaz az üres vermes felismerő automatánál kiesik (!) A P név a push-down automatából rövidült A δ : definíciójában szereplő P szimbólum a hatványhalmaz jelölése; (Q × Γ*) részhalmazaiba képezünk A veremautomata alapvetően (további korlátozások nélkül) nemdeterminisztikus

Az átmenet folyamata (a δ függvény működése)

Tetszőleges q ∈ Q állapot, a ∈ (Ʃ ∪ {λ}) input és a verem tetején lévő Z ∈ Γ szimbólum esetén legyen δ (q, a, Z) = {(q1, α1), (q2, α2), …, (qn, αn)}, valamilyen n ≥ 0-ra, q1, q2, …, qn ∈ Q állapotokkal és α1, α2, …, αn ∈ Γ* veremszimbólumokkal. (n = 0 eset: a képhalmaz üres.) Az automata a q állapotból az a input hatására (ez lehet λ is) átmegy valamelyik qi állapotba, a verem tetején levő Z-t törli, és beírja a verembe αi-t (ha ez λ, akkor nem ír be semmit, ekkor a veremben eggyel kevesebb szimbólum marad).

20

Formális nyelvek


Veremautomaták

Definíció: A C = Q × Ʃ* × Γ* halmazt a P konfigurációi halmazának nevezzük

Egy (q, w, γ) ∈ C konfiguráció jelentése az, hogy P a q állapotban van, a w ∈ Ʃ* input szót kapja (még nem fel nem dolgozott input rész), és vermének tartalma γ

Az input szó feldolgozása: egy lépésben egy betűt, vagy λ-t olvas be (ekkor nincs az input szóban továbblépés) Ha γ = Z1Z2 … Zn, akkor a veremnek n cellája van (mindegyik cellában csak egy szimbólum lehet), és Z1 áll a verem tetején A konfigurációnál a következő input szimbólum és a verem tetején álló szimbólum is feltüntethető, ekkor (q, aw, Zγ) írandó

Átmeneti reláció: a konfigurációk közti átmenetet írja le

Megj.: Ʃ* × Q × Γ* megadás is használatos

Ezek Descartes-szorzatán értelmezett Egy konfigurációból az automata a δ függvény definíciója szerint egy vagy több másik konfigurációba léphet tovább

Definíció: A 1P ⊆ C × C átmeneti relációt a következőképpen definiáljuk tetszőleges p, q ∈ Q, a ∈ (Ʃ ∪ {λ}), w ∈ Ʃ*, Z ∈ Γ és α, γ ∈ Γ*-ra (q, aw, Zγ) 1P (p, w, αγ) akkor és csak akkor áll fent, ha (p, α) ∈ δ (q, a, Z) Az a = λ esetben az inputban nincs előrehaladás, ekkor az automata λ-mozgást végez (Ábrák: F. Z. 44.) Megjegyzések

Ha nem akarjuk kihangsúlyozni az automata nevét, akkor 1 is használható A 1 operátor (reláció) helyett használható a w jelölés is 21

Formális nyelvek


Veremautomaták

Konfigurációk sorozata

Mint korábban: bevezetjük 1*-ot Értelmezhető 1n is: k0 1 k1 1 k2 1… 1 kn

Példa (determinisztikus veremautomata; végállapottal fogad el, B. I. 106.) (Eml.: δ : Q × (Ʃ ∪ {λ}) × Γ → P(Q × Γ*) az átmenetfüggvény C = Q × Ʃ* × Γ* a konfigurációs halmaz)

Leírása és működése δ(q0, a, Z0) = (q1, aZ0) δ(q0, b, Z0) = (q1, bZ0) δ(q1, a, a) = (q1, aa) δ(q1, b, a) = (q1, ba) δ(q1, b, b) = (q1, bb) δ(q1, a, b) = (q1, ab) δ(q1, c, a) = (q2, a) δ(q1, c, b) = (q2, b) δ(q2, a, a) = (q2, λ) δ(q2, b, b) = (q2, λ) δ(q2, λ, Z0) = (q3, Z0) F = {q3} Elemzendő mondat: aabacabaa Induló konfiguráció: (q0, aabacabaa, Z0) A konfigurációk sorozata: (q0, aabacabaa, Z0) 1 (q1, abacabaa, aZ0) 1 (q1, bacabaa, aaZ0) 1 1 (q1, acabaa, baaZ0) 1 (q1, cabaa, abaaZ0) 1 (q2, abaa, abaaZ0) 1 1 (q2, baa, baaZ0) 1 (q2, aa, aaZ0) 1 (q2, a, aZ0) 1 (q2, λ, Z0) 1 1 (q3, λ, Z0) Így az automata a jelsorozatot elfogadta, hiszen minden input szimbólumot feldolgozott, és elfogadó állapotba került Megj: Az automata a wcw–1 alakú szavakat fogadja el 22

Formális nyelvek


Veremautomaták

Példa (nemdeterminisztikus veremautomata; végállapottal fogad el)

Leírása és működése δ(q0, a, Z0) = (q1, aZ0) δ(q0, b, Z0) = (q1, bZ0) δ(q1, a, a) = (q1, aa) | (q2, λ) δ(q1, b, a) = (q1, ba) δ(q1, a, b) = (q1, ab) δ(q1, b, b) = (q1, bb) | (q2, λ) δ(q2, b, b) = (q2, λ) δ(q2, a, a) = (q2, λ) δ(q2, λ, Z0) = (q3, Z0) F = {q3} Eltérés az előző automatától: a c szimbólum kiesik (nem látjuk, hol a szó közepe) Elemzendő mondat: abbaabba A konfigurációk sorozata (első kör): (q0, abbaabba, Z0) 1 (q1, bbaabba, aZ0) 1 (q1, baabba, baZ0) 1 (? – két választási leh.) A (q2, λ) ágon megyünk tovább: (q1, baabba, baZ0) 1 (q2, aabba, aZ0) 1 (q2, abba, Z0) 1 (? – nincs tovább) Lehetőségek: vagy nem a nyelv mondatával dolgozunk, vagy rossz irányba indultunk el Visszatérés, és a (q1, bb) ágon megyünk tovább: (q1, baabba, baZ0) 1 (q1, aabba, bbaZ0) 1 (q1, abba, abbaZ0) 1 (? – két választási leh.) A (q1, λ) ágon megyünk tovább: (q1, abba, abbaZ0) 1 (q2, bba, bbaZ0) 1 (q2, ba, baZ0) 1 (q2, a, aZ0) 1 1 (q2, λ, Z0) 1 (q3, λ, Z0) Az automata a jelsorozatot elfogadta, tehát ez a szó az automata nyelvének egy mondata

Megj: Az automata a ww–1 alakú szavakat fogadja el

Nemdeterminisztikus automatánál (a döntéshez) minden lehetséges mozgássorozatot meg kell nézni

23

Formális nyelvek


Veremautomaták

Definíció: A P veremautomata által végállapotokkal felismert nyelven az Lf(P) = {w ∈ Ʃ* | (q0, w, Z0) 1* (q, λ, γ), ahol q ∈ F és γ ∈ Γ*} nyelvet értjük

Tehát: végállapotokkal P azon w input szavakat ismeri fel, amelyek hatására a q0 kezdőállapotból a verem kezdeti Z0 tartalma mellett az automata valamely q végállapotba kerül. A veremben végül maradhat valamilyen γ tartalom. Másként (B. I.): Azok a w jelsorozatok a nyelv mondatai, amelyek a kezdőállapottal és a verem kezdeti tartalmával olyan konfigurációt alkotnak, amelyből tetsz. számú lépésben elérhető egy olyan konfiguráció, ahol már nincs olvasásra váró jelsorozat (ez az üres jelsorozat), és az állapot elfogadó. A verem tartalma érdektelen.

Az elfogadás feltételét köthetjük a verem üres voltához is Definíció: A P veremautomata által üres veremmel felismert nyelven az Le(P) = {w ∈ Ʃ* | (q0, w, Z0) 1* (q, λ, λ), ahol q ∈ Q} nyelvet értjük

Tehát: üres veremmel P azon w input szavakat ismeri fel, amelyek hatására a q0 kezdőállapotból a verem kezdeti Z0 tartalma mellett P verme kiürül. F-nek ilyenkor nincs szerepe – közömbös, hogy a folyamat végén elfogadó állapotban vagyunk-e

F akár a definiáló rendezett hetesből is elhagyható

De: az üres veremmel elfogadó automatának is végig kell olvasnia a jelsorozatot!

(Ábrák: F. Z. 45–46.) Egy konkrét veremautomata esetén a végállapottal, ill. az üres veremmel elfogadott nyelvek (nagyon) különbözhetnek egymástól – fontos rögzíteni, hogy milyen módon akarjuk használni az automatát (!) 24

Formális nyelvek


Veremautomaták

Az automata működésének rajzos bemutatása Ábrázolnunk kell az állapotokat (átmenetekkel); az inputot, ill. a verem tartalmát Lehetőségek

Mint a véges elfogadó automatáknál, csak az állapotok mellett feltüntetjük az inputot és a verem tartalmát; valamilyen időrend vagy több ábra kell Az egyes állapotokat kiragadva ábrázoljuk, mellettük bemutatva az inputot és a verem tartalmát

Lásd még: D. P. 159. 25

Formális nyelvek


Veremautomaták

Példa (determinisztikus veremautomata; végállapottal fogad el)

Leírása és működése P = (Q, Ʃ, Γ, δ, q0, Z0, F), ahol Q = {q0, q1, q2}, Ʃ = (a, b), Γ = (a, Z0), F = {q0} δ(q0, a, Z0) = (q1, aZ0) (első a) δ(q1, a, a) = (q1, aa) (többi a) δ(q1, b, a) = (q2, λ) (első b) δ(q2, λ, Z0) = (q0, λ) (vége) δ(q2, b, a) = (q2, λ) (többi b) (Az automata parciálisan definiált; rajz: D. P. 170.) Elemzendő mondat: aabb A konfigurációk sorozata (a működés egyszerűen követhető): (q0, aabb, Z0) 1 (q1, abb, aZ0) 1 (q1, bb, aaZ0) 1 (q2, b, aZ0) 1 1(q2, λ, Z0) 1 (q0, λ, λ) Elemzendő mondat: abb Feladat: Mutassuk meg, hogy abb ∉ Lf(P)

A (q0, b, λ) konfigurációból nem lehet továbbmenni

(Konstruáljunk hasonló kis feladatokat az előző oldalakon szereplő automatákhoz is) Igazolható az is (pl. indukcióval), hogy Lf(P) = {anbn | n ≥ 0} Itt: Lf(P) ≠ Le(P), hiszen Le(P) = {anbn | n ≥ 1}, azaz Le(P) = Lf(P) – {λ}

Ennek ellenére a két nyelvosztály közötti kapcsolat általánosan is nagyon szoros Tétel: A veremautomatákkal végállapotokkal felismerhető nyelvek osztálya megegyezik a veremautomatákkal üres veremmel felismerhető nyelvek osztályával 26

1

Recommend Documents