Programozás | Programozás-elmélet » Szurgyi Krisztián - Nyelvek és automaták

Szurgyi Krisztián Nyelvek és automaták Debrecen, 1999 1. Formális nyelvek Ábécé: Legyen V nem üres és véges halmaz, amelyet ábécének hívunk, elemeit pedig betűknek. Jelben: V={x 1 , x 2 , , x n }. Szó: A V ábécé elemeiből álló véges jelsorozat. Üres szó: Olyan szó, amelynek egyetlen betűje sincs. Jele: λ V+: V feletti nem üres szavak halmaza. V*: V+∪λ. A V feletti összes szavak halmaza Szó hossza: Egy p szó hosszát |p|-al jelöljük, és rajta a p-beli betűk számát értjük. Tehát |λ|=0 Szavak egyenlősége: Valamely V*-beli p=x 1 , x 2 ,,x n és q=y 1 , y 2 ,,y m (x 1 , x 2 ,, x n , y 1 , y 2 ,, y m ∈V) szavakat pontosan akkor tekintjük egyenlőknek, ha m=n és minden i(=1,, n)-re x i =y i . Ezt a tényt ki szokás úgy is fejezni, hogy V*-ban csak grafikus (betűről-betűre megegyező) egyenlőség létezik. Szavak szorzása (konkatenáció): A p= x 1 , x 2 ,,x n és q= y 1 , y 2 ,,y m (x 1 , x 2 ,, x n , y 1 , y 2 ,, y m ∈V)

szavak szorzatán a pq=x 1 x 2 x n y 1 y 2 y m szót értjük. Tehát a szavakat egymás mellé írjuk A szorzás asszociatív, de általában nem kommutatív Szavak hatványozása: Amennyiben p=p 1 p k (∈V*, k=1, 2,), továbbá p 1 =p 2 ==p k =q(∈V), úgy alkalmazni fogjuk a p= qk jelölést, s ez esetben p-t a q szó k-adik hatványának is nevezzük. Továbbá megállapodunk abban, hogy minden szó nulladik hatványa az üres szó. Szó tükörképe: Egy p=x 1 , x 2 ,,x n szó tükörképén vagy inverzióján a p-1=x n x n-1 x 1 szót értjük. A V*-ban a szorzás műveletére nézve a λ üres szó egységelem lesz, hiszen minden p∈V-ra pλ=λp=p. Nyilvánvaló továbbá, hogy minden p, q∈V* párra |pq|=|p|+|q|. • • (V*, ⋅) algebrai struktúrát a V által generált egységelemes szabad félcsoportnak, más néven V feletti egységelemes szabad félcsoportnak, vagy röviden V feletti monoidnak hívjuk. (V+, ⋅) algebrai struktúrát a V feletti szabad

félcsoportnak hívjuk. A „szabad” jelző a grafikus egyenlőségre utal. Legyen p és q tetszőleges két szó V*-ban. Azt mondjuk, hogy p kezdőszelete vagy prefixuma q-nak, ha van olyan r∈V*, hogy q=pr. Hasonlóan, ha van olya s∈V* szó, hogy q=sp, akkor azt mondjuk, hogy p a q-nak végződése, zárószelete, vagy szuffixuma. Végül, a p∈V* szót a q∈V szó részszavának mondjuk, ha van olyan r, s∈V, hogy q=rps. Amennyiben p≠q, valódi rész-szóról beszélünk Hasonlóan, egy szó önmagától különböző kezdőszeleteit, illetve végződéseit valódi kezdőszeletnek, illetve valódi végződésnek hívjuk Formális nyelv: Szavaknak egy tetszőleges halmaza. Jelben: L⊆V*. Valamely L⊆V* nyelvet üresnek, végesnek vagy végtelennek hívunk, ha az L (mint halmaz) üres, véges, illetve végtelen. Üres nyelv (lehetetlen nyelv): L=∅ Elemi nyelvek: λ nyelv: L={λ} Alapnyelvek: L=x 1 , L=x 2 , , L=x n Univerzális nyelv (teljes nyelv): L= V*. Az

univerzális nyelv megszámlálhatóan végtelen sok szót tartalmaz (A V* részhalmazainak összessége nem megszámlálhatóan végtelen, tehát egy tetszőleges véges ábécéhez tartozó nyelvek összessége nem megszámlálható.) 1 1.1 Műveletek nyelvekkel L 1 ∪L 2 ={p: p∈L 1 vagy p∈L 2 } L 1 ∩L 2 ={p: p∈L 1 és p∈L 2 } L 1 -L 2 ={p: p∈L 1 és p∉L 2 } L 1 ⋅L 2 ={p 1 p 2 : p 1 ∈L 1 , p 2 ∈L 2 } ¬L=V*-L Unió (asszociatív, kommutatív, idempotens) Metszet (asszociatív, kommutatív, idempotens) Különbség Szorzat Komplementer Hatványozás: L0={λ} L1=L Ln=Ln-1⋅L Iterál (L nyelv hatványainak egyesítése): L*=L0∪L1∪L2∪ L nyelv tükörképe: L-1={p-1: p∈L} A szorzás műveletére nézve az ∅ nyelv nullelemként, a {λ} nyelv egységelemként viselkedik, azaz ∀L-re L⋅∅=∅⋅L=∅; L⋅{λ}={λ}⋅L=L. Nyelvek szorzása disztributív az unió műveletére nézve: L 1 ⋅(L 2 ∪L 3 )=(L 1 ⋅L 2 )∪(L 1 ⋅L 3 ) (L 1 ∪L 2

)⋅L 3 =(L 1 ⋅L 3 )∪(L 2 ⋅L 3 ) {λ}*={λ} ∅*={λ} L*={λ}∪LL Reguláris műveletek: A nyelvekre bevezetett unió, szorzás és iteráció műveletét reguláris műveleteknek nevezzük. Boole-féle műveletek: Az unió, metszet, különbség és komplementerképzés műveletei. E műveletekre érvényesek a halmazelméletből ismert azonosságok. 2 2. Formális rendszerek Formális rendszer (átírási rendszer): Olyan W=(V, H) pár, ahol • V véges ábécé; • H a V*×V direkt szorzat egy véges részhalmaza. A H elemeit helyettesítési szabályoknak nevezzük, és ha (P, Q)∈H, akkor a PQ jelölést használjuk. A formális rendszer fogalma Axel Thue nevéhoz fűződik (1910). A formális rendszer fogalmának speciális eseteként fogható fel a matematikai logika és a számítástudomány több más fogalma, így az asszociatív kalkulus és a Markov-féle normál algoritmus is. Közvetlen levezetés: Legyen P, Q∈V*. Akkor mondjuk, hogy P-ből a Q

közvetlenül, vagy egy lépésben levezethető, W-ben, jelekben: P⇒Q, ha léteznek, olyan P’, P 1 , P’’, Q 1 ∈V* szavak, hogy P= P’P 1 P’’, Q= P’Q 1 P’’ és P 1 Q 1 ∈H. Levezetés: Azt mondjuk, hogy P-ből a Q levezethető W-ben, jelekben: P⇒*Q, ha léteznek olyan P 0 , P 1 ,., P k ∈V* szavak, hogy P 0 =P, P k =Q és P i ⇒P i+1 (i=0, 1,., k-1) Emellett megállapodunk abban, hogy minden P∈V* szóra P⇒*P fennáll. Használni fogjuk még a P⇒+Q jelölést is abban az esetben, ha azt akarjuk hangsúlyozni, hogy léteznek olyan P 0 , P 1 ,, P k ∈V* szavak, hogy P 0 =P, P k =Q, P i ⇒P i+1 (i=0, 1,., k-1), és P≠Q Asszociatív kalkulus: Olyan formális rendszer, melyben a helyettesítési szabályok szimmetrikusak. A helyettesítési szabályokat szokás cseréknek is nevezni Továbbá, ha egy P szóból egy Q szó levezethető az asszociatív kalkulusban, akkor azt mondjuk, hogy P ekvivalens Q-val, és így jelöljük: P≅Q Asszociatív kalkulusban

a levezethetőség, mint reláció ekvivalenciareláció Szóprobléma algoritmikus megoldása: Akkor mondjuk, hogy egy W=(V, H) asszociatív kalkulusban a szóprobléma megoldható, ha létezik olyan algoritmus, melynek segítségével tetszőleges P, Q szópárra eldönthető, hogy P és Q ekvivalens-e, és ha igen, akkor az algoritmus egy P⇒P 1 ⇒P 2 ⇒.⇒P n-1 ⇒Q levezetést is szolgáltat Ezen fogalomnak azért van különös jelentősége, mert kimutatható, hogy nem minden asszociatív kalkulusban oldható meg a szóprobléma, ami egyúttal azt is jelenti, hogy nincs olyan univerzális módszer, ami minden matematikai problémát képes megoldani. Generatív rendszer: Egy W=(V, H) formális rendszert generatív rendszernek nevezünk, ha ki van tüntetve V* egy nem üres véges részhalmaza, amelyet W axiómarendszerének nevezünk, és A x -el jelölünk. Egy ilyen W generatív rendszert W= (V, A x , H) alakban szokás megadni. W-hez hozzárendelünk egy L gW halmazt, az

L gW ={P∈V* | ∃A∈A x : A⇒P} definícióval, s ezt a halmazt a W generatív rendszer által generált nyelvnek hívjuk. L gW tehát tartalmazza mindazon V*-beli szavakat, melyek legalább az egyik axiómából levezethetők. Analitikus rendszer: A W=(V, A x , H) rendszerben tekintjük az összes olyan szavak halmazát, melyekből az axiómák közül legalább az egyik levezethető. Az L aW ={P∈V* | ∃A∈A x : P⇒A} halmazt az analitikus rendszer által elfogadott, felismert vagy acceptált nyelvnek hívjuk. Szemi-Thue rendszer: Olyan W=(V, A x , H) generatív rendszer, ahol ki van tüntetve V* egy olyan F részhalmaza, melyre A x ⊆F. Egy ilyen szemi-Thue rendszert W=(V, A x , H, F) alakban adunk meg, ahol F a formulák halmaza, és a W-nek a generatív rendszerhez hasonló értelmezése esetén mondhatjuk még azt is, hogy F az igaz (vagy igaznak tartott) állítások (kijelentések, mondatok, tételek) halmaza. Legyen W=(V, A x , H, F) tetszőleges szemi-Thue rendszer,

s jelölje A x ⇒*P röviden azt a tényt, hogy létezik olyan P 0 ∈A x , melyre P 0 ⇒*P. Ezt a jelölést használva L gW ={P∈V | A x ⇒*P} és W-ben absztrakt módon az F halmaz, mint elmélet (igaz, vagy igaznak tartott állítások halmaza) axiomatizálásának tipikus kérdései a következőkképpen fogalmazhatók meg. • Teljes-e az elmélet, vagyis az A x axiómarendszerből minden igaz állítás bebizonyítható-e. Jelöléssel: fennáll-e az F⊆L gW tartalmazás • Kategorikus-e az elmélet, vagyis az A x axiómarendszerből minden igaz állítás, de csakis az igaz állítások bebizonyíthatóak-e. Jelöléssel: F=L gW fennáll-e • Ellentmondásos-e az elmélet, vagyis igaz-e, hogy az axiómarendszerből nem vezethető le egyidejűleg igaz és hamis állítás. Képletben: igaz-e, hogy akárhogy is adjuk meg a P∈F és Q∉F párokat, A x ⇒*P mellett A x ⇒*Q nem állhat fenn egyidejűleg. • Minimális-e az elmélet, azaz igaz-e, hogy egyik axióma sem

bizonyítható be a másikból. Képletben: igaz-e, hogy ha P, Q∈A x , és P⇒*Q, akkor szükségképp P=Q. 3 Post-féle normál rendszer: Olyan W=(V, A x , H) generatív rendszer, melyben H elemei PXXQ alakúak, X∈V egy olyan betű, mely sem P-ben, sem Q-ban nem fordul elő. Akkor mondjuk, hogy a V*-beli P 1 szóból a V-beli Q 1 szó közvetlenül levezethető, ha található olyan V-beli X betű, továbbá találhatók olyan (V{X})*-beli P, Q, R szavak, hogy P 1 =PR, Q 1 =RQ, és PXXQ∈H. A levezetés, generált nyelv, elfogadott nyelv definíciója értelemszerűen adódik Post-féle tag rendszer: Olyan W=(V, S, H) hármas, ahol V egy ábécé, H helyettesítési szabályok halmaza, S pedig egy tetszőleges rögzített eleme V*-nak. Erre az S elemre a startszó elnevezés használatos Akkor mondjuk, hogy a V*-beli P szóból a V-beli Q szó közvetlenül levezethető W-ben, ha léteznek olyan P 1 , Q 1 , P’∈V szavak, hogy P=P 1 P’, Q=P’Q 1 , és P 1 Q 1 ∈H. 2.1

Algoritmus Algoritmus: Az algoritmus intuitív fogalmát körülbelül a következőképpen szokták megfogalmazni: A fegyelmezett, egyértelműen előírt lépésekből egyértelműen felépíthető olyan feladatmegoldás modellje, melynek eredménye végrehajtójától függetlenül ugyanazon feladatokra akárhányszor is megismételve ugyanazon eredményt szolgáltatja. Segítségével egy adott feladatosztály minden feladata véges számú lépésben megoldható Fontos tulajdonságai közé tartozik tehát a • függetlenség, amely azt jelenti, hogy ugyanazon feladatra ugyanaz az eredménye, függetlenül attól, hogy ki (vagy mi) a végrehajtója; • egyértelműség, amely azt jelenti, hogy ugyanazon feladatra akárhányszor is alkalmazzuk az algoritmust, mindig ugyanazt az eredményt szolgáltatja; • elemi lépésekre bonthatóság, ahol persze ezen elemi lépések, továbbá ezen lépések sorrendje is egyértelműen meg van határozva; • végesség, vagyis az, hogy a

feladatosztály minden egyes feladatára mindig véges sok lépésben befejeződik. Amennyiben a véges lépésben történő befejeződés követelményétől eltekintünk, az eljárás fogalmához jutunk. Ezen és ehhez hasonló intuitív megfogalmazások után születtek meg a 30-as évek második felétől a különféle matematikailag is precíz algoritmusfogalmak, melyeknek közös tulajdonságuk, hogy ekvivalensek. Ez azt jelent, hogy ha egy algoritmust az egyik algoritmusfogalom segítségével megadtunk, akkor ugyanez az algoritmus a másik algoritmusfogalom segítségével is megadható. Ezen algoritmusfogalmak közé tartoznak az alábbiak: • Markov-féle normál algoritmus; • Turing-gép; • Kleene-féle parciális rekurzív függvények; • Post-féle kanonikus rendszerek; • Herbrand-Gödel-féle egyenlőség-számítás; • Church-féle lambda-definiálhatóság; • Kolmogorov-Uszpenszkij-féle algoritmusok. Markov-féle normál algoritmus: Egy W=(V, H)

formális rendszert Markov-féle normál algoritmusnak nevezünk, ha H rendezett halmaz, és ki van tüntetve benne egy H 1 részhalmaz, megengedve, hogy H 1 az üres halmaz legyen. H 1 elemeit záróhelyettesítésnek hívjuk, és PQ∈H 1 esetén használni fogjuk a P.Q jelölést is Egy ilyen normál algoritmust W= (V, H, H 1 ) alakban adunk meg, ahol a H-beli halmaz egy rendezett halmaz. Az algoritmust egy szóra alkalmazhatjuk: a legelső használható helyettesítési szabályt kell kiválasztani, a szóban pedig a lehető legelső helyen kell alkalmazni. A helyettesítés fogalmát itt elemi helyettesítésnek nevezzük P⇒Q esetén elemi záróhelyettesítésről beszélünk. Levezetés: Azt mondjuk, hogy a P∈V* szóból egy Q∈V szó W-ben levezethető, ha teljesülnek az alábbi feltételek: • W alkalmazható P-re, • léteznek olyan R 0 ,., R k ∈V* szavak, hogy R 0 =P, R k = Q, R i ⇒R i+1 (i=0,., k-1), és vagy R k-1 ⇒R k , vagy pedig R k-1 ⇒R k , és W az R k

(=Q) szóra már nem alkalmazható. Emellett megállapodás, hogy ha W a P szóra nem alkalmazható, akkor P⇒*P. 4 Ha P⇒*Q, akkor szokás mondani, hogy Q a P szóval megadott adatsorozaton a W normál algoritmussal végrehajtott számítás eredménye. Egy normál algoritmus esetén a P∈V* szóra a következő esetek állhatnak fenn: • W a P-re nem alkalmazható. Ekkor a W-vel P-n végzett számítás eredményének magát a P adatot tekintik • P-ből kiindulva létezik záróhelyettesítéssel végződő, vagy tovább nem folytatható helyettesítési lánc. • P-ből olyan helyettesítési lánc indul ki, mely soha nem fejeződik be. Ilyenkor azt mondjuk, hogy W a P-re nem áll meg, W a P adatból eredményt nem szolgáltat. 2.2 Nyelvtan Generatív nyelvtan, generatív grammatika: Egy W= (V, A x , H) generatív rendszert generatív nyelvtannak hívunk, ha V=V N ∪V T , V N ∩V T =∅, A x ={S}. Egy ilyen generatív nyelvtant G=(V N , V T , S, H) alakban adunk meg,

ahol • V N : nemterminális betűk, változók, szimbólumok halmaza, V N véges, V N ≠∅; • V T : terminális betűk, konstansok halmaza V T véges, V T ≠∅; • S: mondatszimbólum, kezdőszimbólum, S∈V N ; • H: helyettesítési szabályok véges halmaza, H⊆V*V N V×V, azaz minden H-beli szabály bal oldala legalább egy darab nemterminális betűt tartalmaz. A V* elemei mondatformák, V N elemei nemtrminális szavak, V T elemei terminális szavak, mondatok. A G generatív grammatika által generált nyelv: L(G)={p∈V T * | S⇒p}, vagy L(G)=L gG ∩V T , L(G)⊆L gG . Analitikus nyelvtan: A generatív nyelvtan duális fogalma. G= (V N , V T , S, H) alakban adjuk meg, a generatív nyelvtanhoz hasonló módon. Szemben azonban a generatív nyelvtannal, itt azt feltételezzük fel, hogy minden Hbeli szabály jobb oldala legalább egy V N -beli betűt tartalmaz A G analitikus nyelvtan által acceptált, elfogadott, vagy felismert nyelv: L(G)= {p∈V T * | p⇒S}, vagy

L(G)= L aG ∩V T *, L(G)⊆L aG . 2.1 Tétel: Tekintsünk egy tetszőleges G=(V N , V T , S, H) generatív (analitikus) nyelvtant Alkossuk meg hozzá az összes olyan QP szabályok H 1 halmazát, melyekre PQ∈H. Ekkor G 1 =(V N , V T , S, H 1 ) analitikus (generatív) nyelvtanra L(G 1 )=L(G). Eszerint minden generatív, vagy analitikus nyelvtan befoglalható egy vele ekvivalens duális nyelvtannal alkotott párba 5 3. Chomsky-féle nyelvosztályok Az oszályozás alapját a helyettesítési szabályok alakjára vonatkozó kikötések képzik abban a hierarchiában, amelyet az elmélet egyik megalapozója Noam Chomsky vezetett be az ötvenes évek végén. Legyen G=(V N , V T , S, H) tetszőleges generatív nyelvtan, és legyen i∈{0, 1, 2, 3}. Azt mondjuk, hogy a G i-típusú nyelvtan, ha H-ra az alábbi feltételek közül az i feltétel teljesül. 0) Nincs külön feltétel, kivéve persze, hogy a szabály bal oldala legalább egy nemterminális betűt tartalmaz. 1) Minden

H-beli szabály P 1 XP 2 P 1 QP 2 alakú, ahol P 1 , P 2 ∈(V N ∪V T )*, X∈V N , Q∈(V N ∪V T )+, vagy pedig Sλ alakú. Utóbbi esetben felteszzük, hogy S nem lép fel egyetlen H-beli szabály jobboldalán sem 2) Minden H-beli szabály XQ alakú, ahol X∈V N , Q∈(V N ∪V T )*. 3) Minden H-beli szabály vagy XpY, vagy pedig Xp alakú, ahol X, Y∈V N , p∈V T *. Definíció: Egy formális nyelv akkor • reguláris, jobb-lineáris, véges állapotú vagy 3-as típusú, • környezetfüggetlen (context-free) vagy 2-es típusú, • környezetfüggő (context-sensitive) vagy 1-es típusú, • általános, mondatszerkezetű (phrase-structure) vagy 0-ás típusú, ha rendre 3-as, 2-es, 1-es, illetve 0-ás típusú nyelvtan generálja. Lineáris nyelvtanról akkor beszélünk, ha a szabályok vagy Xp, vagy Xp 1 Yp 2 alakúak, ahol X, Y∈V N , p, p 1 , p 2 ∈V T *. Speciálisan, ha az összes Xp 1 Yp 2 alakú szabályokban p 2 =λ, akkor 3-as típusú nyelvtanról

beszélünk, ha p 1 =λ, akkor bal-lineáris nyelvtanról beszélünk. Bebizonyítható, hogy a ballineáris grammatikával generálható nyelvek generálhatók jobblineáris grammatikával is. Definíció: A G és G’ nyelvtanokat ekvivalensnek nevezzük egymással, ha L(G)=L(G’). Definíció: Egy grammatikát λ-menetesnek nevezünk, ha az általa generált nyelv nem tartalmazza az üres szót. 3.1 Tétel: Legyen G=(V N , V T , S, H) generatív nyelvtan, és tegyük fel, hogy H-ban vannak olyan szabályok, melyek jobb oldali része tartalmazza S-et Ekkor létezik G’ nyelvtan, hogy L(G)=L(G’) és G’ helyettesítési szabályai jobb oldalán nem szerepel G’ mondatszimbóluma. 3.2 Tétel (Üres szó lemma): Minden környezetfüggetlen G nyelvtanhoz megadható vele olyan ekvivalens G’ nyelvtan, melyre teljesülnek a következők. 1) λ∉L(G) esetén a G’-beli szabályok jobboldalán λ nem fordul elő. 2) λ∈L(G) fennállásakor egyetlen G’-beli szabály S’λ,

alakú, ahol S’ a G’ mondatszimbóluma. Ez esetben az is teljesül, hogy S’ nem fordul elő egyetlen G’-beli szabály jobboldalán sem. Bizonyítás: Legyen G=(V N , V T , S, H) környezetfüggetlen grammatika. Megszerkesztünk hozzá egy G 1 =(V N , V T , S, H 1 ) nyelvtant a következő módon. Definiáljuk először az U i halmazokat az alábbi módon: U 1 ={X | Xλ∈H}, i≥1. U i+1 =U i ∪{X | XQ∈H és Q∈U i *}, Mivel U 1 ⊆U 2 ⊆.⊆U i ⊆⊆V N , és V N véges, ezért ∃k: U k =U k+1 =U k+m , m≥1 Ekkor a G-beli X⇒*λ (X∈V N ) pontosan akkor teljesül, ha X∈U k . Tehát λ∈L(G), akkor és csak akkor ha S∈U k Definiáljuk most a H 1 szabályhalmazt a következőképpen. Legyen XP 1 ∈H 1 pontosan akkor, ha P 1 ≠λ és van olyan XP∈H, hogy P 1 =P, vagy P 1 előállítható P-ből úgy, hogy P-ből U k -beli elemet vagy elemeket hagyunk el Ekkor nyilvánvaló, hogy L(G 1 )⊆L(G){λ} De megfordítva L(G){λ}⊆ L(G 1 ) is fennáll, hiszen ha

S⇒*P (G-ben) és P≠λ, akkor fennáll P∈L(G 1 ) is, mivel Pnek egy G-beli levezetése esetén minden Xλ alakú szabály alkalmazása helyett vehetjük a megfelelő H 1 -beli szabályokat. Így azt kaptuk, hogy L(G){λ}=L(G 1 ) Ha tehát • ha λ∉L(G), akkor G’=G 1 , • ha λ∈L(G), akkor legyen G’=(V N ∪{S’}, V T , S’, H 1 ∪{S’λ, S’S}), ahol S’ az új mondatszimbólum. A fenti tétel alapján a 2-es típusú nyelvtanokat a következőképpen is definiálhattuk volna. 2’-típúsú nyelvtan: Minden H-beli szabály vagy XQ alakú, aholis X∈V N , Q∈(V N ∪V T )+, vagy pedig Sλ alakú. Ez utóbbi esetben feltesszük, hogy S nem lép fel egyetlen H-beli szabály jobboldalán sem 6 Vegyük észre, hogy az 1-es típusú nyelvtanból a 2’-típusú nyelvtant úgy tudjuk származtatni, hogy az 1-es típusú nyelvtan definíciójában szereplő P 1 XP 2 P 1 QP 2 formájú szabályok mindkét oldaláról töröljük a P 1 , P 2 szavakat, azaz más

szavakkal a 2’-ben olyan 1-beli P 1 XP 2 P 1 QP 2 formájú szabályokat tekintünk, melyekre P 1 =P 2 =λ. Jelölje tetszőleges i∈{0, 1, 2, 3} esetén L i az összes i-típusú nyelvek osztályát. A fenti tétel szerint nyertük tehát L 2 ⊆L 1 -et, ami az 1-es, 3-as típusú nyelvek definíciójából rögtön látható L 1 ⊆L 0 , illetve L 3 ⊆L 2 összefüggések miatt az L 3 ⊆L 2 ⊆L 1 ⊆L 0 fennállást jelenti. Bebizonyítható, hogy ez a hierarchia valódi, azaz fennáll az L 3 ⊂L 2 ⊂L 1 ⊂L 0 összefüggés is. 7 4. Speciális nyelvtani alakok 4.1 Jobb-lineáris nyelvtan Jobbról reguláris nyelvtan: A G= (V N , V T , S, H) nyelvtan jobbról reguláris, ha minden szabálya vagy XxY, vagy Xx, vagy pedig Xλ alakú, ahol X, Y∈V N , x∈V T . 4.1 Tétel: Minden 3-as típusú nyelvtanhoz megadható egy vele ekvivalens jobbról reguláris nyelvtan Bizonyítás: Legyen G=(V N , V T , S, H) tetszőleges 3-típusú nyelvtan. A H-beli szabályok az alábbi

alakúak lehetnek: 1) Xx 1 x 2 .x k Y, k≥2; 2) Xx 1 x 2 .x k , k≥2; 3) XY; 4) XxY; 5) Xx; 6) Xλ; ahol, X, Y∈V N , x i ∈V T . Megmutatjuk, hogy megszerkeszthető olyan G-vel ekvivalens grammatika, amely (1)-(3) alakú szabályokat nem tartalmaz. • Minden (1) alakú szabály esetén vezessünk be új Y 1 ,.,Y k-1 ∉V N ∪V T nemterminálisokat, töröljük H-ból a tekintett (1) alakú szabályt, s vegyük fel helyette H-ba az Xx 1 Y 1 , Y 1 x 2 Y 2 ,.,Y k-1 x k Y szabályokat • Minden (2) alakú szabály esetén vezessünk be új Y 1 ,.,Y k-1 ∉V N ∪V T nemterminálisokat, töröljük H-ból a tekintett (2) alakú szabályt, s vegyük fel helyette H-ba az Xx 1 Y 1 , Y 1 x 2 Y 2 ,.,Y k-1 x k szabályokat • Minden Z∈V N -re definiáljuk az U(Z)={Z’ | Z’⇒*Z} halmazokat. Hagyjuk el ezután a (3) alakú szabályokat, s minden H-beli H-beli XxY szabály esetén vegyük fel H-ba az összes X’xY, X’∈U(X) szabályt, továbbá minden H-beli Xλ esetén vegyük

fel az összes X’λ, X’∈U(X) szabályt. 4.2 Környeztfüggetlen nyelvtan A környezetfüggetlen nyelveket igen gyakran használják magasszintű programozási nyelvek szintaxisának megadására. Normális alak: Egy G= (V N , V T , S, H) nyelvtant normális alakúnak hívunk, ha a terminálisok csak Xx alakú szabályok jobboldalán fordulnak elő, ahol X∈V N , x∈V T . 4.2 Tétel: Minden i∈{0, 1, 2} típusú nyelvtanhoz van vele ekvivalens normális alakú i-típusú nyelvtan Bizonyítás: Legyen G=(V N , V T , S, H) egy i (∈{0, 1, 2}) típusú nyelvtan és konstruáljuk meg hozzá a G’=(V N ’, V T , S, H’) grammatikát úgy, hogy • ∀x∈V T -hez rendeljük hozzá A x ∉V N -et, és V N ’=V N ∪{A x | ∀x∈V T }; • PQ∈H (P és Q nem tartalmaz terminálist)⇒ PQ∈H’; • PQ∈H (P vagy Q tartalmaz terminálist)⇒ ∀x∈V T helyébe helyettesítsük A x -et és P’Q’∈H’; • ∀x∈V T : A x x∈H’. 4.3 Tétel: Legyen i∈{0, 1} Ekkor

minden i-típusú nyelvtanhoz van vele ekvivalens olyan i-típusú nyelvtan, melynek szabályai baloldalán terminális betű nem fordul elő (Az állítás i∈{2, 3} esetén triviálisan teljesül) Chomsky-féle normálalak: Egy G= (V N , V T , S, H) nyelvtant Chomsky-féle normálalakúnak hívunk, ha minden szabálya vagy Xx vagy pedig XYZ alakú, ahol X, Y, Z∈V N , x∈V T . Világos, hogy minden Chomsky-féle normálalakú nyelvtan λ-mentes környezetfüggetlen nyelvtan 4.4 Tétel: Minden λ-mentes környezetfüggetlen nyelvtanhoz megadható vele ekvivalens Chomsky-féle normálalakú nyelvtan 8 Bizonyítás: A 3.2 és 42 tétel értelmében elegendő olyan G=(V N , V T , S, H) λ-mentes, normális alakú nyelvtanokra szorítkozni, melyek szabályainak jobb oldalán az üres szó nem fordul elő Megszerkesztjük először a G 1 =(V N ’, V T , S, H 1 ), majd a G’=(V N ’, V T , S, H’) nyelvtanokat. Legyen H 1 =H A G nyelvtan szabályaira a következő négy alak

állhat fenn. 1) Xx (X∈V N , x∈V T ). Ez megfelel a követelményeknek 2) XYZ (X, Y, Z∈V T ). Ez szintén megfelel a követelményeknek 3) XY 1 Y 2 Y k (k≥3, X, Y i ∈V N .) Legyen V N ’=V N ∪{Z 1 .Z k-2 ∉V N } H 1 -ben a 3-as alakú szabályokat helyettesítsük a következőkkel: XY 1 Z 1 , Z 1 Y 2 Z 2 , . Z k-2 Y k-1 Y k . Így kaptunk egy G 1 =(V N ’, V T , S, H 1 ) grammatikát, melyre L(G 1 )=L(G). 4) XY (X, Y∈V N ). Minden X∈V N ’ betűhöz definiáljuk a következő halmazokat: u 1 (X)={X}, u i+1 (X)=u i (X)∪{Y∈V N | ZY∈H valamely Z∈u i (X)-re} Így u 1 (X)⊆u 2 (X)⊆.⊆u k (X)=u k+1 (X), mivel V N véges u(X):=u k (X). Így ∀X, Y∈V N ’: X⇒*Y ⇔ Y∈u(X). Definiáljuk most a H’ halmazt a következőképpen: a) Sa∈H’ ⇔ ∃X∈u(S): Xa∈H 1 (S a mondatszimbólum). b) H’-be kerüljenek még H 1 szabályai közül az Aa alakúak, ahol A∈V N ’ , a∈V T . c) XYZ∈H’ ⇔ ∃A, B, C∈V N ’: ABC∈H 1 és A∈u(X),

Y∈u(B) és Z∈u(C). A G’= (V N ’, V T , S, H’) grammatika Chomsky-féle normálalakú, és L(G’)=L(G), mivel az XY alakú szabályok alkalmazását pótolhatjuk, az a)–c) alatti szabályok alkalmazásával és megfordítva. Legbaloldalibb levezetés: Valamely környezetfüggetlen G nyelvtan esetén legbaloldalibbnak hívunk egy S⇒P 1 ⇒P 2 ⇒.⇒P m= p, p∈V T * levezetést, ha minden egyes lépésben a szereplő szó legbaloldalibb nemterminálisát helyettesítjük egy megfelelő szabály alkalmazása útján. 4.5 Tétel: Minden G környezetfüggetlen nyelvtan és p∈L(G) szó esetén létezik p-nek legbaloldalibb G-beli levezetése 4.6 Segédtétel: Tekintsünk egy G= (V N , V T , S, H) környezetfüggetlen nyelvtant, melynek adott A, B∈V N párra létezik egy AP 1 BP 2 ∈H szabálya. Legyen BQ 1 ,, BQ n az összes olyan H-beli szabály, melynek baloldalán a B változó áll, s legyen H’= (H{AP 1 BP 2 }∪{AP 1 Q 1 P 2 ,., AP 1 Q n P 2 } Ekkor a G nyelvtan

ekvivalens a G’=(V N , V T , S, H’) nyelvtannal. 4.7 Segédtétel (Kiküszöbölős lemma): Legyen adva egy G=(V N , V T , S, H) környezetfüggetlen nyelvtan, s tekintsük valamely A∈V N mellett az összes olyan AAX 1 ,, AAX r H-beli szabályokat, melyek baloldalán az A nemterminális áll, jobboldalán pedig ugyanezen nemterminálissal kezdődik. Jelölje AY 1 ,,AY k az összes többi olyan H-beli szabályokat, melyek baloldala A. Vegyük azt a G’=(V N ’, V T , S, H’) nyelvtant, ahol alkalmas Z∉V N ∪V T mellett V N ’=V N ∪{Z}, H’ pedig úgy adódik, hogy H-ból elhagyjuk az összes olyan szabályt, melynek baloldalán A áll, s felvesszük helyettük az • AY 1 Z,., AY k Z illetve • ZX 1 ,., ZX r , ZX 1 Z,, ZX r Z szabályokat. Ekkor a két nyelvtan ekvivalens Greibach-féle normálalak: Egy G= (V N , V T , S, H) nyelvtant Greibach-féle normálalakúnak hívunk, ha minden szabálya XxP alakú, ahol X∈V N , x∈V T , P∈V N *. 4.8 Tétel: Minden λ-mentes

környezetfüggetlen nyelvtanhoz megadható vele ekvivalens Greibach-féle normálalakú nyelvtan (A tétel bizonyítása a fenti két segédtétel felhasználásával történik) 9 4.3 Környezetfüggő nyelvtan Hosszúságot nem csökkentő nyelvtan: Olyan nyelvtan, melyben a szabályok baloldala legfeljebb olyan hosszú, mint a jobboldala. Nyilván minden λ-mentes környezetfüggő nyelvtan ilyen 4.9 Tétel: Minden hosszúságot nem csökkentő nyelvtanhoz megadható egy vele ekvivalens λ-mentes környezetfüggő nyelvtan Bizonyítás: Legyen G=(V N , V T , S, H) egy hosszúságot nem csökkentő grammatika. Feltehetjük, hogy a grammatika normális alakban van Legyen X 1 X 2 X m Y 1 Y 2 Y n ∈H (X i , Y i ∈V N ) egy tetszőleges szabálya G-nek, ahol m≤n. m=1 esetén a szabályunk speciális környezetfüggő szabály, nevezetesen olyan környezetfüggetlen szabály, melynek jobboldala nem az üres szó. Legyen m≥2 és vezessünk be m darab új Z 1 ,,Z m ∉V N ∪V T

nemterminálist, hagyjuk el H-ból az X 1 X 2 .X m Y 1 Y 2 Y n alakú szabályt és vegyük fel a következő új szabályokat: X 1 .X m Z 1 X 2 X m , Z 1 X 2 .X m Z 1 Z 2 X 3 X m , . Z 1 .Z m-2 X m-1 X m Z 1 Z m-1 X m , Z 1 .Z m-1 X m Z 1 Z m Y m+1 Y n , Z 1 .Z m Y m+1 Y n Y 1 Z 2 Z m Z m+1 Y n , . Y 1 .Y m-1 Z m Y m+1 Y n Y 1 Y m Y n Belátható, hogy így az eredeti grammatikával ekvivalens grammatikát kapunk. Ezek az új szabályok pedig megfelenek az 1-típusú grammatika előírásainak. Kuroda-féle normálalak: Egy G= (V N , V T , S, H) nyelvtant Kuroda-féle normálalakúnak hívunk, ha szabályai a következő alakúak lehetnek: Aa, AB, ABC, ABCD, ahol A, B, C, D∈V N , a∈V T . 4.10 Tétel: Minden hosszúságot nem csökkentő nyelvtanhoz megadható vele ekvivalens Kuroda-féle normálalakú nyelvtan. Bizonyítás: Legyen G=(V N , V T , S, H) egy hosszúságot nem csökkentő grammatika. Feltehetjük, hogy a grammatika normális alakban van Legyen PQ∈H, P= X 1 X m ,

Q= Y 1 Y n Világos, hogy a grammatika tulajdonságai miatt m≤n. • m=1, n=1, 2 esetén a szabályunk megfelelő alakban van. • m=2, n=2 esetén úgyszintén. • m=1, n>2 esetben járjunk el úgy, ahogy azt a Chomsky-féle normálalaknál tettük. • m≥2, n≥3 esetben vezessünk be új Z 1 , Z 2 ,., Z n-1 nemterminális jeleket és vegyük a következő szabályokat: Z m Y m Z m+1 , X 1 X 2 Y 1 Z 2 , Z m+1 Y m+1 Z m+2 , Z 2 X 3 Y 2 Z 3 , . . Z n-1 Y n-1 Y n . Z m-1 X m Y m-1 Z m , Ezekkel a szabályokkal helyettesítve az eredeti szabályokat, a kiinduló grammatikánkkal ekvivalens grammatikát kapunk. A fenti két tétel alapján jutunk el a következő állításhoz. Következmény: Minden λ-mentes környeztfüggetlen grammatikához megadható vele ekvivalens Kuroda-féle normálalakban megadott grammatika. 4.31 Révész észrevételei a Kuroda-féle normálalakról 4.11 Tétel (Révész-féle első észrevétel): A Kuroda-féle normálalak ABCD alakú szabályai

helyettesíthetők a következő környezetfüggő szabályokkal: • ABAB’, • AB’A’B’, • A’B’A’D, • A’DCD, ahol A’, B’ új nemterminálisok. 10 Ennél megadható egy általánosabb Penttonen-féle megfogalmazás, mely szerint elegendő olyan ABCD alakú szabályokra szorítkozni, aholis vagy minden ilyen szabály baloldali környezetfüggő azaz ABAB’ formájú, vagy pedig minden ilyen szabály jobboldali környezetfüggő, azaz ABA’B formájú. 4.12 Tétel (Révész-féle második észrevétel): A Kuroda-féle normálalak ABCD alakú szabályai általában nem helyettesíthetők a következő három környezetfüggő szabállyal: • ABA’B, • A’BA’D, • A’DCD, ahol A’ új nemterminális. 4.4 Mondatszerkezetű nyelvtan Révész-féle normálalak: Egy G=(V N , V T , S, H) nyelvtant Révész-féle normálalakúnak nevezünk, ha szabályai a következő alakúak lehetnek: 1) Sλ, 2) Zz, 3) ZY, 4) ZXY, 5) XZXY, 6) ZYXY, 7) ZYY, ahol X, Y,

Z∈V N , z∈V T továbbá az S mondatszimbólum csak a szabályok baloldalán fordulhat elő. 4.13 Tétel: Minden mondatszerkezetű nyelvtanhoz létezik vele ekvivalens Révész-féle normálalakú nyelvtan Bizonyítás: Tekintsünk egy G=(V N , V T , S, H) mondatszerkezetű nyelvtant. Hagyjuk el a H összes Pλ alakú szabályát, s minden ilyen szabály esetén vegyük fel H-ba az összes xPx és Pxx alakú szabályt, ahol x befutja a teljes V N ∪V T ábécét. Világos, hogy az így nyert új G’ nyelvtan minden egyes ilyen xPx és Pxx szabályának alkalmazása helyett ugyanazt érjük el, ha a G nyelvtanban a Pλ szabályt alkalmazzuk. Ezáltal egy olyan G’ grammatikát kapun, amelyre L(G’)=L(G)-{λ}. Ha λ∈L(G), akkor a G’-be felvesszük még az Sλ szabályt, s ezzel L(G’)=L(G). Ezután hozzuk a nyelvtant normális alakra Az összes PQ (P, Q∈V N *, P≠λ, Q≠λ) szabályok közül azokra, melyekre |P|≤|Q| alkalmazzuk a Kuroda-féle normálalakra hozásnál

alkalmazott helyettesítéseket, illetve a Révész-féle első észrevételnél alkalmazott helyettesítéseket. Így tehát a |P|>|Q| eset vizsgálata maradt hátra Tekintsünk egy ilyen X 1 X m Y 1 Y n , m>n≥1 szabályt Hagyjuk el ezt a szabályt, s alkalmas új U 1 ,,U m , Z n+1 ,, Z m nemterminálisokat és új Z m U m U m ,, X m-1 X m Z m U m , Z m-1 U m-1 U m-1 , X m-2 U m Z m-1 U m-1 , . . Z n+1 U n+1 U n Y n , X n U n+2 Z n+1 U n+1 , X n-1 U n U n-1 Y n-1 , . X 1 U 2 U 1 Y 1 , U 1 Y 1 Y 1 szabályokat vezessünk be, majd a fellépő ABCD alakú szabályokat ismét helyettesítsük a Révész-féle első észrevételnél alkalmazott módon. A fenti bizonyításban szerepelt egy nem konstruktív, csupán egzisztenciális állításon alapuló lépés. Nem tudjuk ugyanis, hogyan lehet általában eldönteni azt a kérdést, hogy λ∈L(G) igaz-e vagy sem. Ha a grammatikában nincsen Pλ alakú szabály, akkor biztos, hogy λ∉L(G) De, ha vannak Pλ alakú szabályok,

abból még nem feltétlenül következik, hogy λ∈L(G) Egy olyan G’ grammatikát mindig tudunk készíteni, amelyre L(G’)=L(G)-{λ}, de, hogy az Sλ szabályt felvegyük-e, vagy sem, ahhoz tudnunk kell, hogy λ∈L(G) igaz-e, vagy sem. Ezért fogalmaztuk úgy a tételt, hogy „létezik olyan grammatika”, és nem mondtuk azt, hogy „megadható” 4.14 Tétel (Savitch tétele a mondatszerkezetű nyelvtanokról): Minden mondatszerkezetű nyelvtanhoz létezik olyan vele ekvivalens nyelvtan, melynek szabályai vagy Av, vagy ABλ alakúak lehetnek, aholis A, B nemterminálisokat jelölnek, v pedig tetszőleges mondatformát. 11 A fenti tételnek Villiam Geffert további erősebb változatát adta ki. 4.15 Tétel (Villiam Geffert, 1991): Minden mondatszerkezetű nyelvtanhoz létezik olyan vele ekvivalens nyelvtan, melynek • környezetfüggetlen szabályai Sv alakúak, ahol v∈(V N ∪V T )*, • környezetfüggő szabályi az alábbiak valamelyike: a) ABλ, CDλ, b) ABλ,

CCλ, c) AAλ, BBBλ, d) ABBBAλ, e) ABCλ. 4.16 Tétel: Minden nyelvtanhoz létezik vele ekvivalens olyan nyelvtan, mely legfeljebb három darab nemterminális betűt tartalmaz, és legfeljebb egy olyan szabályt, mely nem környezetfüggetlen, s minden környezetfüggetlen szabály bal oldalán a mondatszimbólum áll. 12 5. Iterációs tételek és a Chomsky-hierarchia Az iterációs tételeket más néven pumpálós lemmáknak is szokták nevezni. Mielőtt ezekre rátérnénk definiáljuk a levezetési fa fogalmát. Levezetési fa: Környezetfüggetlen és reguláris grammatikák minden levezetése nagyon egyszerűen ábrázolható egy irányított gráf - méghozzá fa - segítségével. Tekintsünk egy S⇒*P levezetést. A fa csúcsainak nemterminális, illetve terminális szimbólumokat feleltetünk meg: a fa gyökeréhez S-t, leveleihez rendre terminális szimólumokat, a közbülső csúcsaihoz pedig nemterminális jelet rendelünk. Az egy csúcsból kiinduló élek

annak a helyettesítési szabálynak az alkamazását jelölik, amelynek bal oldalán az élek közös kiindulási pontjában található nemterminális jel áll, a jobb oldalán pedig az élek végpontjaiban található nemterminális, illetve terminális jelek sorozata (az egyes éleket balról jobbra véve sorra). Azt, hogy az egyes szabályokat milyen sorrendben alkalmazzuk, nem mindig tudjuk egyértelműen rekonstruálni. 5.1 Tétel (Pumpálós lemma reguláris nyelvekre): Legyen L reguláris nyelv Ekkor létezik az L-hez olyan n konstans, hogy ha p egy n-nél nem rövidebb L-beli szó, akkor alkalmas u, v, w szavakra teljesülnek a következők: p=uvw, |uv|≤n, |v|>0, továbbá tetszőleges nemnegatív i-re uviw∈L. Bizonyítás: Tekintsünk egy G=(V N , V T , S, H) nyelvtant, amely a kérdéses nyelvet generálja. A 41 tétel értelmében feltehető, hogy G jobbról reguláris Legyen n>|V N | Ha minden L(G)-beli szó n-nél rövidebb, tételünk nyilvánvalóan fennáll

Tegyük fel most, hogy van az L(G)-nek legalább egy n-nél nem rövidebb p szava, és tekintsük ennek egy levezetését Ekkor ez szükségképpen S⇒x 1 X 1 ⇒x 1 x 2 X 2 ⇒.⇒x 1 x n-1 X n-1 ⇒⇒x 1 x m X m ⇒x 1 x k (=p) alakú lesz, ahol k=m, vagy k=m+1, attól függően hogy az utolsó lépésben Xx vagy Xλ (X∈V N , x∈V T ) alakú szabályt alkalmaztunk, továbbá k≥n. Ekkor viszont a levezetésben szereplő S, X 1 , X 2 ,,X n-1 ,,X m nemterminálisok sorozatában n>|V N | miatt található legalább két ugyanolyan A nemterminális. Bevezetve S-re az X 0 jelölést, jelölje c≥0 azt a legkisebb indexet, melyre X c =A legalább kétszer előfordul az X 0 ,.,x n-1 ,,X m sorozatban, és legyen d az első olyan index, melyre X c =X d , és c≠d Ekkor 0≤c<d<n Amennyiben c=0, azaz X c =S, úgy legyen u=λ, v=x 1 .x d , w=x d+1 x k , ha pedig c>0, akkor legyen u=x 1 x c , v=x c+1 x d , w=x d+1 x n c<d miatt rögtön látható, hogy |v|>0 fennáll.

(Természetesen u=λ és/vagy w=λ is fennállhat Nevezetesen u=λ akkor fog teljesülni, ha c=0, a w=λ pedig d=k mellett fog fennállni. Utóbbi eset úgy áll elő, hogy levetésünk utolsó lépésében a szóban forgó X d nemterminálisra az X d λ szabályt alkalmazzuk) Mutassuk meg azt is, hogy |uv|≤n Mivel c a legkisebb olyan index, melyre X c =X d , továbbá d pont az első olyan index, amelyre ez teljesül, c≤|V N | és d≤|V N |+1≤n, vagyis valóban, |uv|=|x 1 .x d |≤n Végül, ha A=X c =X d és 0≤c<d<n fennállást figyelembe véve tekintjük az S⇒x 1 X 1 ⇒x 1 x 2 X 2 ⇒.⇒x 1 x n-1 X n-1 ⇒⇒x 1 x m X m ⇒x 1 x k (=p) levezetést, azt kapjuk, hogy fenn kell állnia az S⇒*uA, A⇒vA és A⇒w összefüggéseknek is. Ennek alapján közvetlenül belátható az is, hogy tetszőleges nemnegatív i-re uviw∈L. Ezzel a bizonyítás befejeztük Következmény: Az {anbn | n≥1} nyelv nem reguláris. Bizonyítás: Tegyük fel hogy az, s jelöljön n

egy konstanst, mely mellett L(G) kielégíti a reguláris pumpálós lemma tulajdonságait. Ilyen n-et viszont nem fogunk találni, hiszen az anbn szó minden olyan uvw felbontására, melyre |uv|≤n és |v|>0 azt kapjuk, hogy uw=an-|v|bn, azaz uw∉L(G). A fenti gondolatmenet alapján tehát valóban, L 3 ≠L 2 érvényes. 13 5.2 Lemma: Ha egy bináris fának valamely n természetes szám esetén van legalább 2n+1 számú végpontja, akkor létezik a fában a gyökértől a fa valamelyik végpontjába vezető olyan út, mely legalább n+1 hosszú. Bizonyítás: Ha n=1, az állítás nyilvánvalóan igaz. Tegyük fel, hogy az állítás valamely k természetes szám mellett minden n≤k-ra igaz. Ekkor elegendő igazolnunk, hogy állításunk n=k+1 mellett is fennáll Tekintsünk tehát egy 2k+1+1 végpontú F bináris fát, s képezzük azon F’, F” részfákat, melyeket úgy nyerünk, hogy tekintjük az F gyökérpontjából kiinduló két él végpontjait, mint

gyökérpontokat. Mivel F minden végpontja az F’ és F” részfák végpontjainak valamelyike lesz, legalább az egyik részfa fog tartalmazni 2k+1 végpontot Feltevésünk miatt tehát lennie kell ezen a legalább 2k+1 végpontú bináris részfában egy olyan útnak, mely a részfa gyökerétől az egyik végponthoz vezet és legalább k+1 hosszú. Ezen út elejéhez hozzávéve azt az élet, mely az F fa gyökerétől a kérdéses részfa gyökeréhez vezet, egy alkalmas, legalább k+2 hosszúságú úthoz jutunk. Ezzel a bizonyítás befejeztük Az alábbi állítás szükséges feltételt fog adni arra, hogy egy nyelv környezetfüggetlen legyen, és igen hasznosan lehet alkalmazni a környezetfüggetlen grammatikák elméletében. Ezenkívül még számtalan más iterációs lemma is van környezetfüggetlen nyelvekre. Például: Bader-Moura lemma (1982), Nechniv-Ito-Katsura lemma, Hayashi lemma (1973). 5.3 Tétel (Bar-Hillel lemma, pumpálós lemma környezetfüggetlen

nyelvekre): Legyen L környezetfüggetlen nyelv. Létezik L-hez olyan m, n≥1 természetes számpár úgy, hogy minden p∈L szó, amelyre |p|≥m, felírható p=uvwxy alakban úgy, hogy • |vwx|≤n, • |vx|>0, és minden i≥0 egész számra uviwxiy∈L. Bizonyítás: Röviden ez a lemma azt mondja ki, hogy egy környezetfüggetlen nyelvben minden elég hosszú szóhoz végtelen sok (rokon szerkezetű) további szó található. • Tekintsünk egy G=(V N , V T , S, H) nyelvtant, amely a kérdéses nyelvet generálja. Az üres szó lemma miatt feltehető, hogy a G nyelvtan 2’ típusú. Mivel tételünk csak 0-nál nagyobb hosszúságú szavakra vonatkozik, ezért elhagyhatjuk G-ből az Sλ szabályt. Ekkor viszont feltehetjük azt is, hogy G Chomsky-féle normálalakban van megadva • Legyen k=|V N |, és legyen m=2k-1+1, n=2k. • Amennyiben minden L(G)-beli szó m-nél rövidebb állításunk máris teljesül. Legyen tehát valamely p∈L(G)-re |p|≥m. Tekintsünk egy

ilyen p szónak egy G-beli levezetéséhez tartozó F levezetési fát, s hagyjuk el ezen fából az összes végpontokat, és mindazon éleket, melyek végpontjai a fának is végpontjai voltak A Chomsky-féle normálalak speciális volta miatt a keletkező F’ fa egy olyan bináris fa lesz, melynek ugyancsak m számú végpontja van, s minden egyes csúcspontja – beleértve a végpontokat is – nemterminálissal lesz megcímkézve. Alkalmazva az 52 lemmát az így keletkezett F’ bináris fában lesz olyan legalább |V N | hosszúságú út, amely a gyökérponttól valamelyik végpontig vezet. Vegyük a leghosszabb ilyen utak egyikét, és ennek az útnak az utolsó |V N | szakaszát • Ekkor azonban ezen a szakaszon eggyel több csúcspont található, mint amennyi él, vagyis |V N |+1 számú. Emiatt található ezen az úton két olyan csúcs, amely ugyanazzal az A nemterminálissal van megcímkézve. • Vegyük az F’ fa azon F” részfáját, melynek gyökérpontja a

két A-val megcímkézett csúcspont közül az F’ gyökérpontjához közelebb álló csúcspont. Mivel az előbbiek szerint az A-ból kiinduló leghosszabb út pontosan |V N | hosszúságú, ezért az F” fának legfeljebb n=2k (k=|V N |) számú csomópontja van • A gyökérponthoz legközelebb álló A csomóponthoz tartozó részfa által reprezentált levezetés eredményét jelölje q. A másik előfordulásához, mint gyökérponthoz tartozó részfa által reprezentált levezetés eredményét jelölje w Világos, hogy ekkor A⇒*w, továbbá alkalmas v, x terminális szavakra A⇒+vAx teljesülése mellett q= vwx. Tekintettel arra, hogy G Chomsky-féle normálalakú nyelvtan, A⇒+vAx csak úgy lehetséges, ha |vx|≠0, mivel a levezetésnek egy lépést mindenképpen tartalmaznia kell, tekintve, hogy A-nak két különböző előfordulásáról van szó. Emellett nyilván fennáll alkalmas u, y terminális szavakra S⇒*uAy, A⇒+vAx és A⇒*w következtében

S⇒uviwxiy, i≥0 egész. 14 • A tételhez még azt kell belátni, hogy |vwx|≤n, ahol n= 2k, k= |V N |. Ez viszont figyelembe véve azt, hogy |vwx| megegyezik az F” fa végpontjainak számával, teljesül. Ezzel befejeztük a bizonyítást Következmény: Az {aibici | i≥1} nyelv nem környezetfüggetlen. Bizonyítás: Ha volna olyan környezetfüggetlen grammatika, amely generálja ezt a nyelvet, akkor a lemma szerint volna olyan P=uvwxy szó, hogy vx≠λ, és minden i≥0-ra uviwxiy ehhez a nyelvhez tartozik. Az uviwxiy=ajbjcj öszszefüggést azonban az u, v, w, x, y szavak semmilyen konkrét választása mellett sem lehet végtelen sok i-re és j-re kielégíteni. Ugyanis v és x közül egyik sem tartalmazhat többféle betűt Ha viszont csak egyfélét tartalmaznak, akkor az a, b, c közül legalább az egyiknek a kitevője i-től független lesz. A fenti gondolatmenettel egyben, L 2 ≠L 1 is igazolást nyert. 5.4 Tétel: Bármely G= (V N , V T , S, H)

környezetfüggő grammatikáról és tetszőleges p∈V T * szóról eldönthető, hogy p∈L(G) fennáll-e. Bizonyítás: Vegyük észre, hogy tetszőleges 1-es típusú grammatika esetén az esetleges Sλ szabálytól eltekintve minden egyes szabály baloldalának hossza legfeljebb akkora, mint a jobboldalé. Ráadásul, tekintettel arra, hogy az Sλ szabály fellépésekor S nem fordulhat elő egyetlen szabály jobboldalán sem, minden olyan esetben, amikor S⇒W 1 ⇒W 2 ⇒.⇒W t ⇒p levezetés első lépésében nem Sλ szabályt alkalmazzuk, az Sλ szabályt egyetlen további lépésben sem tudjuk alkalmazni. Ha p=λ, akkor a p∈L(G) pontosan akkor teljesül, ha Sλ∈H, ami nyilván eldönthető Feltehetjük tehát, hogy p∈V T * és p≠λ. Ekkor |S|≤|W 1 |≤≤|V t |≤|p| fog fennállni Tehát a levezetés egyetlen lépése sem eredményezhet |p|-nél hosszabb szót. Nyilvánvaló, hogy ha egy szó G-ben levezethető, akkor levezethető ismétlődéseket nem

tartalmazó levezetésekkel. Képletben, ha S=W 0 ⇒W 1 ⇒⇒W t ⇒p mellett W i =W j teljesül, valamely 0≤i<j≤t párra, akkor S= W 0 ⇒.⇒W i ⇒W j+1 ⇒⇒W t ⇒p is fennáll, ahol j= t esetén a W j+1 ⇒.⇒W t lépések értelemszerűen elmaradnak Az ilyen ismétlődéseket nem tartalmazó levezetések száma véges. Nevezetesen, nem nagyobb, mint a V N ∪V T ábécé feletti, |p|-nél nem hosszabb szavakból álló ismétlődés nélküli szósorozatok hossza, vagyis p i ∑ VN∪VT . i=1 Tehát meg kell vizsgálni, hogy az ismétlődés nélküli |p|-nél hosszabb szavakat nem tartalmazó levezetések közt van-e olyan, melynek utolsó lépéseként p adódik. Ha igen, p∈L(G), különben pedig p∉L(G) Megjegyzés: Ez az eldöntési mód gyakorlati célra nemigen alkalmas, inkább elvi jelentőségű. E tétel értelmében tehát az L 1 ≠L 0 összefüggés igazolást nyer, ha sikerül kimutatni, hogy nincs olyan általános algoritmus, mely tetszőleges G=(V

N , V T , S, H) mondatszerkezetű grammatikáról és tetszőleges p∈V T * szóról eldöntené, hogy p∈L(G) fennáll-e. A Turing-gépeknél, a 1510 tétel alapján látni fogjuk, hogy van olyan rész-osztálya a mondatszerkezetű nyelveknek, melyre ilyen általános eldöntő algoritmus nincs. Így tehát L 1 ≠L 0 is bizonyítható, amivel L i+1 ⊂L i , i=0, 1, 2 bizonyítását teljesen befejeztük. 15 6. Eldönthetőség, szintaktikai elemzés Eldönthetőség: A formális nyelvek elméletének egyik jellegzetes problémája annak eldöntése, hogy egy adott szó beletartozik-e egy adott nyelvbe. Ez az 1, 2, 3-típusú nyelvek esetén eldönthető, de a 0-típusú nyelvek esetén, mint látni fogjuk általában algoritmikusan nem eldönthető. Eldöntési eljárás: Egy eljárás, mely olyan kérdésre keresi a választ, ahol csak igen vagy nem választ várunk. Eldöntési algoritmus: Minden olyan eljárás, amely a feltett kérdésre véges sok lépésben igen vagy nem

választ ad. Algoritmikus eldönthetőség: Egy kérdést (problémát) algoritmikusan eldönthetőnek nevezünk, ha megadható hozzá egy eldöntési algoritmus. Szintaktikus elemzés: A gyakorlati alkalmazásoknál általában nem elég egy formális nyelv felismerési problémáját csupán eldöntési problémának tekinteni, hanem egy p∈L szóról azt is meg kell állapítanunk, hogy az hogyan vezethető le az adott grammatikában. Egy-egy szó generálása során a generatív grammatikák, egyúttal egy belső szerkezetet is rendelnek a szóhoz. A környezetfüggetlen nyelveknél például a levezetési fa igen jól tükrözte ezt a belső szerkezetet. Ugyanahhoz a szóhoz természetesen több különféle belső szerkezetet is hozzárendelhetünk A generálás során adódó struktúrát a továbbiakban szintaktikus struktúrának nevezzük, azt a folyamatot pedig, amelylyel megállapítjuk egy-egy adott szóról, hogy az adott grammatika generálja-e, és felveheti-e a szó

megfelelő szintaktikai struktúráját szintaktikus elemzésnek. A szintaktikus elemzés igen fontos részét képezi a programozási nyelvek fordítási folyamatának, egy-egy szakasz fordítása ugyanis a szintaktikus struktúrák közötti megfeleltetés megadását követeli meg Szintaktikus elemző: Legyen G tetszőleges környezetfüggetlen grammatika. A G szintaktikus elemzőinek az olyan automatákat nevezzük, melyek tetszőleges p szóról eldöntik, hogy L(G)-hez tartozik-e, és ha p∈L(G), akkor megadják az p szó G-beli levezetési fáit is. Legyen adva egy G=(V N , V T , S, H) környezetfüggetlen grammatika. Nézzük meg hogyan végezhetünk G alapján szintaktikus elemzést. Hozzuk a G-beli grammatikát Greibach-féle normálalakra A G-beli szabályok tehát mind XdX 1 X k alakúak, ahol X, X 1 ,,X k nemterminális jelek, d pedig valamilyen terminális jel. Elemezzük az ω=d 1 d n szót. Keressük meg G szabályai között az Sd 1 X 1 X i típusúakat. Ha ilyen

szabály nincs, akkor az ω szó nem tartozhat az L(G) nyelvbe. Ha van ilyen szabály, akkor vegyük az első ilyet, és alkalmazzuk azt S-re Folytassuk az eljárást ezután az X 1 d 2 Y 1 Y j típusú szabályok keresésével. Ha valamikor megakadunk a folyamatban, térjünk vissza a legutolsó olyan helyre, ahol még kihasználatlan választási lehetőségünk maradt, és innentől kezdve most már egy új úton haladjunk tovább. Nyilvánvaló, hogy véges sok lépés alatt el tudjuk dönteni ω-ról, hogy a G grammatika generálja-e vagy sem, és ugyancsak véges sok lépésben megkaphatjuk ω összes G-beli levezetését is. Az is igaz, hogy bármely ω szó levezetése pontosan |ω| lépésből áll. Ha a szintaktikus elemzés során a levezetési fa megkeresését a kezdőszimbólummal kezdjük, akkor azt mondjuk, hogy az elemzés felülről lefelé történt. Ilyen elemzés a fenti is 6.1 CYK-algoritmus A Cocke-Younger-Kasami-algoritmust, Chomsky-féle normálalakú

nyelvtanok esetében alkalmazhatjuk. A felismerő algoritmus a szabályok alapján egy tetszőleges bemenőszóhoz igyekszik megkonstruálni a megfelelő levezetési gráfot. A Chomsky-féle normálalak miatt ez – a végpontokba befutó élektől eltekintve – egy bináris fa lesz, amelynek méretét a bemenőszó hosszúsága fogja meghatározni. Ha például a bemenőszó mindössze négybetűs, akkor az összes lehetséges levezetési fának a száma öt Egy n hosszúságú bemenőszó esetében a levezetési fa összes lehetséges szögpontjai egy olyan háromszögmátrixba rendezhetők, amelynek a legalsó sora n-elemű, és minden további sora eggyel kevesebb elemű, mint a közvetlenül alatta lévő sor. Egy adott fa természetesen nem használhatja fel az összes szögpontját ennek a mátrixnak, csak n=2 esetben. A felismerési algoritmus ennek a háromszögmátrixnak az elemeit alulró fölfelé fogja meghatározni, úgy hogy minden szögponthoz beírja azokat a

nemterminálisokat, amelyekből a kérdéses szögpont alatti részháromszög végpontjainak megfelelő bemenőszórészlet levezethető. Ha a mátrix kitöltését befejeztük, akkor már csak azt kell megnéznünk, hogy a háromszög legfelső csúcsához be van-e írva az S Ha igen, akkor az adott bemenőszó levezethető az S-ből, tehát hozzátartozik az 16 adott grammatika által generált nyelvhez. Ellenkező esetben viszont biztos, hogy nem tartozik hozzá, mert a kitöltés során minden lehetőséget kimerítettünk. A szóban forgó háromszögmátrixot felismerési mátrixnak nevezzük, és minden elemének tulajdonképpen egy rekeszt feletetünk meg, ahová a változókat beírjuk. Ezeket az alábbi ábrán megadott módon indexeljük A kitöltést az első sornál kezdve soronként balról-jobbra, a sorokat pedig alulról felfelé történő sorrendben töltjük ki Legyen adva egy G= (V N , V T , S, H) környezetfüggetlen grammatika, és legyen a megvizsgálandó

bemenőszó w=a 1 a 2 .a n Az F felismerési mátrix első sorának i-edik rekeszébe beírjuk az X-et, ha szerepel egy Xa i szabály a grammatikában. (Ugyanabba a rekeszbe általában több változót is beírhatunk) A mátrix további sorainak kitöltésekor, minden egyes rekesz tartalmának a meghatározása az adott rekesz alatti részháromszög befogói mentén található rekeszek tartalmának felhasználásával történik Pontosabban az (i, j) rekesz kitöltéséhez az (1, j) rekeszben található változókat egyenként párosítjuk az (i-1, j+1) rekeszben találhatókkal, majd ugyanezt tesszük a (2, j) és (i2, j+2),., (i-1, j) és (1, j+i-1) rekesz-párokkal Ha egy ilyen párosítás alkalmával olyan párt találunk, amely szerepel egy szabály jobb oldalán, akkor a szabály baloldalán álló változót felvesszük az (i, j) rekeszbe A feldolgozás menetét az alábbi ábra szemlélteti. Tehát azokat az ABC alakú G-beli szabályokat keressük, amelynél B a

baloldali rekeszben, C a joboldali rekeszben található, és az új rekeszbe beírjuk A-t. A CYK algoritmus lépései a következők. 1) w:=a 1 a 2 .a n ; 2) for j:=1 to n do begin F[1, j]:=∅; F[1, j]:= F[1, j]∪{A | ∃a∈V T : Aa∈H és w[j]=a}; end; 3) for i:=2 to n do for j:=1 to n-i+1 do begin F[i, j]:=∅; for k:=1 to i-1 do F[i, j]:=F[i, j]∪{A | ABC∈H és B∈F[k, j] és C∈F[i-k, j+k]}; end; 4) if F[n, 1]={S} then out(‘A w szó levezethető G-ben.’) else out(‘A w szó nem vezethető le G-ben.’); 17 Példa Tekintsük a következő grammatikát. G=({S, A, B, C, D}, {a, b}, S, H), ahol a H szabályhalmaz a következő: SAB, ABC, BSC, CDD, DBA. SCB, Aa, Bb, Cb, SCD, SSS, Legyen w=aabbaba. A w-hez megkonstruált felismerési mátrixot és levezetési fát az alábbi ábrák szemléltetik Hangsúlyozni kell, hogy a szintaktikai elemzés során az eredetileg adott grammatikában való levezetéseket keressük, mert az adott szó grammatikai szerkezetét ebben

a grammatikában akarjuk leírni. Nem hozhatjuk tehát minden további nélkül valamilyen számunkra kedvező normálalakra az adott grammatikát, ahogy azt az előzőekben tettük, hiszen a levezetéseket az eredeti szabályokkal kell megadnunk. Környezetfüggetlen nyelvek esetén alkalmazható egy általános algoritmus, amely tetszőleges környezetfüggetlen grammatikára igen hatékonyan oldja meg a szintaktikai elemzést. Ezt az alábbiakban ismertetjük 6.2 Early-algoritmus Az Early-algoritmusnál (1970) az adott bemenő szóhoz egy felismerési mátrixot készítünk. A felismerési mátrix elemei pontozott szabályokat tartalmaznak. Legyen mondjuk AXY, ahol X, Y∈(V N ∪V T )*, egy tetszőleges szabálya az adott környezetfüggetlen G grammatikának. Ekkor az AXY egy az eredeti szabályhoz tartozó pontozott szabály lesz, ahol a pont lényegében azt jelzi, hogy adott szabály tekintetében balról jobbra haladva meddig jutottunk el az elemzésben. Szemléltetésül

tekintsük az alábbi ábrát, ahol a levezetési fát nagyvonalúan háromszögekkel jelképeztük. Az ábra az elemzésnek egy közbülső stádiumában rendelkezésünkre álló információt tükrözi. Eszerint az elemzéssel a bemenő szó j-edik betűjéig jutottunk el, miközben megállapítottuk, hogy léteznek olyan W, Z, X, Y∈(V N ∪V T )* szavak, melyekre S⇒WAZ, W⇒a 1 .a i , X⇒*a i+1 .a j és AXY∈H Ezt a körülményt fejezzük ki azzal, hogy az AX.Y pontozott szabályt beírjuk a felismerési mátrix i-edik sorának j-edik elemébe 18 A felismerési mátrixot az alábbi módon indexeljük. 0, 0 0, 1 0, 2 1, 1 1, 2 2, 2 0, n 1, n 2, n n, n A felismerési mátrix egyel több sort és oszlopot tartalmaz, mint a ahány betűből a bemenő szó áll. A P∈L(G) pontosan akkor teljesül, ha a 0-adik sor n-edik elemében szerepel egy SUZ alakú pontozott szabály, valamely U, Z∈(V N ∪V T )* szavakra, ahol Z⇒λ. (Az előbbiek értelmében ugyanis ez azt

jelenti, hogy SU∈H és U*a 1 .a n ) Jelöljük a felismerési mátrix i-edik sorának j-edik elemét F i, j -vel. A felismerési mátrix kitöltését oszloponként alulról fölfelé végezzük, kivéve a fődiagonálisban lévő elemeket, amelyeket az adott oszlopban utoljára töltjük ki Az egyes oszlopokat ugyanakkor balról jobbra haladva vesszük sorra. (A mondottakból következik, hogy az F n,n kitöltésére tulajdonképpen nincs szükség) Az Early-féle algoritmus lépései a következők. 1) j=0, minden SW∈H szabályra S.W∈F 0, 0 2) B.U∈F j,j , ha BU∈H és ∃i≤j, hogy AXZBY∈F i,j , A∈V N , X, Y, Z∈(V N ∪V T )*, Z⇒λ. 3) Ha j<n, akkor j:=j+1, i:=j-1. Ha j=n, akkor készen vagyunk 4) AXZa j .Y∈F i, j , ha AXZa j Y∈F i, j-1 , és Z⇒*λ. 5) AXZB.Y∈F i,j , ha ∃k, melyre i≤k<j, és AXZBY∈F i,k , ahol Z⇒*λ, BU.∈F k,j , U∈(V N ∪V T )*. 6) Ha i>0, akkor i:=i-1 és térjünk vissza a negyedik lépésre, különben térjünk

vissza a második lépésre. Ezzel az algoritmussal tehát megadtuk a felismerési mátrixot, amelyből a P szó levezetése viszonylag egyszerűen rekonstruálható, amennyiben P∈L(G). Az algoritmus helyességének a bizonyításához be kell látnunk a következő tételt. 6.1 Tétel: Az Early-féle algoritmussal nyert felismerési mátrixban egy AXY pontozott szabály pontosan akkor szerepel F i,j -ben, ha AXZY∈H, Z⇒*λ, X⇒a i+1 .a j , és van olyan Z∈(V N ∪V T )* szó, amelyre S⇒a 1 .a i AZ Bizonyítás: Először a feltétel szükségességét bizonyítjuk, a mátrix elemeire vonatkozó teljes indukcióval. Az F 0,0 esetében az 1. és 2 lépések szerint csak olyan pontozott szabályok jöhetnek szóba, ahol a jobb oldalon a pont előtti rész üres. Ha tehát AY, akkor vagy A=S és SY∈H, vagy AY∈H és S⇒*.AZ valamely Z szóra Az indukció ezek után az (i, j) indexpároknak egy olyan elrendezésével végezzük, amely pontosan megfelel a mátrix kitöltési

sorrendjének. A fődiagonális elemeit külön kell kezelnünk Tegyük fel tehát, hogy a bizonyítandó állítás minden F r, s -re teljesül, hacsak s<j, vagy s=j és i<r<j Legyen most AX.Y∈F i, j Ha i≠j, akkor ezt a szabályt csak az algoritmus 4 vagy 5 lépésében írhattuk be ide. Az első esetben X=X’a j és AX’a j Y∈F i, j-1 De akkor az indukciós feltevésből S⇒*a 1 .a i AZ következik, valamilyen Z szóra, és X’⇒*a i+1 .a j-1 , amiből az állításunk közvetlen adódik Ha viszont az 5 lépésben írjuk be a szabályt, akkor X=X’B valamely X’ szóra és B változóra úgy, hogy van egy olyan k index, melyre AX’.BY∈F i, k , és BU.∈F k, j valamely U szóra Az indukciós feltevésből most S⇒*a 1 .a i AZ, valamint X’⇒*a i+1 .a k , illetve S⇒*a 1 .a k BZ, és * U⇒ a k+1 .a j adódik Ezekből a BU∈H figyelembevételével nyilván X’B⇒*a i+1 .a k a k+1 a j amivel az állításunkat bebizonyítottuk Hátra van még az i=j

eset, vagyis a fődiagonálisban lévő elemek esete. Az indukciós feltevés ebben az esetben azokra az F r, s elemekre vonatkozik, ahol s<j, vagy s=j és 0<r<j. A fődiagonális elemeibe csak az algoritmus 2 lépésében írhattunk be szabályokat De itt is csak olyan BU alakú szabályok jöhetnek szóba, amelyekre van olyan i≤j, hogy AX.BY∈F i, j Itt az i=j eset is előfordulhat Tekintsük azonban azt a szabályt, amelyet az algoritmus először helyez el az F j, j -ben. Ebben az esetben az i<j kell, hogy fennálljon Az indukciós feltevésből tehát S⇒*a 1 .a i AZ és X⇒*a i+1 .a j következik Ugyanakkor nyilván A⇒*XBY is fennáll, amiből S⇒a 1 .a j BYZ következik, s ezzel az állításunkat igazoltuk. Az indukciós feltevést most már minden új szabály elhelyezésénél alkalmazhatjuk az F j, j -be beírt szabályokra is. Ha tehát egy BU szabályt az algoritmus azért vesz fel az F j, j -be, mert BU∈H, és AX.BY∈F j, j , akkor itt nyilván

X=λ és S⇒*a 1 .a j AZ, és ezért S⇒*a 1 .a j BYZ, amivel a bizonyítást befejeztük 19 A feltétel elégségességét ugyancsak teljes indukcióval végezzük. Először nézzük az F 0, 0 -t Tegyük fel, hogy S⇒*BZ teljesül valamely B változóra és Z szóra, és BU∈H. Az S⇒*BZ levezetés lépésszámára vonatkozóan egy külön teljes indukciót végzünk. Ha a lépésszám nulla, akkor B=S és Z=λ, és ezért az algoritmus a BU szabályt már az első lépésben felveszi az F 0, 0 -ba. Tegyük fel, hogy az állítás k lépésre igaz, és legyen az S⇒*BZ levezetés lépésszáma k+1. Ekkor nyilván van olyan A nemterminális és Z’ szó, hogy S⇒*AZ’, A⇒BZ”, ahol Z=Z”Z’ és az S⇒*AZ’ levezetés lépésszáma k. Ezért az indukciós feltevésből ABZ”∈F 0, 0 , tehát az algoritmus 2 lépése szerint BU∈F 0, 0 Most tegyük fel, hogy az algoritmus elégséges volta igaz minden olyan F r, s -re, ahol s<j, vagy s=j és i<r<j.

Legyen akkor AXY∈H, X⇒*a i+1 .a j , és S⇒*a 1 .a i AZ valamely Z szóra Ha most X=X’a j , akkor az indukciós feltevés szerint AX’.a j Y∈F i, j-1 , és az algoritmus 4 lépése alapján AX’a j Y∈F i, j Egyébként X= X’B, ahol B⇒*a k+1 .a j és X’⇒*a i+1 .a k valamely k-ra Az indukciós feltevésből most AX’BY∈F i, k és BU∈F k, j adódik valamilyen U szóra, amelyre U⇒*a k+1 .a j és BU∈H De akkor az algoritmus 5 lépése szerint AX’BY∈F i, j Végül vegyük a fődiagonális elemeit. Az indukciós feltevést most azokra az F r, s elemekre tesszük, amelyekre s≤j és 0<r<j Legyen tehát AY∈H és S⇒*a 1 .a j AZ Ez a levezetés nyilván átrendezhető úgy, hogy a változók közül a legbaloldalibbat helyettesítjük be először mindaddig, amíg az a j -t meg nem kapjuk Eszerint van egy olyan A’ változó, hogy S⇒*a 1 .a k A’Z’⇒*a 1 .a k a k+1 a j AZ”Z’, ahol Z”Z’⇒*Z. Ha itt k<j, akkor az indukciós feltevés

szerint A’a k+1 .a j AZ”∈F k, j , és így az algoritmus 2 lépése szerint AY∈F j, j A k=j esetében viszont az indukciós feltevést már nem alkalmazhatjuk az A’AZ” szabályra és az S⇒*a 1 .a j A’Z’ levezetésre, hiszen ez a levezetés véges számú lépésből áll, tehát véges számú lépésben el kell jutnunk egy olyan esethez, ahol k<j. Az A’.AZ”∈F j, j -ből pedig az algoritmus 2 lépése szerint AY∈F j, j következik, és ezzel a tétel bizonyítását befejeztük Az Early-féle algoritmusnál a levezetési fát lényegében felülről lefelé próbáljuk megszerkeszteni úgy, hogy párhuzamosan követjük az összes lehetséges alternatívát, miközben a terminális jelek felhasználásával fokozatosan kirekesztjük a nem megfelelőeket. Figyelemre méltó tulajdonsága az algoritmusnak, hogy a hatásfoka nem marad el az előbb ismertetett CYK-algoritmus hatásfokától. A memóriaigény tekintetében ennek az algoritmusnak a hatásfoka is

n2-tel arányos, a lépésszám tekintetében pedig az most is n3-al. Lehetséges ezt az algoritmust még tovább finomítani, de az általános környezetfüggetlen nyelvek időbonyolultságát mindeddig még csak n281 nagyságrendre sikerült leszorítani. 20 7. Automaták és néhány típusaik Kimenő jel nélküli automata vagy Medvegyev-féle automata: Olyan M=(A, X, δ) rendszer, amelyben • A: belső állapotok halmaza, A≠∅; • X: bemenő jelek halmaza, X≠∅; • δ: A×XA átmenetfüggvény. Az automaták diszkrét időskála mentén működnek, s ha valamely időpillanatban egy a∈A állapotban vannak, és ebben az állapotban kapnak egy x∈X bemenő jelet, akkor a következő pillanatban átmennek a δ(a,x) állapotba. Iniciális kimenő jel nélküli automata: M=(A, a 0 , X, δ), ahol • A: belső állapotok halmaza, A≠∅; • a 0 ∈A, iniciális vagy kezdőállapot; • X: bemenő jelek halmaza, X≠∅; • δ: A×XA átmenetfüggvény. Véges

állapotú automata: Véges belső állapothalmazzal rendelkező automata. Véges automata: Az automatához tartozó minden halmaz véges. Determinisztikus és nemdeterminisztikus automata: Ha az automatához tartozó átmenetfüggvények és kimenetfüggvények egyértékűek (δ: A×XA), akkor az automata determinisztikus, ellenkező esetben (δ: A×X2A) az automatát nem determinisztikusnak mondjuk. A nemdeterminisztikus automatánál δ átmenetfüggvénnyel meghatározzuk az összes lehetséges következő konfigurációt, amibe az eredeti átvihető Ezután az összes új konfigurációra is meghatározzuk a lehetséges új konfigurációkat stb. Teljesen definiált és parciális automata: Ha az átmenet- és kimenetfüggvénye minden (a,x) (a∈A, x∈X) párra értelmezve van, akkor az automatát teljesen definiáltnak mondjuk. Ellenkező esetben, amikor az átmenet és kimenet függvények valamelyike csupán részlegesen definiált, az automatát parciális automatának

nevezzük Rabin-Scott automata, felismerő automata vagy Acceptor: M=(A, a 0 , X, δ, A F ), ahol • A: belső állapotok nem üres, véges halmaza; • a 0 ∈A, iniciális vagy kezdőállapot; • X: a bemenő jelek véges halmaza, a bemenő ábécé; • δ: A×XA átmenetfüggvény; • A F ⊆A, a végállapotok halmaza. Működése: Legyen adva egy x 1 x 2 x k ∈X* bemeneti szó, és egy a∈A kezdeti állapot. Ekkor a 1 =δ(a, x 1 ) a 2 =δ(a 1 , x 2 ) a k =δ(a k-1 , x k ) Az automata működése végén azt kell eldönteni, hogy az a k ∈A F -nek vagy sem. Ha eleme, akkor M felismerte (elfogadta) a bemenő szót Ha nem eleme, vagy valamely <a j , x j+1 > párra, amely az automata működése közben adódott az átmenetfüggvény nincs értelmezve, akkor azt mondjuk, hogy az M nem ismerte fel (visszautasította) a bemenő szót 21 Mealy-automata: M=(A, X, Y, δ, η), ahol • A: belső állapotok nem üres, véges halmaza; • X: a bemenő jelek véges halmaza,

a bemenő ábécé; • Y: a kimenő jelek véges halmaza, a kimenő ábécé; • δ: A×XA átmenetfüggvény; • η: A×XY kimenetfüggvény. Moore-automata: M=(A, X, Y, δ, η), ahol • A: belső állapotok nem üres, véges halmaza; • X: a bemenő jelek véges halmaza, a bemenő ábécé; • Y: a kimenő jelek véges halmaza, a kimenő ábécé; • δ: A×XA átmenetfüggvény; • η: AY kimenetfüggvény. Működése: Legyen adva egy x 1 x 2 x k ∈X* bemeneti szó. Az a∈A kezdeti állapotból az η kimeneti függvény megadja az első kimeneti jelet, η(a)-t η(a)=y 0 a 1 =δ(a, x 1 ) η(a 1 )=y 1 a 2 =δ(a 1 , x 2 ) η(a k )=y k a k =δ(a k-1 , x k ) Működése eredményeként az y 0 y 1 y k kimeneti szót kapjuk. Ha a bemeneti szó λ (üres szó), akkor a kimeneti szó η(a). Megjegyzés: A Moore-automaták kimeneti szavában eggyel több betű van, mint a bemeneti szóban. A kimeneti jel csak a belső állapottól függ. Valószínűségi vagy sztochasztikus

automata: Abban különbözik a Mealy-féle automatától, hogy működése nem két függvénnyel van jellemezve, hanem egy P(a’, y | a, x) feltételes valószínűséggel, ahol P(a’, y | a, x) azon esemény bekövetkezésének valószínűségét jelenti, hogy az automata az a’ állapotba megy át és közben az y kimenő jelet adja ki, feltéve, hogy az előző időpillanatban az a állapotban volt és ebben az állapotban az x bemenő jelet kapta. Autonóm automata: Egy véges automatát autonóm automatának nevezünk, ha a bemenő jelek halmaza egyetlen elemből áll. Memória nélküli automata: Egy Mealy-féle automatát memória nélküli automatának nevezünk, ha állapothalmaza egyetlen elemből áll. Egy ilyen automata esetén a kimenő jel csupán a bemenő jel függvénye Automata generátorrendszere: Azt mondjuk, hogy egy B⊆A halmaz az M=(A, X, Y, δ, η) automata generátorrendszere, ha minden a∈A állapothalmazhoz van olyan b∈B és p∈X*, hogy a=u(δ(b,

p)), ahol u(z) a z szó utolsó betűje. Összefüggő vagy ciklikus automata: Az M automatát összefüggőnek nevezzük, ha létezik egyelemű generátorrendszere, röviden, generátoreleme. Egy M iniciális automatát akkor mondunk iniciálisan összefüggőnek, ha a kezdőállapota generátoreleme M-nek. Továbbá, egy automatát erősen összefüggőnek nevezünk, ha összefüggő és minden állapota generálja. 22 7.1 Az átmenet- és kimenetfüggvények értelmezésének kiterjesztése Legyen δ: A×X* A, η: A×X* Y úgy, hogy tetszőleges a∈A állapotra és az λ üres szóra teljesüljön δ(a, λ)=a, η(a, λ)=λ, továbbá, tetszőleges nem-üres p=x 1 x 2 x k ∈X* bemenő szó esetén legyen δ(a, p)=a 1 a 2 a k ∈A* és η(a, p)=y 1 y 2 y k ∈Y*, ahol a 1 =δ(a,x 1 ), a 2 =δ(a 1 , x 2 ), , a k =δ(a k-1 , x k ) és y 1 =η(a, x 1 ), y 2 =η(a 1 , x 2 ), , y k =η(a k-1 , x k ). Vagyis δ(a, px)=δ(a, p)δ(u(δ(a, p)), x), ahol u(z) a z szó utolsó betűjét

jelenti. 7.2 Automaták megadása táblázattal Egy M=(A, X, Y, δ, η) véges automatát megadhatunk az algebrában használatos Cayley-tábla alkalmas módosításával. Az M automata átmenet-kimenet tábláján olyan téglalap alakú táblázatot értünk, amelynek sorait és oszlopait rendre megjelöljük M bemenő jeleivel illetve állapotaival, és bármely a∈A, x∈X pár esetén az x-el jelölt sor és az a-val jelölt oszlop metszetébe a (δ(a, x), η(a, x)) vektort írjuk. Emellett megállapodunk abban, hogy ha M iniciális, akkor az első oszlopot M kezdő állapotával jelöljük meg Az M=(A, X, Y, δ, µ) Moore-féle automata átmenetkimenet táblája abban különbözik az előbbi táblától, hogy az x-el jelölt sor és az a-val jelölt oszlop fölé az a állapot µ(a) jele kerül. E táblából értelemszerű egyszerűsítéssel adódik egy kimenő jel nélküli automata átmenet táblája 7.3 Automaták megadása gráffal Egy véges automatát szemléletesen

megadhatunk irányított gráffal. Az M=(A, X, Y, δ, η) automata átmenet-kimenet gráfján (vagy átmenet diagramm) azt az irányított gráfot értjük, amelynek csúcsai az A állapothalmaz elemeivel vannak megjelölve, és az a és b állapotokkal megjelölt csúcsok pontosan akkor vannak, a-ból b-be irányított és (x, y) párral megjelölt éllel összekötve, ha az x∈X jel hatására M a-ból a b állapotba megy át, és ennél az átmenetnél az y∈Y jelet adja ki, azaz, δ(a, x)=b és η(a, x)=y. Azokat a csúcsokat, amelyek végállapotokat jelölnek valamivel külön meg kell jelölni (Például kettős kört rajzolunk köréjük) A kezdőállapotot jelképező csúcsot rendszerint azzal különböztetjük meg a többitől, hogy kívülről egy nyilat húzunk ebbe a csúcsba. Az átmenet diagramm definíciójából világosan látszik, hogy a diagrammal ábrázolt M automata pontosan akkor fogadja el p szót, ha a diagrammban van olyan irányított út, amely a

kezdőállapotból indul ki, valamelyik végállapotban ér véget, és amelynek az élei sorrendre nézve egyezően a p szó betűit tartalmazzák. 23 8. Automaták által indukált leképezések Alfabetikus leképezés: Az α: X* Y alakú leképezéseket alfabetikus leképezéseknek nevezzük. Az alfabetikus leképezések tehát olyan leképezések, amelyek szabad félcsoportot szabad félcsoportba képeznek le. Állapot által indukált leképezés: Egy M=(A, X , Y, δ, η) automata bármely a∈A állapotához hozzárendeljük az α a : p η(a, p) (p∈X*) alfabetikus leképezést, amelyet az a állapot által indukált leképezésnek nevezünk. Iniciális automata által indukált leképezés: Ha M iniciális automata az a 0 kezdő állapottal, akkor e kezdő állapot által indukált αa 0 leképezést az M iniciális automata által indukált leképezésnek nevezzük, és rá az α M jelölést használjuk. Automataleképezés: Egy α: X* Y alfabetikus leképezést

automataleképzésnek nevezünk, ha létezik olyan M iniciális automata, amelyre α=α M teljesül. 8.1 Tétel (Raney): Egy α: X* Y alfabetikus leképezés pontosan akkor automataleképezés, ha eleget tesz a következő feltételeknek: 1) α szóhossztartó, azaz minden p∈X* szóra |α(p)|=|p| teljesül; 2) α a szó kezdő szeleteit a képszó kezdő szeleteibe viszi át. Bizonyítás: A tétel szükségessége a δ(a, p)=a 1 a 2 a k ∈A* és η(a, p)=y 1 y 2 y k ∈Y*, ahol a 1 =δ(a,x 1 ), a 2 =δ(a 1 , x 2 ), , a k =δ(a k-1 , x k ) és y 1 =η(a, x 1 ), y 2 =η(a 1 , x 2 ), , y k =η(a k-1 , x k ) összefüggések alapján nyilvánvaló. Az elegendőség bizonyításához tegyük fel, hogy az α: X*Y leképezés eleget tesz az (1)-(2) feltételeknek. Akkor bármely p, q∈X* párra az α(pq) képszó felbontható (*) α(pq)= α(p)α p (q), |α(p)|=|p| alakban. Az α leképezésből kiindulva tetszőleges p∈X* szóhoz rendeljük hozzá azt az α p : X* Y leképezést,

melyre α p : q α p (q) α(pq)=α(p) α p (q), q∈X* teljesül. Az α p (p∈X*) leképezést az α leképezés állapotainak nevezzük. Speciálisan, α λ olyan állapota α-nak, melyre α λ =α (ahol λ az üres szó). Megmutatjuk, hogy az α p (p∈X*) leképezések is eleget tesznek az (1) és (2) feltételeknek. Valóban (*)-ból látható, hogy α p megtartja a szavak hosszát. Legyen most p, q, r∈X*. Akkor α(pqr)=α(p)α p (qr) és α(pqr)=α(pq)α pq (r)=α(p)α p (q)α pq (r). Mivel a bal oldalak egyenlők és az X* félcsoport szabad, ezért a két utolsó egyenlőségből kapjuk, hogy α p (qr)=α p (q)α pq (r), azaz, az α p leképezés a szó kezdő szeleteit a képszó kezdő szeleteibe viszi át, vagyis rá a (2) feltétel is teljesül. Alsó automata: Legyen A α ={α p | p∈X*} és alkossuk meg azt az M α =(A α , α, X, Y, δ α , η α ) iniciális automatát, amelyre δ α (α p , x)= α px , x∈X. η α (α p , x)= α p (x), Megmutatjuk, hogy M α

indukálja az α leképezést. Legyen e célból q=x 1 x 2 x k ∈X* tetszőleges bemenő szó. Akkor δ α (α, q)=δ α (α, x 1 x 2 x 3 .x k )=αx 1 αx 1 x 2 αx 1 x 2 x 3 αx 1 x 2 x k és így αM α (q)=η α (α, q)=η α (α, x 1 x 2 .x k )=α(x 1 )αx 1 (x 2 )αx 1 x 2 (x 3 )αx 1 x 2 x k-1 (x k )=α(q), 24 tehát az α=αM α egyenlőség valóban teljesül. Ezzel kimutattuk, hogy az (1) és (2) feltételeket kielégítő leképezések automataleképezések, amivel az elegendőség bizonyítását is befejeztük. A tétel bizonyítása során megkonstruált M α automatát az α leképezéshez tartozó alsó automatának nevezzük. Felső automata: Az α: X* Y automataleképezés indukálható azzal az Mα=(X, λ, X, Y, δα, ηα), automatával is, amelynél δα(p, x)=px, (ahol u(p) a p szó utolsó betűje). ηα(p, x)=u(α(px)) α M automatát az α automataleképezéshez tartozó felső automatának nevezzük. Egy α automataleképezés iniciális automatával

való realizálásánál fontos szempont, hogy az a lehető leggazdaságosabb, azaz, minél kevesebb állapottal bíró automatával történjék. Ebből a szempontból Mα felső automata a legrosszabb, az M α alsó automata viszont a lehető legjobb Így, ha az α automataleképezést a leggazdaságosabb módon akarjuk realizálni, akkor az α-hoz tartozó alsó automatát kell megkonstruálnunk 25 9. Automaták ekvivalenciája Definíció: Legyen M 1 =(A, X, Y, δ, η) és M 2 =(B, X, Y, δ’, η’) közös bemenő, illetve kimenő halmazzal bíró automaták. Azt mondjuk, hogy az M 1 automata a állapota ekvivalens az M 2 automata b állapotával, jelekben a=b, ha α a =α b fennáll, vagyis az a és b állapotok ugyanazt a leképezést indukáljak az M 1 illetve M 2 automatában. Magát az M 1 automatát akkor mondjuk ekvivalensnek az M 2 automatával, ha M 1 minden állapotához van M 2 -nek egy ezzel az állapottal ekvivalens állapota, és megfordítva, M 2 bármely

állapotához található M 1 -ben egy ezzel az állapottal ekvivalens állapot. Azt a tényt, hogy M 1 ekvivalens M 2 -vel így jelöljük: M 1 ≡M 2 9.1 Lemma: Az M 1 =(A, X, Y, δ, η) és M 2 =(B, X, Y, δ’, η’) automaták tetszőleges a∈A és b∈B állapotaira igaz az a≡b ⇒ δ(a, x)≡δ’(b, x) (x∈X) implikáció. 9.2 Tétel: Egy M automata minden A-homomorf képe ekvivalens M-el 9.3 Tétel: Egymással ekvivalens Rabin-Scott-féle automatákban a végállapotok halmazával előállított nyelvek megegyeznek egymással. A tétel fordítva nem igaz Tehát két Rabin-Scott-féle automata előállíthatja ugyanazt a nyelvet, de nem biztos, hogy a két automata elvivalens. Definíció: Két Rabin-Scott-féle automatát egymással gyengén ekvivalensnek mondunk, ha bennük a végállapotok halmazával ugyanaz a nyelv állítható elő. Így az előbbi tétel azt mondja ki, hogy ha két Rabin-Scott-féle automata egymással ekvivalens, akkor egymással gyengén

ekvivalensek is. 9.4 Tétel: A véges automaták ekvivalenciaproblémája algoritmikusan megoldható Definíció: Legyen M olyan Mealy-automata, amelynek bemeneti ábécéje X, kimeneti ábécéje Y, továbbá legyen N Moore-féle automata ugyanezekkel a bemeneti és kimeneti ábécékkel. Az M és N automatákat ekvivalensnek nevezzük, ha minden p bemeneti szóra bM(p)=N(p), ahol b az a kimeneti jel, amelyet az N automata kimenetfüggvénye a kezdőállapotban ad ki 9.5 Tétel (A Gill): Tetszőleges M Mealy-féle automatához megadható vele ekvivalens N Moore-féle automata Ha M véges, akkor N is véges. Bizonyítás: Legyen M=(A, X, Y, δ, η, a 0 ) Mealy-féle automata, és N=(A’, X, Y, δ’, µ, a 0 ’) Moore-féle automata. Ekkor • A’=A×Y, azaz az N belső állapotai <a, y> típusú rendezett párok (a∈A, y∈Y); • δ’(<a, y>, x)=<δ(a, x), η(a, x)>; • µ(<a, y>)=y; • A 0 ’=<a 0 , y 0 >, ahol y 0 tetszőleges kimeneti jel. 9.6

Tétel: Legyen N tetszőleges Moore-automata Ekkor létezik olyan Mealy-automata, amely ekvivalens N-el 26 10. Automaták algebrai elmélete Részautomata: Az M 1 =(A 1 , X 1 , Y 1 , δ 1 , η 1 ) automatát az M=(A, X, Y, δ, η) automata részautomatájának nevezzük, ha A 1 ⊆A, X 1 ⊆X, Y 1 ⊆Y és a δ 1 , η 1 függvények az A 1 ×X 1 halmazon egybeesnek a δ illetve η függvényekkel. M 1 valódi részautomatája Mnek, ha az A 1 , X 1 , Y 1 halmazok közül legalább az egyik valódi részhalmaza M megfelelő halmazának Ha az M iniciális automata, úgy M iniciális részautomatáján olyan részautomatát értünk, amely M kezdő állapotát tartalmazza és ugyancsak iniciális automata ezzel a kezdő állapottal. Azt a tényt, hogy M 1 részautomatája M-nek a következőképpen jelöljük: M 1 <M Definíció: A ϕ(⊆D×K) relációt a D halmaz K halmazba való egyértelmű leképezésének, függvénynek vagy egyszerűen csak leképezésnek nevezzük, ha

∀x∈D-hez pontosan egy olyan y∈K van, melyre (x, y)∈ϕ. A D halmaz a ϕ reláció értelmezési tartománya, a K halmaz pedig a ϕ képtere. A ϕ(x) elem az x elem képe, x pedig az ősképe A D minden elemének tehát csak egy képeleme van, a megfordítás azonban általában nem igaz. Jelölje R a D-beli elemek képeinek halmazát. Az R halmazt a ϕ reláció értékkészletének nevezzük Világos, hogy R⊆K Leképezéseknél az (x, y)∈ϕ helyett még a következő jelölések használatosak: ϕ(x)=y, xy, xϕx. A D halmaz ϕ leképezését K-ba így jelöljük: ϕ: DK. Definíció: Legyen M=(A, X, Y, δ, η), M’=(A’, X’, Y’, δ’, η’) tetszőleges automaták. Azt mondjuk, hogy a Ψ 1 : A A’, Ψ 2 : X X’, Ψ 3 : Y Y’ egyértelmű leképezésekből álló Ψ=(Ψ 1 , Ψ 2 , Ψ 3 ) leképezésrendszer M-nek M’-be való homomorfizmusa, ha minden a∈A, x∈X párra teljesülnek a Ψ 1 (δ(a, x))=δ’(Ψ 1 (a), Ψ 2 (x)), Ψ 3 (η(a, x))=η’(Ψ 1 (a), Ψ

2 (x)) feltételek. • Ha Ψ 1 , Ψ 2 , Ψ 3 egyértelmű leképezések ráképezések (szürjektívek), akkor azt mondjuk, hogy az M’ automata M-nek homomorf képe, vagy Ψ M-nek M’-re való homomorfizmusa és ezt így jelöljük: M∼M’. • Ha Ψ 1 , Ψ 2 , Ψ 3 egyértelmű leképezések egy-egy értelműek (injektívek), akkor azt mondjuk, hogy Ψ az M automatának M’-be való beágyazása vagy M-nek M’-be való izomorfizmusa. • Ha Ψ 1 , Ψ 2 , Ψ 3 leképezések bijektívek, akkor azt mondjuk, hogy M izomorf M’-vel, vagy M’ az M-nek izomorf képe, képletben: M≈M’. Homomorfizmus esetén tehát az M’ automata tud ugyanúgy viselkedni, mint az M automata, de ez fordítva nem feltétlenül igaz. Izomorfia elv: Két egymással izomorf automatát absztrakt szempontból azonosnak tekintünk, hiszen lényegében azonos viselkedésűek, csupán a hozzájuk tartozó halmazok elemeinek jelölésében térnek el egymástól. A ∼ homomorfia relácó reflexív és

tranzitív, a ≈ izomorfia reláció pedig ezen kívül még szimmetrikus is. Más szóval az izomorfia ekvivalenciareláció Iniciális automaták esetén a homomorfizmustól (és így az izomorfizmustól is) megköveteljük, hogy a leképezések végrehajtásakor a kezdő állapot kezdő állapotba menjen át. Állapot-homomorfizmus: Ha az M és M’ automatákra X=X’ és Y=Y’ teljesül, továbbá a Ψ 2 és Ψ 3 leképezések az X illetve Y halmazok identikus leképezései, akkor a Ψ 2 és Ψ 3 leképezésektől eltekinthetünk és a (Ψ 1 , Ψ 2 , Ψ 3 ) homomorfizmus az egyetlen Ψ=Ψ 1 leképezésbe megy át. Ekkor a fenti feltételek egyszerűen így írhatók: Ψ(δ(a, x))=δ’(Ψ(a), x), η(a, x)= η’(Ψ(a), x). Az ilyen h homomorfizmust állapot-homomorfizmusnak vagy A-homomorfizmusnak nevezzük. 27 Állapot-izomorfizmus: Speciálisan, ha a fenti Ψ leképezés egy-egy értelmű, akkor a leképezés állapot-izomorfizmus (vagy A-izomorfizmus), és maguk az M és

M’ automaták állapot-izomorfak. Osztályozás: Legyen M=(A, X , Y, δ, η) tetszőleges automata és R az A állapothalmazon értelmezett ekvivalenciareláció (reflexív, szimmetrikus, tranzitív). Ismeretes, hogy R indukálja az A halmaznak egy C R osztályozását, amelynél egy a, b∈A elempár pontosan akkor esik egy ekvivalenciaosztályba, ha a és b az R relációban állnak egymással, azaz ha C R [a] jelöli az a∈A által reprezentált osztályt, akkor C R [a]=C R [b]⇔aRb. Faktorhalmaz: Az A halmazon értelmezett R ekvivalenciarelációhoz tartozó ekvivalenciaosztályok halmaza az Anak R által meghatározott faktorhalmaza, melyet A R -el jelölünk. A R =<C R [a] | a∈A> Az ekvivalenciareláció osztályainak számát a reláció index-ének nevezzük. Egy osztályozást végesnek mondunk, ha az osztályok száma véges. Egy ekvivalenciarelációt véges indexűnek nevezünk, ha a hozzá tartozó osztályozás véges. Kongruenciareláció: Ha ∀a, b∈A és

∀x∈X esetén igaz az aRb⇒δ(a, x)Rδ(b, x) és η(a, x)=η(b, x) implikáció, akkor az R ekvivalenciarelációt kongruenciának nevezzük M-en. Bal kongruencia: Legyen A a belső állapotok halmaza és legyen R ekvivalenciareláció A-n. Az R relációt balkongruenciának nevezzük A-n, ha tetszőleges a, b∈A elemekre igaz az aRb⇒δ(a, xy)Rδ(b, xy) és η(a, xy)=η(b, xy) implikáció. Analóg módon definiálhatjuk az A jobb kongruenciáit Kompatibilis osztályozás: Az M automata A állapothalmazának olyan osztályozását, amelyek M kongruenciáihoz tartoznak, M kompatibilis osztályozásainak hívjuk. Könnyen belátható, hogy • ∀a∈A-ra, aRa (reflexivitás); • ∀a, b∈A-ra, ha aRb, akkor bRa (szimmetria); • ∀a, b, c∈A-ra, ha aRb és bRc, akkor aRc (tranzitivitás). Egy osztályozást bal kompatibilis, jobb kompatibilis illetve kompatibilis osztályozásnak mondunk aszerint, hogy a hozzá tartozó ekvivalenciareláció bal kongruencia, jobb kongruencia,

illetve kongruencia. A kompatibilis osztályozással kapott ekvivalenciaosztályokat mellékosztályoknak vagy maradékosztályoknak szokás nevezni Faktorautomata: Legyen R tetszőleges kongruencia az M=(A, X , Y, δ, η) automatán és alkossuk meg azt az M’=(A R , X, Y, δ’, η’) automatát, amelyre a δ’ és η’ függvényeket a δ’(C R [a], x)=C R [δ(a, x)] és η’(C R [a], x)=η(a, x) összefüggésekkel értelmezzük. Könnyen belátható, hogy M’ automata jól definiált Az M’ automatát az M automata faktorautomatájának nevezzük és rá az M/R vagy M/C R jelölést használjuk Ha az M automata iniciális és kezdő állapota a 0 , akkor az M/R faktorautomatát is iniciálisnak tekintjük a C R [a 0 ] kezdőállapottal. Az algebrából ismert általános homomorfia tétel automatákra vonatkozó alábbi specializálása azt fejezi ki, hogy egy automata A-homomorf képei és faktorautomatái lényegében (az A-izomorfiától eltekintve) azonosak. 10.1

Általános homomorfia tétel automatákra: Egy M automata tetszőleges R kongruenciájához tartozó M/R faktorautomata M-nek A-homomorf képe. Megfordítva, ha egy M’ automata az M automatának A-homomorf képe, akkor megadható az M automatán olyan S kongruenciareláció, amelyhez tartozó M/S faktorautomata A-izomorf az M’ automatával. 28 10.1 Redukált automata Definíció: Tetszőleges M=(A, X , Y, δ, η) automatán definiáljuk a következő R M relációt: aR M b ⇔ α a =α b (a, b∈A). Eszerint két belső állapot akkor lesz egy osztályban, ha egy tetszőleges szó beolvasása után, az automata a két belső állapotból ugyanabba az új állapotba megy át. Az R M relációt maximális kongruenciának, a megfelelő M/R M faktorautomatát pedig az M automatához tartozó redukált automatának nevezzük. Általában egy M automatát redukáltnak mondunk, ha tetszőleges a, b állapotaira aR M b ⇔ a=b teljesül. Végül, ha M iniciális az a 0 kezdő

állapottal, akkor az M/R M automatát is iniciálisnak tekintjük a CR M [a 0 ] kezdőállapottal. 10.2 Tétel: Tetszőleges M automatára az R M reláció kongruencia és M tetszőleges R kongruenciájához tartozó C R kompatibilis osztályozás finomítása az R M -hez tartozó C M kompatibilis osztályozásnak. 10.3 Tétel: Legyen M olyan iniciálisan összefüggő automata, amely az α leképezést indukálja Akkor M/R M redukált automata A-izomorf az M-hez tartozó alsó automatával 10.4 Tétel: Minden automata ekvivalens a hozzá tartozó redukált automatával és két automata pontosan akkor ekvivalens egymással, ha a hozzájuk tartozó redukált automaták A-izomorfak. 10.2 Véges automaták minimalizációja Az M=(A, X, Y, δ, η) automatához tartozó minimális automatán az M-el ekvivalens automaták közül azokat értjük, amelynek állapothalmaza a lehető legkisebb számosságú. Ez az automata létezik és az A-izomorfiától eltekintve egyértelműen

meghatározott, mégpedig A-izomorf az M 0 =M/R M faktorautomatával. Egy M automata minimalizálásán a hozzá tartozó M 0 redukált automata megszerkesztését értjük A következőkben egy D. D Aufenkamp-tól és F E Hohn-tól származó minimalizációs eljárással megmutatjuk, hogy véges automatákra a minimalizálási probléma algoritmikusan megoldható. Legyen M=(A, X, Y, δ, η) tetszőleges véges automata. Az M-hez tartozó M 0 minimális automata megszerkesztéséhez az R M maximális kongruenciához tartozó C M kompatibilis osztályozást kell megadnunk A C M osztályozást egyre finomodó olyan C 1 , C 2 , osztályozások sorozatán keresztül fogjuk elérni, amelyeket a következőképpen definiálunk. Legyen a, b∈A Akkor a C 1 osztályozást a C 1 [a]=C 1 [b] ⇔ ∀x(∈X): η(a, x)= η(b, x) ekvivalencia által definiáljuk, és ha valamely i (≥1) indexre C i már definiálva van, úgy legyen C i+1 [a]=C i+1 [b] ⇔ C i [a]=C i [b] és ∀x(∈X): C i [δ(a,

x)]=C i [δ(b, x)]. Ezzel az A állapothalmazon egy osztályozást definiáltunk, amelyre nyilván C 1 ⊇C 2 ⊇⊇C m ⊇ Megmutatható, hogy bármely i-re a C i osztályozásnál pontosan azok az állapotok kerülnek egy osztályba, amelyekből indulva az M automata minden legfeljebb i hosszúságú bemenő szóra ugyanazzal a kimenő jelsorozattal válaszol, azaz C i [a]=C i [b] ⇔ ∀p(∈X*, |p|≤i): α a (p)=α b (p). Bizonyítható, hogy létezik olyan m index, hogy C 1 ⊃C 2 ⊃C m =C m+1 = és nyilván C m megegyezik az M-hez tartozó R M maximális kongruenciát kísérő C M kompatibilis osztályozással, és így a keresett M 0 minimális automata az M/C m faktorautomatával. 29 11. Véges automaták és nyelvek kapcsolata A véges automatákat a formális nyelvek felismerőiként és átalakítóiként használják. Egy véges automatán általában az M=(A, a 0 , X, δ, A F ), ötöst értjük, ahol • A: belső állapotok nem üres, véges halmaza; • a 0

∈A, iniciális vagy kezdőállapot; • X: a bemenő jelek véges halmaza, a bemenő ábécé; • δ: A×XA átmenetfüggvény; • A F ⊆A, a végállapotok halmaza. Definíció: Egy M véges automata által felismert nyelv a következő: L(M)={p∈X* | u(δ( a 0 , p))∈A F , ahol u(z) a z szó utolsó betűjét jelenti.} Definíció: Egy véges automatát λ-menetesnek nevezünk, ha A 0 ∩A F =∅. 11.1 Tétel: Ha M tetszőleges nem teljesen definiált véges automata, akkor tudunk hozzá konstruálni egy vele ekvivalens teljesen definiált M’ véges automatát, amelyre L(M)=L(M’) Nyilvánvaló, hogy a determinisztikus véges automaták által felismert nyelvek osztálya része a nemdeterminisztukus véges automaták által felismert nyelvek osztályának. A determinisztikus véges automatákat ugynis felfoghatjuk úgy is, mint speciális nemdeterminisztukus véges automatákat. A most következő tétel az ellenkező irányú tartalmazást mondja ki. 11.2 Tétel: Minden M

nemdeterminisztikus véges automatához megadható olyan M’ determinisztikus véges automata, amelyre L(M)=L(M’) Bizonyítás: Legyen M=(A, a 0 , X, δ, A F ) olyan nemdeterminisztikus véges automata, amely felismeri az L nyelvet. Konstruáljuk meg az M’=(A’, a 0 ’, X, δ’, A F ’) determinisztikus véges automatát a következőképpen: • az A’ állapothalmaz elemei kölcsönösen egyértelműen megfeleltethetők A részhalmazainak; az {a 1 ,, a n }⊆A részhalmazhoz rendelt A’-beli belső állapotot jelöljük a[a 1 ,,a n ]-el; • • • minden x∈X betűre és minden a[a 1 ,,a n ] belső állapotra δ’(a[a 1 ,,a n ], x)=a[r 1 ,,r n ] pontosan akkor teljesül, ha {r 1 ,., r n }=δ(a 1 , x)∪δ(a 2 , x)∪∪δ(a n , x); a 0 ’=a[a 0 ]; A F ’ mindazokból az a[a 1 ,,a n ] belső állapotokból áll, amelyekre {a 1 , , a n }∩A F ≠∅. Ekkor L(M)=L(M’). 11.3 Tétel: Ha L tetszőleges 3-típusú nyelv, akkor találhatunk olyan nemdeterminisztikus

véges automatát, amely felismeri az L nyelvet. Bizonyítás: Mivel L nyelv jobb-lineáris a 4.1 tétel értelmében van olyan G= (V N , V T , S, H) jobbról-reguláris grammatika, amely L-et generálja. Készítsük el azt az M=(A, a 0 , X, δ, A F ) nemdeterminisztikus véges automatát, amelyre • A=V N ∪{E}, E∉V N ∪V T ; • X=V T ; • δ(B, x) tartalmazza mindazokat a D állapotokat, amelyekre G-ben szerepel a BxD szabály, továbbá legyen benne az E állapot is, ha G-ben szerepel a Bx szabály; • δ(E, x)=∅ minden x∈V T -re; • a 0 =S; • A F ={E}, ha G-ben nem szerepel az Sλ (üres szó) szabály, illetve A F ={E, S}, ha az Sλ szabály G-ben van. 30 11.4 Tétel: Ha az L nyelvet egy determinisztikus véges automata felismeri, akkor létezik olyan 3-típusú grammatika, amely az L nyelvet generálja Bizonyítás: Legyen M= (A, a 0 , X, δ, A F ) olyan determinisztikus véges automata, amely felismeri az L nyelvet. Definiáljuk a következő G=(V N , V T ,

S, H) grammatikát, melyre • V N =A; • V T =X; • S=a 0 ; • H minden olyan δ(a, x)=b (ahol a, b∈A, x∈X) egyenlőséghez tartalmaz egy axb (ahol a, b∈V N , x∈V T ) szabályt, továbbá δ(a, x)=b, b∈A F esetén tartalmaz egy kiegészítő ax szabályt is. Ekkor L(G)=L-{λ}. Ha λ∈L, akkor az előbbi G grammatikából készítsük el azt a G’=(V N ’, V T , S’, H’) grammatikát, melyre • V N ’=V N ∪{S’| S’∉(V N ∪V T )}; • S’ az új mondatszimbólum, S’ nem szerepel a szabályok jobb oldalán; • H’=H∪{S’λ}. Az így kapott új, szintén 3-típusú grammatika most már valóban L-et fogja generálni. A fenti három tétel alapján a determinisztikus, illetve nemdeterminisztikus véges automaták által felismert nyelvek osztálya megegyezik a 3-típusú grammatikák által generált nyelvek osztályával. A determinisztikus véges automaták által felismert nyelvek osztálya egyenértékű a nemdeterminisztikus véges automaták

által felismert nyelvek osztályának. 31 12. Véges automaták analízise és szintézise Analízis probléma: Adott tetszőleges automatához hogyan lehet meghatározni azt a leképezést, amelyet az automata indukál? Szintézis probléma: Tetszőleges alfabetikus leképezésről hogyan lehet eldönteni, hogy indukálható-e automatával, és ha igen, hogyan lehet megkonstruálni olyan automatát, amely ezt a leképezést indukálja? Egy véges automatát akkor tekintünk adottnak, ha átmenet- kimenet táblával, vagy átmenet- kimenet gráffal van megadva. Automataleképezések megadása viszont a végtelen értelmezési tartomány miatt nehézkes Az automataleképezések egy megadási módját a reguláris nyelv (vagy esemény) bevezetésével S C Kleene adta meg először 1956-ban. 12.1 Reguláris nyelv, reguláris kifejezés Reguláris nyelv: Az üres nyelv és azok a nyelvek, amelyek az elemi nyelvekből az alapműveletek (unió, szorzás, iteráció) véges számú

alkalmazásával előállíthatók. 12.1 Tétel: A reguláris nyelvek halmaza zárt a Boole-féle műveletekre nézve Reguláris nyelvek tulajdonságai: • Legyen L’ és L’’ tetszőleges reguláris nyelvek. Ekkor az L’∪L’’ nyelv szintén reguláris • Legyen L’ és L’’ tetszőleges reguláris nyelvek. Ekkor az L’⋅L’’ nyelv szintén reguláris • Legyen L tetszőleges reguláris nyelv. Ekkor az L iteráltja, L* szintén reguláris nyelv lesz. • Minden véges nyelv reguláris. 12.2 Tétel: Egy nyelv pontosan akkor reguláris, ha 3-as típusú Reguláris kifejezés: Legyen V tetszőleges ábécé. Ekkor 1. ∅ a V-ből alkotott reguláris kifejezés, és az üres halmazt jelöli; 2. λ szintén V-ből alkotott reguláris kifejezés, és a {λ} halmazt jelöli; 3. tetszőleges a∈V betűre a reguláris kifejezés, amely az {a} halmazt jelöli; 4. ha x és y V-ből alkotott reguláris kifejezések, amelyek az X, illetve az Y halmazokat jelölik, akkor

(x+y), (xy) és (x)* szintén V-ből alkotott reguláris kifejezések, és az általuk jelölt halmazok rendre X∪Y, XY, illetve X. 5. csak azt a kifejezést nevezzük reguláris kifejezésnek, ami az 1-4 szabályok véges sokszori alkalmazásával hozható létre. A reguláris kifejezés tehát megmutatja, hogy egy reguláris nyelv hogyan áll elő az alapműveletek segítségével. Példa: Az 1*+0(10)11 jelsorozat reguláris kifejezés, amely a következő halmazt jelöli: {1}*∪({0}⋅({1}⋅{0})⋅{1}⋅{1}). Megjegyzés: Különböző reguláris kifejezések is jelölhetik ugyanazt a halmazt. Például: (ba)*b és b(ab). Definíció: Két reguláris kifejezést ekvivalensnek nevezzük, ha ugyanazt a halmazt jelölik. Tetszőleges ábécéből alkotott reguláris kifejezésekre igazak az alábbi ekvivalenciák: x+y=y+x, x(y+z)=xy+xz, (x+y)+z=x+(y+z), (x+y)*=(x+y), (xy)z=x(yz), (x+y)*=(xy), (x+y)z=xz+yz, (x*)=x, ∅*=λ, xx*+λ=x. x+x=x, 32 12.2 Nyelvek előállítása

automatákban Definíció: Azt mondjuk, hogy egy X fölötti L nyelv egy M=(A, a 0 , X, δ) kimenő jel nélküli iniciális automatában az A állapothalmaz valamely A’ részhalmazával előállítható, vagy más szóval, az M automata az L nyelvet felismeri vagy elfogadja az A’(⊆A) halmazzal, jelekben A L = LM ha L azokból és csak azokból a p∈X* szavakból áll, amelyek hatására M az a 0 kezdő állapotból valamilyen A’-beli állapotba megy át. Az A’ állapothalmazt M végállapotainak nevezzük 12.3 Véges automaták analízise Véges automaták analízisén olyan algoritmus megadását értjük, amelynek segítségével bármely átmenet táblájával vagy átmenet gráfjával megadott M kimenő jel nélküli iniciális véges automatához és M állapothalmazainak bármely A’ részhalmazához fel tudjuk írni annak az L nyelvnek egy reguláris kifejezését, amely M-ben az A’ halmazzal előállítható. 12.3 Tétel: Minden véges automatában

előállítható nyelv reguláris nyelv Létezik olyan algoritmus, amelynek alkalmazásával bármely előre megadott véges iniciális automata és állapothalmazának tetszőleges előre kijelölt részhalmaza esetén fel tudjuk írni annak a nyelvnek egy reguláris kifejezését, amely ebben az automatában az adott halmazzal előállítható. Ilyen algoritmus létezését először S. C Kleene bizonyította be 1956-ban Az alábbiakban egy R F McNaughton és H. Yamada-tól származó algoritmus ismertetése található, amely egyben a fenti tétel konstruktív bizonyítását is szolgálja. Legyen M= (A, 1, X, δ) olyan átmenet táblájával megadott n állapotú véges automata, amelyre A= {1, 2,,n} és legyen A’={i 1 , i 2 ,,i k }⊆A. Azt kell megmutatni, hogy az X fölötti LA’ M nyelv reguláris és eljárást kell adni e nyelv egy reguláris kifejezésének felírására. Nyilvánvalóan érvényes ik i2 i1 A LM = LM ∪ LM ∪  ∪ LM egyenlőséget figyelembe véve

elegendő azzal az esettel foglalkozni, mikor az A’ halmaz egyetlen elemből áll. Legyen tehát a továbbiakban A’={m} Jelölje k L ij (i, j = 1, 2,  , n; k = 0, 1,  , n) azt a nyelvet, amely pontosan azokból a bemenő szavakból áll, amelyek hatására az M automata az i∈A állapotból a j∈A állapotba megy át, mégpedig legfeljebb az 1, 2,,k∈A állapotokon, mint közbülső állapotokon át. Speciálisan 0 L ij azt a nyelvet jelöli, melynek szavai hatására az M az i∈A állapotból közvetlenül, közbülső állapotok nélkül megy át a j∈A állapotba. Világos, hogy ilyen jelölés mellett A n L M = L1m ezért elegendő azt megmutatni, hogy az Ln 1m nyelv reguláris és létezik algoritmus e nyelv és egy reguláris kifejezés felírására. Ennél többet fogunk bizonyítani Nevezetesen k szerinti teljes indukcióval megmutatjuk ezt minden Lk ij (1≤i, j≤n; 0≤k≤n) nyelvre. Legyen k=0 és tekintsük M átmenet tábláját. Ha e tábla i-vel

jelölt oszlopában j nem fordul elő, akkor L0 ij az üres nyelv, tehát reguláris és reguláris kifejezésként vehető a ∅ szimbólum. Ha pedig a tábla i-vel jelölt oszlopában a j állapot fellép, akkor L0 ij azoknak az x t bemenő jeleknek – mint egyelemű nyelveknek – az összege, amelyekre δ(i, 33 x t )=j teljesül, tehát L0 ij most is reguláris nyelv és reguláris kifejezésként vehető a Σx t összeg. Ezzel megmutattuk, hogy az állítás k=0 esetén igaz. Legyen k≥1 és tegyük fel, hogy az állítást már minden k-nál kisebb felső indexre bebizonyítottuk, azaz tegyük fel, hogy az 0 1 k −1 L ij , L ij ,  , L ij (1 ≤ i, j ≤ n) nyelvek mind regulárisak és ismeretes egy-egy reguláris kifejezésük. Belátható, hogy érvényes az k k −1 k −1 k −1 * k −1 L ij = L ij + L ik + L kk ⋅ L kj rekurziós formula, amelynek segítségével az előbbi reguláris kifejezésből az Lk ij nyelv egy reguláris kifejezését is fel tudjuk

írni, így az az esemény is reguláris. ( ) 12.4 Véges automaták szintézise A véges automaták szintézisén olyan algoritmus megadását értjük, amelynek segítségével bármely véges X ábécé fölötti, reguláris kifejezésével megadott L reguláris nyelvhez meg tudunk konstruálni olyan M kimenő jel nélküli iniciális véges automatát, és ki tudjuk jelölni M állapothalmazainak olyan A’ részhalmazát, hogy az L nyelv az M automatában az A’ halmazzal előállítható. 12.4 Tétel: Minden reguláris nyelv előállítható véges automatákban Létezik olyan algoritmus, amelynek alkalmazásával bármely reguláris kifejezéssel megadott reguláris nyelvhez meg tudunk adni egy kimenő jel nélküli iniciális véges automatát és ki tudjuk jelölni a kapott automata állapothalmazának egy alkalmas részhalmazát úgy, hogy az adott nyelv ebben az automatában az állapothalmaz kijelölt részhalmazával előállítható. A szintézis probléma algoritmikus

megoldhatóságát S. C Kleene bizonyította be 1956-ban Most a szintézis probléma megoldására egy V M Gluskov-tól származó egyszerű eljárás ismertetése következik, amely eléggé gazdaságos abban az értelemben, hogy az esetek többségében a minimálishoz közeli automatát eredményez Emellett alkalmas arra, hogy segítségével véges sok, reguláris kifejezéssel megadott reguláris nyelvhez egyszerre szerkesszünk meg olyan iniciálisan összefüggő véges automatát, amelyben az adott nyelvek mindegyike előállítható az állapothalmaz egy-egy alkalmas részhalmazával. Az eljárás lényege, hogy számba vesszük azoknak a szavaknak a struktúráját, amelyek az adott nyelvek közül legalább egyben előfordulnak. Legyenek L 1 , L 2 ,, L k olyan reguláris nyelvek az X={x1, x2,, xn} ábécé fölött, amelyek reguláris kifejezésekkel vannak megadva. Az adott nyelveket azonosíthatjuk az őket leíró reguláris kifejezésekkel, így L 1 , L 2 ,, L k jelen

esetben nyelveket és reguláris kifejezéseket egyaránt jelölnek. A nyelvalgebra alapműveleteire megismert műveleti azonosságok alkalmazásával hozzuk a reguláris kifejezéseket minél rövidebb alakra, majd a bennük előforduló Xbeli betűket balról jobb felé haladva indexezzük meg alulról folytatólagosan az 1, 2 , természetes számokkal úgy, hogy az azonos betűk különböző előfordulási helyükön különböző indexeket kapjanak. Az ilyen betűket ezek után indexezett betűknek fogjuk nevezni. Legyenek u és v indexezett betűk Azt mondjuk, hogy az u indexezett betű megelőzi a v indexezett betűt, jelekben: u < v, ha létezik olyan p szó, amely benne van legalább egy L i (1≤i≤k) nyelvben és amely p=uv alakú. Az u betűt kezdő betűnek nevezzük, ha első betűje legalább egy olyan szónak, amely benne van legalább egy L i -ben és végül u betűt záró betűnek mondjuk, ha utolsó betűje legalább egy olyan szónak, amely legalább egy L

i -ben benne van. Jelölje K és Z a kezdő- illetve záró betűk halmazát Ezek után a keresett M=(A, a 0 , X, δ) véges automatát a következőképpen definiáljuk. • Az a 0 kezdő állapot legyen tetszőleges szimbólum. • Bármely i(=1, 2,, n) esetén a δ(a 0 , xi)=ai 1 állapot legyen a K-beli indexezett xi betűk halmaza. Ilyen módon definiáltuk már az M automata a 0 , a1 1 , a2 1 ,,an 1 állapotait, mint valamilyen szimbólumot, illetve mint az indexezett betűk halmazának bizonyos részhalmazait. Az M automata többi állapotát ezekből kiindulva indukcióval definiáljuk a következő módon. Ha már egy a∈A állapot definiálva van, akkor a δ(a, xi)=axi állapot legyen azoknak az indexezett xi betűknek a halmaza, melyeket megelőz legalább egy a-beli indexezett betű. A konstrukcióból világos, hogy az így definiált M automata iniciálisan összefüggő és véges, hiszen a 0 -tól különböző állapotai az indexezett betűk halmazának bizonyos

részhalmazai, és így állapotainak száma legfeljebb 2m+1, ahol m a fenti indexelés során felhasznált legnagyobb természetes szám. 34 Tetszőleges i(=1, 2,, k) esetén legyen A” i (⊆A) azoknak az állapotoknak a halmaza, amelyek legalább egy L i beli záró betűt tartalmaznak. Könnyű belátni, hogy az L i nyelv előállítható az M automatában azzal az A’ i halmazzal, amelyre  " " A i ∪ a 0 , ha λ ∈ L i ; A = " i A , ha λ ∉ L i .  i teljesül. { } 12.5 Kleene tétele A véges automaták analízise és szintézise során említett két tétel egybefoglalásával megfogalmazható a következő tétel: 12.5 Tétel (Kleene): A véges automatákban előállítható nyelvek egybeesnek a reguláris nyelvekkel 35 13. Veremautomata A veremautomatákat a programozási nyelvek elemzésére (környezetfüggetlen nyelvek szintaktikai elemzése), fordítására és formális nyelvek felismerőiként használják. A veremautomata

speciális szerkezetű végtelen automata (push-down automaton), amelynél egy potenciálisan végtelen befogadóképességű veremmemória összes lehetséges tartalma képviseli a végtelen sok lehetséges állapotot. A veremautomata tehát egy olyan véges automata, amelynek a vezérlőművét egy veremmemóriával láttuk el. A veremmemória ugyanúgy mezőkre van felosztva, mint a bemenőszalag, és itt is minden mezőbe egy-egy jelet írunk A veremszerű tárolási mód azt jelenti, hogy az adatok törlése a bevitelükhöz képest fordított sorrendben történik. Másrészt a veremmemória belsejének tartalmához közvetlenül nem férünk hozzá, mindig csak a verem tetején lévő adatot tudjuk kiolvasni, illetve módosítani (felülírni vagy törölni), és csak a verem tetejére helyezhetünk új elemet. Egy ilyen veremmemóriát könnyen megvalósíthatunk egy előre-hátra mozgó mágnesszalaggal, amelynél az írás mindig előremenetben, az olvasás pedig

hátramenetben történik. A hátramenet ugyanakkor mindig törléssel jár Egy veremautomatán az M=(A, X, Z, δ, a 0 , z 0 , A F ), hetest értjük, ahol • A: belső állapotok nem üres, véges halmaza; • X: a bemenő jelek véges halmaza, a bemenő ábécé; • Z: egy véges ábécé, a veremábécé; • δ: A×(X∪{λ})×ZA×Z* átmenetfüggvény; • a 0 ∈A, iniciális vagy kezdőállapot; • z 0 ∈Z kezdőjel a veremmemóriában; • A F ⊆A, a végállapotok halmaza. Definíció: Egy veremautomata pillanatnyi konfigurációja alatt olyan <a, x, z> rendezett hármasokat értünk, amelyekben a∈A, x∈X*, z∈Z. Működése: A nemdeterminisztikus veremautomata diszkrét lépésekben dolgozik. A vezérlőmű egy-egy lépésben az alábbi lehetőségek közül választhat egyet: • A vezérlőmű leolvassa a veremmemória legfelső elemét, valamint bemenő szó soron következő betűjét, és ezektől, valamint saját belső állapotától függően véges sok

lehetőség közül dönt arról, hogy mi legyen a következő belső állapota, illetve, hogy milyen szót írjon – ez esetleg lehet üres szó is – a veremmemóriába, a beolvasott legfelső jel helyébe. Ezután a vezérlőmű felkészül a következő bemenő jel leolvasására • A belső állapotától és a veremmemória legfölső jelétől függően a vezérlőmű véges sok lehetőség közül dönt a saját következő belső állapotáról, valamint a veremmemóriából beolvasott jel helyébe írandó szóról. Eközben a vezérlőmű nem olvas bemenő jelet, és nem is lép tovább a bemenő szalagon. Az ilyen lépéseket az automata a bemenő szó utolsó betűjének leolvasása után is megteheti. Ugyanez precízebb megfogalmazásban: Egy nemdeterminisztikus veremautomata minden lépésben a pillanatnyi konfigurációból a δ leképezés értelmében egy vagy több újabb konfigurációba mehet át. Az átmenet a következőképpen történik Legyen az adott

konfiguráció <a, x, z> (a∈A, x∈X*, z∈Z) és x=x 1 y, (x 1 ∈X, y∈X) és z= uz 1 (z 1 ∈Z, u∈Z*). Legyen δ leképezés értéke a (a, x 1 , z 1 ) argumentumra a következő: ahol p i ∈A, w i ∈Z* (1≤i≤m). δ(a, x 1 , z 1 )={(p 1 , w 1 ), (p 2 , w 2 ),(p m , w m )}, Ekkor a veremautomata ebben a lépésben a <a, x, z> konfigurációból átmegy a <p i , y, uw i > (1≤i≤m) konfigurációkba, és ugyanakkor a bemenő szalag egy mezővel előbbre ugrik. Amennyiben az a és z 1 mellett a δ(a, λ, z 1 ) nem üres, tehát δ(a, λ, z 1 )={(r 1 , s 1 ), (r 2 , s 2 ),(r n , s n )}, ahol r j ∈A, s i ∈Z* (1≤j≤n), 36 akkor a veremautomata egy <a, x, z> konfigurációból úgy megy át <r j , x, us j > (1≤j≤n) konfigurációkba, hogy közben a bemenő szalag helyben marad. Az ilyen lépéseket λ lépéseknek nevezzük, s ezek lehetővé teszik, hogy a veremautomata az aktuális bemenő jeltől függetlenül, mintegy autonóm

üzemmódban megváltoztassa a konfigurációját. Ilyenkor az aktuális bemenőjel leolvasása elmarad és csak a legközelebbi nem λ-lépésben fog megtörténni Előfordulhat természetesen, hogy valamely (a, x 1 , z 1 ) argumentumra sem a δ(a, x 1 , z 1 ) sem a δ(a, λ, z 1 ) nem üres, ami nincs ellentétben a nemdeterminisztikus működéssel. Definíció: Egy M veremautomata által elfogadott nyelv a következő: L(M)={p∈X* | a 0 z 0 p ⇒ aW, valamely W∈Z és a∈A F -re}. Megjegyzés: a nemdeterminisztikus működés értelmében ez azt jelenti, hogy legalább egy olyan átalakítás van, amely egy végállapottal végződik, de amellett lehet akárhány olyan átalakítás, amely nem végállapothoz vezet. A p szó elfogadása szempontjából W, a verem végső tartalma közömbös. Definíció: Egy M veremautomata által üres veremmel elfogadott nyelv a következő: N(M)={p∈X* | a 0 z 0 p ⇒ a, valamely a∈A-ra}. Megjegyzés: Itt tehát azt követeljük meg, hogy

legyen egy olyan átalakítás, amelynél a p szó beolvasása után a verem kiürül, s most az a állapot hovatartozása közömbös. Ha a verem kiürül, akkor az automata nyilván elakad, mivel az M leképezés üres veremnél nincs értelmezve. Példa: M=({a 0 , a 1 , a 2 }, {a, b}, {z 0 , z 1 }, δ, a 0 , z 0 , {a 0 }), ahol az átmenetfüggvény: δ(a 0 , a, z 0 ) ={<a 1 , z 0 z 1 >}, δ(a 1 , a, z 1 ) ={<a 1 , z 1 z 1 >}, δ(a 1 , b, z 1 ) ={<a 2 , λ>}, δ(a 2 , b, z 1 ) ={<a 2 , λ>}, δ(a 2 , λ, z 0 ) ={<a 0 , λ>}. Nézzük meg, hogy hogyan működik az M veremautomata az aabb és az abaab bemeneti szavak hatására. A következőket kapjuk: <a 0 , aabb, z 0 > ⇒ <a 1 , abb, z 0 z 1 > ⇒ <a 1 , bb, z 0 z 1 z 1 > ⇒ <a 2 , b, z 0 z 1 > ⇒ <a 2 , λ, z 0 > ⇒ <a 0 , λ, λ>; <a 0 , abaab, z 0 > ⇒ <a 1 , baab, z 0 z 1 > ⇒ <a 2 , aab, z 0 >. Tétel: Bármely M veremautomatához

megadható olyan M’ veremautomata, amelyre L(M’)=N(M). Tétel: Bármely M veremautomatához megadható olyan M’ veremautomata, amelyre N(M’)=L(M). Tétel: Bármely környezetfüggetlen G grammatikához megadható olyan M veremautomata, amelyre L(M)=L(G). Tétel: Bármely M veremautomatához megadható olyan G környezetfüggetlen grammatika, amelyre L(G)=L(M). A veremautomaták esetében a determinisztikus változat nem egyenértékű a nemdeterminisztikus változattal, azaz a determinisztikus veremautomatákkal felismert nyelvek osztálya a 2-es típusú nyelvosztály valódi részét képezik. 13.1 Kettős veremautomata A veremautomata általánosításaként olyan automatákat is definiálhatunk, amelyek egynél több veremmemóriával rendelkeznek. Tekintsük azt az esetet, amikor két ilyen veremmemóriánk van, és nincs külön bemenő szalagunk, hanem a beolvasandó szót az egyik veremmemóriában helyezzük el. Indításkor emellett feltételezzük, hogy a másik

verem üres, pontosabban csak a z 0 kezdőjel van az alján. 37 Egy nemdeterminisztikus kettős veremautomatán az M=(A, Z, δ, a 0 , z 0 , A F ), hatost értjük, ahol • A: belső állapotok nem üres, véges halmaza; • Z: egy véges ábécé, a veremábécé; • δ: Z×A×ZA×(Z-{z 0 })×{R, L, N, E, I} átmenetfüggvény; • a 0 ∈A, iniciális vagy kezdőállapot; • z 0 ∈Z kezdőjel a veremmemóriában; • A F ⊆A, a végállapotok halmaza. Definíció: Egy kettős veremautomata pillanatnyi konfigurációján értjük azt a WaP szót, melyre W∈Z* a második verem pillanatnyi tartalma, a∈A, P∈Z* pedig az első verem pillanatnyi tartalma. A P és W szavak elhelyezése a veremben ellentett, ugyanis az első veremben a P legelső betűje, míg a második veremben a W utolsó betűje van legfelül. A két verem tetején levő jelektől, valamint a vezérlőmű pillanatnyi állapotától függően az automata az alábbi lehetőségek közül választ egyet: •

vagy az első verem hosszát egyel csökkenti és a másodikét egyel növeli (R: jobbra lépés), • vagy az második verem hosszát egyel csökkenti, az elsőét egyel növeli (L: balra lépés), • vagy mindkét verem hosszát változatlanul hagyja (N: nincs mozgás), • vagy az első verem hossza változatlan marad, míg a másodiké eggyel csökken (E: törlés), • vagy az első verem hosszát eggyel növeli, a másodikét pedig változatlanul hagyja (I: beszúrás). Emellett minden esetben egy új jelet ír az egyik verem tetejére, és a vezérlőmű egy új állapotba megy át. Tétel: Bármely mondatszerkezetű G grammatikához van olyan M kettős veremautomata, amelyre L(M)=L(G). Tétel: Bármely M kettős L(G)=N(M). veremautomatához megadható olyan G mondatszerkezetű grammatika, amelyre Tétel: Bármely M kettős veremautomatához megadható olyan M’ kettős veremautomata, amelyre N(M’)=L(M). Tétel: A kettős veremautomaták által elfogadott nyelvek osztálya

megegyezik a 0-ás típusú nyelvek osztályával. Tétel: A kettős veremautomatáknál a determinisztikus és nemdeterminisztikus változat az elfogadott nyelvosztály szempontjából egyenértékű. 38 14. Lineárisan korlátolt automata Egy lineárisan korlátolt automatán az M=(A, X, δ, a 0 , K), ötöst értjük, ahol • A: belső állapotok nem üres, véges halmaza; • X: a bemenő jelek véges halmaza, a bemenő ábécé; • δ: A×XA×X×{R, L, N} átmenetfüggvény, és tetszőleges a∈A, x∈X-re teljesülnek az alábbi feltételek: I. (b, y, S)∈δ(a, K) ⇒ y=K (b∈A, y∈X, S∈{R, L, N}), II. (b, K, S)∈δ(a, x) ⇒ x=K (b∈A, S∈{R, L, N}); • a 0 ∈A, iniciális vagy kezdőállapot; • K∈X korlátozó jel. Működése: Úgy tekintjük, hogy M-hez hozzá tartozik egy bemenő szalag, amely rekeszekre van beosztva és az egyes rekeszekben a bemenő szó betűi vannak beírva folytatólagosan. Emellett feltételezzük, hogy a bemenő szó csak KpK

(p∈{X-K}*) alakú lehet, és hogy az automata működése kezdetén az író- olvasó fej a bemenő szalagon álló bemenő szót közrefogó két korlátozó jel közül a bal oldalira mutat. Ha működése valamelyik időpillanatában M olyan szituációba kerül, hogy M az a∈A állapotban van és az író olvasó fej a bemenő szalag olyan rekeszére mutat, amelyben az x∈X bemenő jel áll, akkor ebből a helyzetből M működése a következő lehetőségek valamelyike szerint folytatódhat: • Ha δ(a, x)=∅, akkor M nem működik tovább. • Ha (b, y, N)∈δ(a, x), akkor az író- olvasó fej helyben marad, kitörli a rekeszből az x jelet, helyébe az y jelet írja és M átmegy b állapotba. • Ha (b, y, L)∈δ(a, x), akkor az író- olvasó fej kitörli a rekeszből az x jelet, helyébe az y jelet írja, majd egy rekesznyi hellyel balra lép és egyidejűleg M átmegy b állapotba. • Ha (b, y, R)∈δ(a, x), akkor az író- olvasó fej kitörli a rekeszből az x

jelet, helyébe az y jelet írja, majd egy rekesznyi hellyel jobbra lép és egyidejűleg M átmegy b állapotba. Az író- olvasó fej tehát képes a bemenő szalag mentén mindkét irányba egy-egy rekesznyi hellyel elmozdulni vagy helyben maradni, továbbá bemenő jelet más bemenő jelre kicserélni. Az I, II feltételek szerint azonban a korlátozó jel csak a korlátozó jelre cserélhető ki, és csak a korlátozó jel cserélhető ki a korlátozó jelre. Lineárisan korlátolt automatának nevezzük az olyan kettős veremautomatát is, amelynél az átmenetfüggvény nem tartalmaz I-típusú, azaz beszúrási lépést. Tehát a két verem összhosszúsága az automata működése közben nem növekszik. 14.1 Tétel: Ha egy véges ábécé fölötti L nyelv előállítható egy lineárisan korlátolt automatában, akkor L környezetfüggő 14.2 Tétel: Minden környezetfüggő nyelv előállítható lineárisan korlátolt automatában A lineárisan korlátolt automaták által

elfogadott nyelvek osztálya megegyezik az 1-es típusú nyelvek osztályával. Mindmáig nyitott kérdés viszont az, hogy a determinisztikus lineárisan korlátolt automata egyenértékű-e a nemdeterminisztikus változattal. 39 15. Turing-gép A Turing-gép fogalmát Alan Turing vezette be bizonyos automatikusan végrehajtható számítások tanulmányozására 1936-ban, jóval az első programvezérlésű elektronikus számítógépek megjelenése előtt. Egy Turing-gépen az M=(A, a 0 , X, B, A F , µ), hatost értjük, ahol • A: belső állapotok nem üres, véges halmaza; • a 0 ∈A, iniciális vagy kezdőállapot; • X: egy véges ábécé, a szalagábécé; • B∈X a szóköz betű, vagy blank jel; • A F ⊆A, a végállapotok halmaza; • µ: (A-A F )×XA×X×{Jobb, Bal, Helyben} mozgásfüggvény. A Turing-gép minden egyes lépése a következő műveletek végrehajtásából áll: • beolvas egy új jelet a szalagról, • megváltoztatja a vezérlőmű

állapotát, • kiír egy új jelet a szalagra, • egy mezővel jobbra vagy balra lépteti az író-olvasó fejet, vagy helyben marad. Konfiguráció: Egy nemdeterminisztikus Turing-gép egy pillanatnyi konfigurációja W=PaQ alakú, ahol P, Q∈X*, a∈A és P∈X+ esetén P nem kezdődhet, Q∈X+ esetén pedig Q nem végződhet szóközzel. Az író/olvasó fej a Q szó első betűjén áll. Ha a=a 0 és P=λ akkor kezdő konfigurációról, ha pedig a∈A F , akkor végkonfigurációról beszélünk Sok esetben nem szokták elkülöníteni a Turing-gép végállapotait a többi állapottól. Ilyenkor végkonfiguráció alatt azokat a W=PaxQ, x∈X{B}, illetve W=Pa konfigurációkat szokás érteni, ahol µ(a, x)=∅, illetve µ(a, B)=∅. Számítási folyamat: A konfigurációk egymásba való átmeneteinek sorozata. Teljes számítási folyamat: Olyan számítási folyamat, mely a kezdőkonfigurációból indul, és egy befejező konfigurációval ér véget. Egyszerű végtelen

ciklus: Amennyiben valamely PaxQ (a∈AA F , x∈X), illetve Pa (a∈AA F ) pillanatnyi konfiguráció esetén µ(a, x)=(a, x, Helyben), illetve µ(a, B)=(a, B, Helyben), akkor azt mondjuk, hogy a Turing-gép a tekintett pillanatnyi konfigurációban egyszerű végtelen ciklusba esik. A Turing-gép tehát akkor áll le működésével, ha a vezérlőműnek nincs meghatározva a következő lépése, vagy végállapotba kerül. Az eddig vizsgált automatáktól eltérően a Turing-gépek egy-egy bemenet hatására akár végtelen hosszú ideig is dolgozhatnak. A fentiekben definiált Turing-gép a kettős veremautomatával egyenértékű. Képzeljük el ugyanis, hogy a Turinggép mindkét irányban végtelen szalagját középen – pontosabban az író-olvasó fej mellett – kettévágjuk, és a két félszalagnak blanket nem tartalmazó részeit a két veremmemóriába helyezzük el. Ily módon a Turing-gépet szimulálni lehet kettős veremautomatával, és viszont A lineárisan

korlátolt automatákat is általában Turing-gépekre alapozva szokták megadni. Eszerint a lineárisan korlátolt automata egy olyan Turing-gép, amely a szalagjáról csak annyi mezőt használ fel, amennyit a bemenő szó elfoglal. Ahhoz, hogy az automata érzékelni tudja a két szó végét, két speciális jelet, ún szóvégmarkereket szoktak elhelyezni a bemenő szó két végére. (A blank-et ugyanis mindig felül kell írni, ha beolvassuk) 15.1 Tétel: Bármely M Turing-géphez megadható olyan M’ kettős veremautomata, amelyre L(M’)=L(M) (A tétel fordítottja is igaz.) 40 Turing-gép időbonyolultsága: Egy Turing-gépet t(n) időbonyolultságúnak mondunk, ha minden legfeljebb nhosszúságú bemenő szóra legfeljebb t(n) lépést hajt végre. Turing-gép szalagbonyolultsága: l(n) szalagbonyolultságúnak mondunk egy Turing-gépet, ha minden legfeljebb n-hosszúságú bemenő szóra legfeljebb l(n) mezőt használ fel a szalagján. Vezessük be a többszalagos

Turing-gép fogalmát, mely az egyszalagos Turing-gép fogalmának közvetlen általánosításaként adódik. A k szalag mindegyikéhez tartozik egy író-olvasó fej, és minden egyes lépés a k db szalag mindegyikén párhuzamosan egy-egy olyan műveletnek a végrehajtását jelenti, mint amilyet az egyszalagos Turing-gépnél már láttunk 15.2 Tétel: Bármely k-szalagos Turing-gép szimulálható egyszalagos Turing-géppel A szalagok számának növekedése tehát nem bővíti a Turing-géppel megoldható feladatok körét. 15.3 Tétel: Bármely egyszalagos nemdeterminisztikus Turing-gép szimulálható egyszalagos determinisztikus Turing-géppel. Tehát a determinisztikus, illetve nemdeterminisztikus Turing-gépekkel ugyanazt a nyelvosztályt lehet felismerni. 15.4 Tétel: Bármely 0-típusú G grammatikához megadható olyan M Turing-gép, amelyre L(M)=L(G)-λ (A bizonyításhoz a 0-típusú grammatikát először Révész-féle normálalakra kell hozni) 15.1 A Turing-gép

által előállított parciális rekurzív függvény Legyen M tetszőleges Turin-gép, és tekintsük az alábbi egyenlőséggel meghatározott függvényt: *  f M ( P ) = QR, ha a 0 P ⇒ QaR, a ∈ A F ;  definiálatlan különben . Az ilyen függvényeket Turing-értelemben előállítható, függvényeknek, vagy Turing-gép által előállított parciális rekurzív függvényeknek nevezzük, s azt mondjuk, hogy az M Turing-gép az f M függvényt állítja elő. Ezen függvények segítségével a Turing-gépekre is úgy tekinthetünk, mint a formális nyelvek átalakítóira, melyek a szalagjukra írt bemeneti szót valamilyen kimeneti szóvá alakítják át a szalagon. Ha a részbenrekurzív függvény mindenütt értelmezett, akkor általánosan rekurzív, vagy egyszerűen rekurzív függvénynek nevezzük 15.2 Univerzális Turing-gép Olyan Turing-gép, amellyel bármely Turing-gép működését szimulálni lehet. Az U univerzális Turing-gép univerzalitása

alatt a következőket értjük Legyen adva egy tetszőleges M Turing-gép Amennyiben M átmenetfüggvényét és w startszavát megfelelő módon kódoljuk, akkor U erre a kódolt bemenetre pontosan akkor áll meg végállapotban, ha az M is megáll a w szóra, mint bemenetre. Az is igaz, hogy ha az U megáll, akkor szalagján a megállás pillanatában épp az M befejező konfiguráció van valamilyen formában kódolva. Univerzális utánzó gépek: - 4 állapot - 16 állapot - 106 állapot 7 bementeti jel 2 bemeneti jel 7 bemeneti jel Minsky Rozborov Zimmer 15.5 Tétel: Létezik univerzális algoritmus, mely izomorfizmustól eltekintve egyértelműen megadja bármely Turing-gép és annak startszava leírását Bizonyítás: A bizonyítás során alkalmazott meggondolást Gödel-számozásnak, a kódolt alakot pedig a Turing-gép Gödel számának hívjuk. Megjegyezzük, hogy léteznek ezen módszernél jóval hatékonyabb univerzális kódolási módszerek is. Ismeretes, hogy

minden természetes szám sorrendtől és asszociáltaktól eltekintve egyértelműen felírható prímhatvány tényezős alakban. Ezt a tényt fogjuk felhasználni Tekintsünk egy M= (A, a 0 , X, B, A F , µ) Turing-gépet, s legyen a 0 ,., a m-1 az állapotok egy olyan (kezdő állapottal kezdődő) felsorolása, ahol alkalmas 0≤k≤m-1 mellett {a 0 ,., a k }=AA F Jelölje továbbá x 1 ,, x n a szalagábécé betűinek egy felsorolását, s végül legyen 41 d 1 =(a 0 , x 1 ),., d k+1 =(a k , x 1 ), d k+2 =(a 0 , x 2 ),, d 2(k+1) =(a k , x 2 ),, d n(k+1) =(a k , x n ) Képezzük az M Turing-géphez és ezekhez az elrendezésekhez a u n(k+1) vn(k+1) w n(k+1) v w m k +1 n u1 gM = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 1 ⋅ 13 1 ⋅  ⋅ p n(k +1)+1 ⋅ p n(k +1)+ 2 ⋅ p n(k +1)+3 (tetszőleges rögzített számrendszerbeli, például tízes számrendszerbeli) természetes számot, ahol 2 hatványa az állapotok számát, 3 hatványa a nem-végállapotok számát, 5 hatványa a

szalagábécé betűinek számát jelöli, s minden további u v w p i +i1 , p i +i 2 , p i +i3 i=1,., n(k+1) prímhatvány-hármas esetén, ahol alkalmas a s ∈{a 0 ,, a k }(=AA F ), x t ∈{x 1 ,, x n } mellett d i =(a s , x t ) áll fenn, (u i , v i , w i )=(0, 0, 0), ha µ(a s , x t ) nincs értelmezve, ha pedig µ(a s , x t ) értelmezve van, akkor µ(a s , x t )=(a s’ , x t’ , Merre) esetén u i = s’+1, v i = t’, továbbá, mondjuk, w i = 1 ha Merre= Bal, w i = 2 ha Merre= Jobb, illetve w i = 3 ha Merre=Helyben. Az így meghatározott g M számot az M Turing-gép Gödel-számának fogjuk hívni Amennyiben a w startszó w=xi 1 .xi d alakú, a c(l(M), w) kódolt alak legyen (a rögzített számrendszerbeli) g M (p n(k+1)+4 )i 1 . (p n(k+1)+d )i d természetes szám. Látható, hogy a szóban forgó kódolás (izomorfizmustól eltekintve) egyértelmű, s ha a nyert c(l(M), w) természetes szám például tízes számrendszerben van megadva, akkor egy alkalmas tizenegy

bemenő jeles gépnek inputként megadható (tizenegyedik bemenő jel a szóköz jel). 15.3 Rekurzív és rekurzívan felsorolható nyelvek Rekurzív nyelvek: Egy L nyelvet (szóhalmazt) rekurzívnak nevezünk, ha a p∈L tartalmazási probléma algoritmikusan eldönthető. Rekurzívan felsorolható nyelvek: Egy L nyelvet rekurzívan felsorolhatónak nevezünk, ha van egy olyan (véges vagy végtelen) eljárás, mely az összes p∈L szót valamilyen sorrendben (esetleg ismétlésekkel) előállítja, azaz felsorolja. Minden rekurzív nyelv nyilván rekurzívan felsorolható. Nem kell ugyanis mást tennünk, mint rendre előállítani az összes P∈V T * szót, miközben minden egyes új szó előállítása után alkalmazzuk rá az eldöntési algoritmust, és belevesszük a felsorolásba, ha igen választ kapunk, egyébként elhagyjuk. Ezáltal megadtunk egy felsorolási eljárást, ahol még az ismétléseket is kizártuk Megfordítva viszont abból, hogy egy nyelv rekurzívan

felsorolható, még nem következik, hogy algoritmikusan eldönthető. 15.6 Tétel: Egy nyelv pontosan akkor rekurzív, ha mind L mind L komplementere rekurzívan felsorolható Azt már tudjuk, a rekurzív nyelvek osztálya magában foglalja az 1-típusú nyelvek osztályát. Azt is könnyű belátni, hogy minden 0-típusú nyelv rekurzívan felsorolható. Ehhez nem kell mást tenni, mint rendre előállítanunk az S-ből 1, 2 stb. lépésben levezethető összes jelsorozatot, s ezek közül kiválasztani a csak terminális jelekből állókat Eszerint kimondhatjuk az alábbi tételt 15.7 Tétel: Minden 1-típusú nyelv rekurzív, és minden 0-típusú nyelv rekurzívan felsorolható Belátható továbbá, hogy az 1-típusú nyelvek osztálya valódi része a rekurzív nyelvek osztályának. 15.8 Tétel: Van olyan rekurzív nyelv, amely nem 1-típusú Jelöljük a rekurzív nyelvek osztályát R-el, a rekurzívan felsorolható nyelvekét pedig F-el. Az eddigiek szerint azt tudjuk, hogy

L 1 ⊂R⊂F. Másrészt láttuk, hogy L 0 ⊆F, ahol viszont nem tudjuk, hogy a tartalmazási reláció milyen szigorú. Ha kiderülne, hogy L 0 =F, akkor rendben is volnánk, mert abból következnék egyrészt az, hogy L 1 valódi része L 0 -nak, másrészt pedig az, hogy az L 0 nyelvosztály bővebb a rekurzív nyelvek osztályánál is, vagyis hogy a tartalmazási probléma az L 0 nyelvosztályban algoritmikusan nem eldönthető. 15.9 Tétel: A rekurzív felsorolható nyelvek osztálya megegyezik a 0-típusú nyelvek osztályával (Tehát L 1 ⊂R⊂L 0 =F.) 42 15.4 A Churh-féle tézis A tézis olyan nem bizonyított állítás, melynek igazolása formális matematikai eszközökkel nem lehetséges. Church tézis (Alonzo Church, 1936): Az effektíve kiszámítható függvények osztálya megegyezik a parciális rekurzív függvények osztályával. Church-Turing tézis: Minden ami effektíve kiszámítható, kiszámítható Turing-géppel is. Matematikai értelemben ennek

csak a cáfolatát lehetne bizonyítani, ha megadnánk egy konkrét eljárást, amelyhez nem lehet a megfelelő Turing-gépet megkonstruálni. Ilyen ellenpéldát viszont még nem találtak Az eljárás formális definiálását célzó egyéb megközelítések, nevezetesen a rekurzív függvények, illetve a Markovféle normál algoritmus definíciói egyenértékűek a Turing-géppel. A fenti tézis azt mondja ki, hogy minden eljárás egyenértékű valamely Turing-géppel, azaz minden pontosan definiált eljáráshoz megadható egy Turing-gép, amely ezt az eljárás végrehajtja. 15.5 Eldönthetetlen problémák Akkor mondjuk, hogy egy Turing-gép valamely startszó hatására megáll, ha a startszó eleme a tekintett Turing-gép által felismert nyelvnek, azaz a startszóhoz tartozó kezdő konfigurációból kiindulva eljut egy végkonfigurációba. Azt mondjuk, hogy a Turing-gépek megállási problémája megoldható, ha létezik olyan A Turing-gép, mely egy M Turing-gép

leírását, és az M gép egy p input szavának kódolt alakját startszóként megkapva megáll, s megállva egyértelműen megállapítható, hogy p∈L(A), avagy sem. Ha ilyen A Turing-gép nem létezik, azt mondjuk, hogy a Turing-gépek megállási problémája megoldhatatlan. 15.10 Tétel (Turing-tétel): A Turing-gépek megállási problémája megoldhatatlan Bizonyítás (Minsky, 1961): A bizonyítás indirekt. Tegyük fel, hogy létezik olyan A Turing-gép, mely a c(l(M),w) szót startszóként megkapva (ahol l(M) az M gép leírása, w az M startszava, c(l(M), w) az M kódolt alakja) - megáll és ekkor az “igen” válasz kódolt alakja olvasható a szalagján, ha M megáll a w inputra, - megáll és ekkor a “nem” válasz kódolt alakja olvasható a szalagján, ha M nem áll meg a w inputra. Ha A létezik, megszerkeszthető az a B Turing-gép, mely az l(M) startszó hatására előállítja a c(l(M), l(M)) startszót, majd ezután ugyanúgy működik mint A, azzal a

különbséggel, hogy valahányszor az A igen megállást ér el, a B gép ugyanakkor egyszerű végtelen ciklusba esik. Mi történik akkor, ha B saját magát kapja meg bemenő szóként, azaz B a c(l(B)) startszót kapja? Előállítja a c(l(B), l(B)) startszót, és azt kapjuk, hogy B az l(B)-re pontosan akkor áll meg, ha B az l(B) startszó hatására nem áll meg. Ez nyilvánvalóan ellentmondás, amivel a tétel igazolást nyert Rekurzívan felsorolható nyelvek egy tulajdonságát triviálisnak nevezzük, ha vagy minden rekurzívan felsorolható nyelv rendelkezik ezzel a tulajdonsággal, vagy egyik sem. Nem triviális tulajdonság például, hogy az adott nyelv üres-e, véges-e stb. 15.11 Tétel (Rice): Legyen adva a rekurzívan felsorolható nyelvek valamilyen nem triviális tulajdonsága Ekkor annak eldöntése, hogy egy nyelv rendelkezik-e az adott tulajdonsággal algoritmikusan megoldhatatlan probléma. Következmény: Annak felismerése, hogy egy rekurzívan

felsorolható nyelv mikor • üres, • véges, • rekurzív, • reguláris, • környezetfüggetlen, • környezetfüggő stb., algoritmikusan eldönthetetlen probléma. 43 Ajánlott irodalom Révész György: Bevezetés a formális nyelvek elméletébe I-II., ELTE jegyzet, Tankönyvkiadó, Budapest, 1976 Peák István: Bevezetés az automaták elméletébe I. – Az automaták mint információátalakító rendszerek, ELTE jegyzet, Tankönyvkiadó, Budapest, 1977. Peák István: Bevezetés az automaták elméletébe II. – Az automaták mint felismerő rendszerek, ELTE jegyzet, Tankönyvkiadó, Budapest, 1978 Peák István: Bevezetés az automaták elméletébe III. – Automaták kompozíciói Struktúratételek, ELTE jegyzet, Tankönyvkiadó, Budapest, 1980. Gécseg Ferenc, Peák István: Az automaták algebrai elmélete, Matematikai lapok, 17 (1966), 77-134. Ádám A., Katona Gy, Bagyinszki J: Véges automaták, MTA Matematikai Kutató Intézete, Budapest, 1972

Trahtenbrot, B. A: Algoritmusok és absztrakt automaták, Műszaki könyvkiadó, Budapest, 1978 Demetrovics János, Jordan Denev, Radiszlav Pavlov: A számítástudomány matematikai alapjai, Tankönyvkiadó, Budapest, 1989. Varga László: Rendszerprogramozás, II. kötet, ELTE jegyzet, Budapest, 1975 Varga László: Rendszerprogramok elmélete és gyakorlata, Akadémia kiadó, Budapest, 1978. 44 Tartalomjegyzék 1. Formális nyelvek 1 1.1 Műveletek nyelvekkel 2 2. Formális rendszerek 3 2.1 Algoritmus 4 2.2 Nyelvtan 5 3. Chomsky-féle nyelvosztályok 6 4. Speciális nyelvtani alakok 8 4.1 Jobb-lineáris nyelvtan 8 4.2 Környeztfüggetlen nyelvtan 8 4.3 Környezetfüggő nyelvtan 10 4.31 Révész észrevételei a Kuroda-féle normálalakról 10 4.4 Mondatszerkezetű nyelvtan 11 5. Iterációs tételek és a Chomsky-hierarchia 13 6. Eldönthetőség, szintaktikai elemzés 16 6.1 CYK-algoritmus 16 6.2 Early-algoritmus 18 7. Automaták és néhány típusaik 21 7.1

Az átmenet- és kimenetfüggvények értelmezésének kiterjesztése 23 7.2 Automaták megadása táblázattal 23 7.3 Automaták megadása gráffal 23 8. Automaták által indukált leképezések 24 9. Automaták ekvivalenciája 26 10. Automaták algebrai elmélete 27 10.1 Redukált automata 29 10.2 Véges automaták minimalizációja 29 11. Véges automaták és nyelvek kapcsolata 30 12. Véges automaták analízise és szintézise 32 12.1 Reguláris nyelv, reguláris kifejezés 32 12.2 Nyelvek előállítása automatákban 33 12.3 Véges automaták analízise 33 12.4 Véges automaták szintézise 34 12.5 Kleene tétele 35 13. Veremautomata 36 13.1 Kettős veremautomata 37 14. Lineárisan korlátolt automata 39 15. Turing-gép 40 15.1 A Turing-gép által előállított parciális rekurzív függvény 41 15.2 Univerzális Turing-gép 41 15.3 Rekurzív és rekurzívan felsorolható nyelvek 42 15.4 A Churh-féle tézis 43 15.5 Eldönthetetlen problémák 43

Ajánlott irodalom . 44 45 Nyelvek és automaták 1 tételsor (1999) 1. Formális rendszer és főbb típusai. Helyettesítés, közvetlen levezetéses, levezetés Asszociatív kalkulus, szóprobléma, generatív rendszer, szemi-Thue rendszer Egy elmélet axiomatizálásának tipikus kérdései Markovféle algoritmus Alkalmazhatóság, elemi helyettesítés, levezetés Markov-féle normál algoritmus esetén A generatív nyelvtan, mint formális rendszer 2. A generatív nyelvtan és az általa generált nyelv fogalma. Chomsky hierarchia, üres szó lemma 3. Normális alakú nyelvtan, jobblineáris nyelvtan, jobbról reguláris nyelvtan. 4. Környezetfüggetlen nyelvtan, Chomsky-féle normálalak. 5. Környezetfüggő nyelvtan, Kuroda-féle normálalak. 6. Hosszúságot nem csökkentő nyelvtan. Révész észrevételei a Kuroda-féle normálalak egyszerűsíthetőségéről 7. Mondatszerkezetű nyelvtan, Révész-féle normálalak. 8. Levezetési fa, Bar-Hillel

lemma. 9. CYK-algoritmus. 10. Early-algoritmus, és az Early-tétel szükségessége 11. Early-algoritmus, és az Early-tétel elegendősége 12. Automaták és néhány típusaik (Mealy automata, Moore automata, kimenő jel nélküli automata, véges automata, iniciális automata, Rabin-Scott-féle felismerő automata, parciális automata, nemdeterminisztikus automata, sztochasztikus automata) Automaták megadása táblázattal és gráffal 13. Részautomata, izomorfizmus, homomorfizmus, kompatibilis osztályozás Minimális automata AufenkampHohn féle minimalizálási módszer 14. Automaták által indukált leképezések Raney tétele Alsó és felső automata 15. Automaták ekvivalenciája Gill tétele a Moore és Mealy-féle automaták ekvivalenciájáról 16. Véges automaták analízise McNaughton és Yamada algoritmusa 17. Véges automaták szintézise Gluskov algoritmusa 18. A 3-as típusú nyelvtan és a véges automaták kapcsolata Nemdeterminisztikus és

determinisztikus véges automaták által felismert nyelvosztály egybeesésének kimutatása 19. A 2-es típusú nyelvtan és a veremautomata A veremautomata működési elve és alkalmazása kifejezések kiértékelésénél Determinisztikus és nemdeterminisztikus automaták által felismert nyelvek 20. Az 1-es típusú nyelvtan és a lineárisan korlátolt automata A lineárisan korlátolt automata működési elve Determinisztikus és nemdeterminisztikus lineárisan korlátolt automaták által felismert nyelvosztályok (megoldatlan problémája). 21. A 0-ás típusú nyelvtan és a Turing-gép A Turing-gép működési elve A Turing-gép által megvalósított parciális rekurzív függvény 22. Univerzális (utánzó) Turing-gép létezése, Turing-gép szimulálása Turing-géppel A kódolás problémájának kérdése. 23. Megoldhatatlan probléma létezése: a Turing-gép megállási problémája 46