2)

Formális nyelvek és gépek (09/10/2)

Formális nyelvek és gépek (definíciós és tétel lista - 09/10/2)

ábécé: Ábécének nevezünk egy tetszőleges véges szimbólumhalmazt. Jelölése: X, Y betű: Az ábécé elemeit betűknek hívjuk. szó: Az X ábécé elemeinek egy tetszőleges, véges sorozatát szónak nevezzük. Jelölése: v, w, X ábécé feletti összes szó halmaza: X*

nyelv: Az X* valamely részhalmazát az X ábécé feletti nyelvnek nevezzük. nyelvosztály: Nyelvek valamely összességét nyelvosztálynak, nyelvcsaládnak nevezzük. reguláris nyelvek: Reguláris nyelveknek nevezzük azokat az L nyelveket, melyek megfelelnek az alábbiaknak: - L az {a}, az üres szót tartalmazó, az üres nyelvek valamelyike (ezek az elemi nyelvek), ahol a eleme U

L nyelv rekurzív: Akkor rekurzív egy nyelv, ha van olyan A eldöntő algoritmus, melynek inputjára egy tetszőleges u szót helyezve, eldönti, hogy ez az u szó benne van-e az L nyelvben, ha igen a válasz, u eleme a nyelvnek, ha nem a válasz, akkor nem.

L nyelv parciálisan rekurzív: Akkor parciálisan rekurzív egy nyelv, ha létezik olyan A parciális eldöntő algoritmus, melynek inputjára tetszőleges szót helyezve, eldönti, hogy az benne van-e az L nyelvben. Ha eleme, akkor igen válasszal tér vissza, ha nem vagy nem terminál vagy nem választ ad.

L nyelv rekurzívan felsorolható: Az L nyelv rekurzívan felsorolható, hogyha létezik olyan algoritmus, amely felsorolja az elemeit.

-----------------------------------------produkciós rendszer: Produkciós rendszer alatt azt a nyelv definiálási módszert értjük, amely egy hármassal azonosít egy nyelvet. Ezek: X, amely a nyelv ábécéje, P amely a produkciós szabályok véges halmaza (részhalmaza X* x X*) és a Ax egy véges axiómahalmaz (részhalmaza X*-nak). Formális leírását lásd jegyzet 16. oldal.

közvetlen levezetés: Egy produkciós rendszerben akkor mondjuk, hogy X*-beli a szóból közvetlen levezethető X*-beli b szó, hogyha létezik a produkciós rendszerben olyan q1, q2 X*-beli szavak, valamint olyan p ->q szabály, amelyekre igaz az, hogy a = q1pq2 és b=q1qq2. Tehát a környezet azonos és a részszavak "egymás közötti megfeleltetésére" van szabály a rendszerben.

p.r. által generált nyelv: Egy produkciós rendszer által generált T ábécére relatív L nyelv az a nyelv, amely azokból a T*-beli szavakból áll, melyekhez létezik olyan elem az axiómahalmazban (Ax) melyből a produkciós rendszerben közvetett levezetés vezet a nyelv egy szavához.

p.r. által elfogadott nyelv: Egy produkciós rendszer által elfogadott T ábécére relatív nyelv az a nyelv, amely azokból a T*-beli szavakból áll, melyekből egy axiómahalmazbeli elem közvetett levezethető.

Mi a különbség a generált és az elfogadott nyelv között? A generált nyelvben tehát az axiómahalmazbeli elemből vezettük le a generált nyelv elemeit, míg az elfogadott nyelvben az elfogadott nyelv szavaiból vezettük le az axiómahalmazbeli elemet.

generatív nyelvtanok: G=[T,N,P,S] (T: terminális jelek, N: nyelvtani jelek, P: véges szabályhalmaz, S: kezdőszimbólum)

mondatforma: Terminális jelekből és nyelvtani jelekből álló összetételek. (T unió N)* terminális szavak: Terminális jelekből alkotott szavak. Jele: T* ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Ez a jegyzet nem hivatalos és a teljesség igénye nélkül készült. Előfordulhatnak benne hibák, hiányosságok. Amennyiben hibás leírást, definíciót találsz vagy bármilyen észrevételed van, kérlek szólj nekem a [email protected] címen. -------------------------------------------------------1-


Chomsky-féle hierarchia (nyelvosztályok): 4 nyelvosztály létezik, 0-ás, 1-es, 2-es és 3-as típusú. 0-ás típus: Nincs megkötés rá, ami azt is jelenti, hogy minden nyelvtan egyben 0-ás típusú nyelvtan is. Egyetlen megkötés az az "alap" megkötés, miszerint a szabályok bal oldalán mindenképpen szerepelnie kell nyelvtani jelnek. 1-es típus: Két szabályformát enged: - q1Aq2 -> q1qq2, ahol q1 és q2 mondatforma, tehát (TUN)* és ezt nevezzük környezetnek és A eleme a nyelvtani jeleknek, q pedig szintén mondatforma: (TUN)+, a csillag helyett + jel azt jelenti, hogy q bármilyen mondatforma lehet, kivétel az üres szó. Ez a szabályforma a környezetfüggő szabályforma. - S -> epsz, tehát üres szó. Ezt úgy használhatjuk a nyelvtanunkban, hogy S a kezdőszimbólum ugyanebben a nyelvtanban és ha ez a szabály használt, akkor S nem szerepelhet a szabályok jobboldalán. Tehát a szabályok jobboldala ne legyen közvetlen leképezhető üres szóra. 2-es típus: Itt is két szabályforma lehetséges és következik az 1-es típusúból. További megkötése, hogy az 1-es típusnál megismert szabályban a környezet, azaz q1 és q2 üres szó legyen! Tehát ebből következnek az alábbi szabályformák: - A -> q, ahol A eleme a nyelvtani jeleknek és q egy mondatforma, kivétel az üres szót (TUN)+. Ez a környezetfüggetlen szabályforma. - Ugyanaz mint az 1-es típusúnál: S -> epsz 3- típus: További megszorítás a 2-es típusúhoz képest, hogy q csak bizonyos formájú lehet. Három megengedett szabályforma van tehát: - A -> aB, ahol A és B nyelvtani jelek és a egy terminális jel. - A -> a, ahol A egy nyelvtani jel és a egy terminális jel. - Ugyanaz mint az -1es és 2-es típusnál: S -> epsz Mindhárom típusnál az S -> epsz szabályforma csak az egyéb szabályokkal nem levezethető üres szó levezetésére szolgál. Egyértelműen látható, hogy az egyes nyelvtanok egymás részhalmazai és a 0-ás típusú a "legnagyobb" ennek részhalmaza az 1-es, ennek a 2-es és a 2-esnek a 3-as.

Church-tézis: Minden valamilyen konstruktív módon megadható nyelv leírható nyelvtannal. kiterjesztett nyelvtani típusok kiterjesztési tétel: Nem lesz vizsgán, így nem részletezem. e-mentesítés (e: üres szó): Az az eljárás mely eltűnteti az olyan szabályokat, amelyek jobb oldalán áll üres szó.

láncszabályok: (A -> B ahol A,B eleme N) Olyan szabály, amelynek bal és jobb oldalán is 1-1 nyelvtani jel áll.

láncmentesítés: A láncszabályokat eltűntető eljárás. hosszredukció: Álljon itt a példa: A -> uB, azt szeretnénk elérni, hogy u csak egy betű legyen. A hosszredukció az az eljárás, melyben az ilyen szabályoknál felbontással érjük el, amit szeretnénk, így több szabályt kapunk, de az már mind "jó". A -> uB-re pl. A -> t1Z1; Z1 ->t2Z2 ... Zk-1 ->tkB, ahol Z-k új nyelvtani jelek.

-----------------------------------------

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------Ez a jegyzet nem hivatalos és a teljesség igénye nélkül készült. Előfordulhatnak benne hibák, hiányosságok. Amennyiben hibás leírást, definíciót találsz vagy bármilyen észrevételed van, kérlek szólj nekem a [email protected] címen. -------------------------------------------------------2-


Kuroda normálforma tétel: Tetszőleges 3-as nyelvcsaládba tartozó nyelv esetén, létezik olyan G nyelvtan, amely Kuroda normálformájú és L(G)=L, azaz a G Kuroda normálformájú nyelvtan által generált L nyelv, egyenlő a tetszőleges L nyelvünkkel. Kuroda normálforma szabályai: - S -> epsz, ilyenkor S kezdőszimbólum és nem állhat S a szabályok jobboldalán. - A ->t - A -> BC - AB -> AC - BA -> CA ahol A, B, C 1-1 nyelvtani jel és t egy terminális jel.

Chomsky normálforma tétel: Tetszőleges 2-es nyelvcsaládba tartozó nyelv esetén, létezik olyan G nyelvtan, amely Chomsky normálformájú és L(G)=L, azaz a G Chomsky normálformájú nyelvtan által generált L nyelv, egyenlő a tetszőleges L nyelvünkkel. Chomsky normálforma szabályai: - S -> epsz, ahol S kezdőszimbólum és nem állhat S a szabályok jobboldalán. - A -> t - A -> BC ahol A, B, C 1-1 nyelvtani jel és t egy terminális jel.

Greibach normálforma tétel: A tétel és bizonyítása nem lesz a vizsgán. Greibach normálforma szabályai: - S -> epsz, ahol S kezdőszimbólum és nem állhat S a szabályok jobboldalán. - A -> tQ ahol A nyelvtani jel és t egy terminális jel és Q egy tetszőleges nyelvtani jelsorozat: N*

3-as normálforma szabályai: - A -> epsz - A -> aB ahol A és B nyelvtani jel és a terminális jel. Vegyük észre, hogy a Chomsky és Kuroda normálformánál csak S, mint kezdőszimbólumból volt levezethető üres szó, itt viszont tetszőleges A nyelvtani jelből is.

rekurzív nyelvtani jel (balrekurzív, jobbrekurzív): Az A nyelvtani jel rekurzív, vagyis önbeágyazott, ha indul belőle egy olyan nem triviális levezetés alfa1Aalfa2-re, ahol alfa1 és alfa2 eleme a terminális és nyelvtani jelek összességének. Egy A nyelvtani jel, akkor balrekurzív, ha alfa1 (azaz baloldali környezet) = üres szó és akkor jobbrekurzív, ha alfa 2 (azaz jobboldali környezete) üres szó.

nyelvtan redukálása: A nyelvtan redukálása az, amikor a felesleges nyelvtani jeleket és szabályokat elhagyjuk. A felesleges jelek leképzése során zsákutcába visznek, vagyis belőlük semmilyen T*-beli szó nem vezethető le. Felesleges nyelvtani szabályok pedig azok, amelyek a kezdőszimbólumból nem elérhetőek.

zsákutca-mentesítés: Első lépésben keressük meg a zsákutcákat, azaz az olyan részleképzéseket, melyekből nem tudunk tovább lépni, de az még nem T*-beli szó. A lényeg, hogy építsük fel azt a H halmazt, amely tartalmazza az összes elérhető nyelvtani jelet és végül ezt vonjuk ki az összes nyelvtani jelünkből. H halmaz konstrukciós lépéseit lásd a jegyzet 51. oldalán.

összefüggő nyelvtan, összefüggővé alakítás redukált nyelvtan: Egy zsákutcamentes és összefüggő 2-es típusú nyelvtant redukáltnak nevezünk.



rendezett nyelvtan: Egy G nyelvtan rendezett nyelvtan, hogyha a nyelvtani jelei megszámozhatóak úgy, hogy N = {A1, ... An} és Ai -> Ajq egy szabály, akkor i<j és q eleme a terminális nyelvtani jeleknek.

kvázi Greibach normálformájú nyelvtan ----------------------------------------zárt nyelvcsalád (jel) nyelvi operátorra: Egy nyelvcsalád akkor zárt egy nyelvi operátorra, ha a nyelvcsalád nyelvei a nyelvi operátor végrehajtásának hatására is az adott nyelvcsaládbeli nyelvek maradnak.

zártsági tétel: Mind a négy nyelvosztály zárt az unió, a konkatenáció és a lezárás műveletére. ----------------------------------------veremautomata: Egy olyan speciális matematikai gép, amelyben n-verem van és a következőkből áll: A az automata lehetséges állapotainak véges halmaza, T egy ábécé itt a bemenő ábécé, az i. verem ábécé epsziloni, gamma az állapotátmeneti függvény, a0 eleme A-nak ez a kezdőállapot, az i. verem kezdőszimbóluma, F pedig részhalmaza A-nak és a végállapotok halmazát jelöli.

konfiguráció: Azoknak az adatoknak az összessége, melyektől a gép elkövetkezendő működése függ. közvetlen és közvetett konfiguráció-átmenet: Közvetlen konfiguráció-átmenetről beszélünk, hogyha V veremautomata 1 lépésben vált át egyik konfigurációból a másikba. Közvetett konfigurációátmenet pedig a közvetlen átmenet reflexív, tranzitív lezártja. Azaz egyszerűen szólva, hogyha egy megadott állapotból egy másik állapotba több lépésen keresztül jutunk el.

termináló konfiguráció: Az a konfiguráció, amelynek nincs már rákövetkezője. Az "utolsó lépés". végállapottal illetve üres veremmel elfogadó konfiguráció: Végállapottal elfogadó egy [f, epszilon, béta1 ... bétan] konfiguráció, hogyha f eleme F-nek (F a végállapotok halmaza). Üres veremmel elfogadó pedig akkor, hogyha béta1 = epszilon.

determinisztikus veremautomata: Egy adott V n-verem determinisztikus, ha minden konfigurációnak legfeljebb egy rákövetkezője van.

0-vermek: Nincsen benne kiegészítő tár, működése az input jeltől és az aktuális állapottól függ csupán. A szavak elfogadása is csak végállapottal lehetséges, épp ezért elég simán elfogadásról beszélni.

0-vermek osztályozása: 4 osztály van, egyre több megkötéssel. Ezek részleteit lásd a jegyzet 74. oldalán.

állapotátmenet függvény: Értékkészlete véges halmaz legyen. Igazából az a függvény, amely leírja az egyik konfigurációból másikba való lépést formálisan. Létezik kiterjesztése is.

----------------------------------------Kis Bar-Hillel lemma: Minden nyelvhez, amely a 3-as típusú nyelvcsaládba tartozik, van olyan n=n(L) eleme N nyelvfüggő konstans, hogy a nyelv minden szavának egy tetszőleges n-nél hosszabb vagy azzal egyenlő részszavában létezik egy elég rövid (n-nel egyenlő vagy annál kisebb, de 0-nál nagyobb) részszó, amely nem üres és beiterálható.

adott L nyelv p eleme T*-ra vonatkozó maradéknyelve Lp: L nyelv p-re vonatkozó maradéknyelve, azokat az u szavakat adja meg, amelyekre igaz, hogy pu eleme az L nyelvnek.

A determinisztikus automata A-beli q állapotra vonatkozó maradéka: Azokat az u szavakat tartalmazza, melyek hatására az automata q állapotból végállapotba jut.

Myhill-Nerode tétel: Egy nyelv akkor és csak is akkor eleme a 3-as típusú nyelvcsaládnak, ha p-re vonatkozó maradéknyelve, ahol p a terminális szavak egy eleme, kisebb végtelennél, azaz véges. -------------------------------------------------------------------------------------------------------------------------------------------------------------------------Ez a jegyzet nem hivatalos és a teljesség igénye nélkül készült. Előfordulhatnak benne hibák, hiányosságok. Amennyiben hibás leírást, definíciót találsz vagy bármilyen észrevételed van, kérlek szólj nekem a [email protected] címen. -------------------------------------------------------4-


minimál automata: Egy 3-as típusú nyelvez adott minimális állapotszámú, véges, determinisztikus automatát a nyelv minimális automatájának hívjuk.

minimál automata előállítása: lépések: 1. összefüggővé alakítás, 2. redukció összefüggő automata: Egy automata akkor összefüggő, hogyha minden állapotához (a) létezik egy olyan terminális szó (u), amellyel egy a0 állapotból az a állapotba léphetünk, azaz a kezdőállapotból elérhető ez az állapot.

redukció, redukált automata: Ha két állapot ugyanazon szavak hatására kerül végállapotba, akkor azt nem tekintjük megkülönböztethető nyelveknek a nyelvelfogadás szempontjából. Redukált automatába ilyen állapotok nincsenek.

Kleene tétele: A 3.as nyelvcsaládba tartozó nyelvek reguláris nyelvek. 3-as típusú nyelvosztály zárt a komplementer, a metszet, a különbség és a szimmetrikus differencia műveleteire.

----------------------------------------algoritmikusan eldönthető problémák: Egy adott probléma algoritmikusan eldönthető, ha létezik olyan algoritmus, mely igen válasszal áll le, ha a problémának van megoldása és nem választ ad, ha nincsen.

G feletti szintaxisfa: A levezetések szerkezetét tudjuk vele ábrázolni. G tetszőleges 2-es típusú nyelvtan. A t nemüres fát G feletti szintaxisfának nevezzük, hogyha pontjai a nyelvtan terminális és nyelvtani jelei vagy az üres szóval vannak címkézve. Azaz T u N u {epsz}. Belső pontjai nyelvtani jelekkel vannak címkézve (N elemeivel) és ha egy belső pont címkéje X, a közvetlen leszármazottjai balról jobbra X1, X2 .. Xk, akkor X -> X1X2 ... Xk egy szabály a nyelvtanunkban.

legbal és legjobb levezetés: Ez hosszabb, mintsem, hogy itt leírjam és egy szép kis ábra is van hozzá a jegyzet 110. oldalán.

legbal és legjobb mondatforma: Legbal, illetve legjobb levezetés során előforduló mondatformák. egyértelmű nyelvtan: Egy kiterjesztett 2-es típusú nyelvtan akkor egyértelmű, hogyha a nyelvtanunk feletti L nyelv minden szavának pontosan egy szintaxisfája létezik.

egyértelmű nyelv: Egy 2-es típusú nyelv akkor egyértelmű, hogyha létezik hozzá olyan kiterjesztett 2-es típusú nyelvtan, amely egyértelmű.

lényegesen nem egyértelmű nyelv: Egy 2-es típusú nyelvet, akkor nevezünk lényegesen nem egyértelmű nyelvnek, hogyha az adott nyelvhez nem létezik egyértelmű nyelvtan.

Nagy Bar-Hillel lemma: Egy 2-es típusú nyelvben lévő minden elég hosszú szóban van két, egymáshoz elég közel álló, nem triviális, párhuzamosan beiterálható részszó.

legbal kezdőszelet-egyeztetéses elemzés: Egy 2-es kiterjesztett nyelvtan legbal kezdőszeletegyeztetéses elemzésének hívjuk azt az elemzési módszert, amely során egy tetszőleges u szó egy S kezdőállapotból induló legbal levezetését konstruáljuk meg a levezetés során kialakult mondatforma terminális jeleiből álló kezdőszeletének az eredeti u szó kezdőszeleteivel való egyeztetésével. Ez akkor sikeresen, ha az a tetszőleges u szó, a nyelvtanunk felett lévő L nyelv egy szava.

-----------------------------------------determinisztikus 1-vermek 1-es normálformájú 1-verem 2-es normálformájú 1-verem 3-as normálformájú 1-verem -------------------------------------------------------------------------------------------------------------------------------------------------------------------------Ez a jegyzet nem hivatalos és a teljesség igénye nélkül készült. Előfordulhatnak benne hibák, hiányosságok. Amennyiben hibás leírást, definíciót találsz vagy bármilyen észrevételed van, kérlek szólj nekem a [email protected] címen. -------------------------------------------------------5-


-----------------------------------------fordítóprogramok elemzései: lexikális elemzés, szintaxiselemzés, szemantikus elemzés szintaxiselemzési módszerek (top-down és bottom-up, left to right elemzők) LL(k) nyelvtanok LR(k) nyelvtanok -----------------------------------------Turing automaták: Turing automata elmélete nem lesz vizsgán, így nem tárgyalom. Viszont Turing programozás várható.


2)

Recommend Documents