9. előadás Környezetfüggetlen nyelvek

Formális nyelvek

Széchenyi István Egyetem

9. előadás Környezetfüggetlen nyelvek

Dr. Kallós Gábor

2015–2016 11

Formális nyelvek


Tartalom Bevezetés CF nyelv példák

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

Elemzések 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 α egy (N ∪ T)*-beli szó (ún. mondatforma)

Itt nagyobb a szabadság a helyettesítési szabályoknál, mint a reguláris nyelveket generáló nyelvtanoknál Ez viszont több olyan problémát is felvet, amivel eddig még nem találkoztunk

Példa 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 konvenciót a nemterminális és terminális jelek használatáról (de: ezek a szimbólumok kellenek) (E – expression, T – term, F – factor; az a pedig egy azonosító) A nyelvtan az 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 (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 ⇒ 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 (több nemterm. a jobb oldalon) 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? Eml.: A CF nyelvek (nyelvtanok) fontos tulajdonsága, hogy a levezetések fa alakban ábrázolhatók A fa gyökere a mondatszimbólum Minden csomópontból annyi él (olyan – kötött – sorrendben) fut ki, amennyi a szabály jobboldalán található szimbólumok száma, és az élek végein a jobboldal megfelelő szimbólumai találhatók 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 N-beli 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)

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”, ill. „Az oroszlán simogatása veszélyes” Angol: ”Fruit flies like a banana” (Az angolban gyakori: egy szóalak lehet főnév vagy ige is)

Itt a szövegkörnyezet vagy a beszédhelyzet segít eldönteni a helyes jelentést A fordítóprogramoktól ilyet nem nagyon várhatunk…

Egyszerű példák, amikor a Word helyesírás-ellenőrzője nem jelez: 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! (Segítség: lásd előző oldal)

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ételhez 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


Egy- és többértelműség 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 (!) 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!

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 Itt a generált nyelv egyértelmű nyelvtannal is előállítható

Vajon mindig ez a helyzet, vagy lehet a többértelműség nyelvi tulajdonság? Vá.: Léteznek olyan nyelvek, amelyekről bizonyítható, hogy nem lehet őket egyértelmű nyelvtannal generálni Ekkor a többértelműség nyelvi tulajdonság (azaz: nincs ∀ CF nyelvnek egyért. 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


Egy- és többértelműség 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 nyelvtan vagy nyelv egyértelmű-e (B. I. 83.) Persze ettől még sok konkrét esetben a probléma megoldható (egyedi tulajdonságok vagy szerencsés ötletek felhasználásával) Például a Gar nyelvtan egyértelműsége igazolható

Visszatekintés: Felmerül-e az egyértelműség/többértelműség kérdése a reguláris nyelveknél? (B. I.) Vá.: Nem!

(Mindegy, hogy a redukált- vagy a nem redukált esetet vizsgáljuk.) 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ó (Eml.: a bal- és jobbreguláris nyelvtanok ekvivalensek) Egy levezetési fához itt csak egy levezetés tartozik (minden mondatformában csak egyetlen nemterminális szimbólum szerepel)

Nemdeterminisztikusság: egy mondatnak létezhet több kül. levezetési fája, de a ND megszüntethető (NDA → DA konstrukció) Tehát (végül): 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 CF 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.: a bal (oldali) levezetés technikája a mélységi kereséshez hasonlít

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 9

Formális nyelvek


Levezetési fák Példa (a nyelvtan λ-szabályt is tartalmaz) Alapnyelvtan: G6 = ({S}, {a, b}, {S → aB, S → bA, S → λ, A → aS, A → bAA, B → bS, B → aBB}, S) Szó: aababb A (sikeres) levezetés: S → aB ⇒ aaBB ⇒ aabSB ⇒ aabB ⇒ aabaBB ⇒ aababSB ⇒ aababB ⇒ aababbS ⇒ aababb Az ábra alján látható a levezetett szó (a betűket összeolvassuk, a λ-kat elhagyjuk) Feladatok Nézzük meg, hogyan tudjuk kiolvasni a levezetési fából a közbülső mondatformákat Rajzoljunk fel más levezetési fákat is a nyelvtanhoz Próbáljunk előállítani bal és jobb (oldali) levezetéseket a nyelvtannal 10

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: Az a fa, amelynek egyetlen szögpontja (csak gyökere) van, és annak címkéje X, eleme DX-nek (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)

Ha X ∈ T, akkor a 2. és 3. feltételek soha nem teljesülnek, ekkor tehát DX = {X} (Terminálisból már nem lehet levezetni semmit)

Megjegyzések A derivációs fa leveleihez T-beli vagy N-beli szimbólumokat, közbülső csúcsaihoz pedig N-beli 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.)

11

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: 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).

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 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 a 2. slidesor levezetési fáira (27. és 28. slide), é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 12

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 (F. Z.) 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 ∀ m ≤ n-re 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 ∀ 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. 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 = α. 13

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 Ez a példákban jól látható

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

14

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) 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 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) 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!

15

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, mivel ∀ 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*} 16

Formális nyelvek


Elemzések Az elemzés (parsing) feladatáról A cél a nyelvtani struktúra felfedezése/felderítése, ez a fordítás fontos része Parsing kifejezés eredete: „parts of speech” (latin megfelelő)

A feladat: adott x ∈ T* szóhoz konstruáljunk egy olyan derivációs fát, amit a nyelvtan elő tud állítani A feladat (könnyű) része lehet egy ellenőrzés is, hogy x valóban terminális szó-e

Két alapvető megközelítés: felülről-lefelé (top-down) és alulról-felfelé (bottom-up) Mindegyiken belül: többféle egyedi módszer (algoritmus)

Felülről-lefelé elemzés S-ből kiindulva, a szokásos (ismert) módon felépítjük a levezetési fát Ehhez általában sok különböző mondatformát és mondatot kell előállítani

Alulról-felfelé elemzés Az x szóból kiindulva felfelé építjük fel a fát, végül el kell jutni S-ig Egyik lehetséges megvalósítás: a redukciós módszer Felcseréljük a szabályok jobb és bal oldalát, így a szabályokból (produkció) „redukciókat” kapunk Ez sok esetben sima ügy, de adódhatnak nehézségek (eml.: probléma adódik a λ-szabályokkal)

17

Formális nyelvek


Elemzések Egyszerű példa a redukciós módszer alkalmazására Alapnyelvtan: G3 = ({S}, {a, b}, {S → aSb, S → ab}, S), szó: aaabbb A fordított nyelvtan szabályai: Pf = {aSb → S, ab → S} A folyamat: x-ben keresünk egy olyan részszót, amire alkalmazható valamelyik szabály Alkalmazzuk a megfelelő szabályt Az új x' szóval végrehajtjuk ugyanezt stb.

Példánkban egyértelmű a szabályok alkalmazása, mindegyik lépésben csak egy választható

18

Formális nyelvek


Elemzések Redukciós módszer (második példa) Alapnyelvtan: G6 = ({S}, {a, b}, {S → aB, S → bA, S → λ, A → aS, A → bAA, B → bS, B → aBB}, S), szó: aababb A fordított nyelvtan szabályai: Pf = {λ → S, aB → S, bA → S, aS → A, bAA → A, bS → B, aBB → B} A redukció nyilván a λ → S szabállyal indul, hogy alkalmazhassuk majd az aS → A vagy a bS → B szabályok valamelyikét Csakhogy, ha S-t pl. az első vagy második a után helyezzük el, akkor a fa nem lesz felépíthető Feladat: Ellenőrizzük ezt!

(Mi persze tudjuk, hogy aababb ⇒ aababbS ⇒ aababB ⇒ aababSB ⇒ aabaBB ⇒ aabB ⇒ …) További fontos kérdés: aabaBB-nél aB → S, aBB → B is választható lenne, hogyan döntünk? Itt már nem egyértelmű a szabályok alkalmazása! Megoldás lehet a CF nyelvtanok megfelelő átalakítása (ld. később, 12. slidesor) λ mentesítés A jobb oldalon legfeljebb kettő hosszú szabályok legyenek (Chomsky-féle normálforma)

Külön köszönet: a hivatkozott jegyzetek szerzőinek

Formális nyelvek

19


Ajánlott irodalom Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Polygon, Szeged, 2001 Dömösi Pál és társai: Formális nyelvek és automaták, Elektronikus jegyzet, 2011 Bach Iván: Formális nyelvek, Typotex kiadó, Budapest, 2002 Csörnyei Zoltán: Fordítóprogramok, Typotex kiadó, Budapest, 2009 Alan P. Parkes: A Concise Introduction to Languages and Machines, Springer,  London, 2008

20

9. előadás Környezetfüggetlen nyelvek

Recommend Documents