Programozás | Programozás-elmélet » Formális nyelvek kidolgozott tételek

A1. Generatív nyelvtan definíciója, levezetés, nyelvtan által generált nyelv fogalma Chomsky nyelvosztályok. DEF: Generatív nyelvtannak egy G=(N,Σ,P,S) rendezett négyest nevezünk, ahol: • N nemterminális ábécé • Σ terminális ábécé amire N∩Σ=∅ • S∈N a kezdőszimbólum • P pedig αβ alakú átjárási szabályok véges halmaza, ahol α,β∈(N∪Σ)* és α-ban van legalább egy nemterminális betű. DEF: Az (N∪Σ)* halmaz felett bevezetünk egy ⇒G-vel jelölt relációt, amit közvetlen derivációnak (levezetési relációnak) nevezünk: tetszőleges γ,δ∈(N∪Σ)*-ra akkor és csak akkor áll fenn γ⇒Gδ, ha van olyan α’,β’∈(N∪Σ)* szavak, amelyekre fennállnak, hogy γ=α’αβ’, δ=α’ββ’. DEF: A G=(N,Σ,P,S) nyelvtan által generált nyelv: L(G)={u∈Σ*|S⇒Gu}. DEF: (Chomsky nyelvosztályok) Azt mondjuk, hogy a G=(N,Σ,P,S) nyelvtan: • 0 típusú (kifejezés struktúrájú), ha rá semmilyen korlátozás nincs. •

1 típusú (környezetfüggõ), ha P-ben minden szabály αAβαδβ alakú, ahol δ≠λ. Kivétel lehet az Sλ szabály, ekkor azonban S nem szerepelhet semelyik szabály jobb oldalán. • 2 típusú (környezetfüggetlen), ha P-ben minden szabály Aα alakú. • 3 típusú (reguláris), ha P-ben minden szabály AxB vagy Ax alakú. A2. Véges automata fogalma, nemdeterminisztikus és determinisztikus automaták ekvivalenciája. DEF: Az M=(Q,Σ,δ,q0,F) rendszert nemdeterminisztikus automatának nevezzük, ahol: • Q egy nemüres véges halmaz, az állapotok halmaza • Σ az input ábécé • q0∈Q a kezdőállapot • F⊆Q a végállapotok halmaza • δ: Q×ΣP(Q) egy leképezés, az átmenetfüggvény. DEF: Azt mondjuk, hogy az M=(Q,Σ,δ,q0,F) automata determinisztikus, ha teljesül, hogy minden q∈Q és a∈Σ esetén a δ(q,a) halmaz legfeljebb egy elemű. TÉTEL: A nemdeterminisztikus automatákkal felismerhető nyelvek osztálya megegyezik a determinisztkus

automatákkal felismerhető nyelvek osztályával. BIZ: (a) Először is észrevesszük, hogy ha egy nyelv felismerhető determinisztikus automatával akkor felismerhető nemdeterminisztikus automatával is, hiszen a determinisztikus automata a nemdeterminisztikusnak speciális esete. (b) A másik irányú tartalmazás igazolásához legyen M=(Q,Σ,δ,q0,F) tetszőleges nemdeterminisztikus automata. Megadunk egy M’=(Q’,Σ,δ’,q’0,F’) determinisztikus automatát, amelyre L(M’)=L(M). Definiáljuk M’-őt a következőképpen: • Q’=P(Q) • q’0={q0} • F’= {S⊆Q|S∩F≠∅} • δ’: Q’×ΣQ’ az a leképezés amelyre tetszőleges S∈Q’ és a∈Σ esetén δ’(S,a)=∪q∈Sδ(q,a). Megmutatjuk, hogy L(M’)=L(M). Először vegyünkegy w∈L(M) szót Legyen w= a1a2ak, ahol ai∈Σ Mivel w∈L(M), vannak olyan q1,,qk∈Q állapotok, hogy q1∈δ(q0,a1),,qk∈δ(qk-1,ak) és qk∈F. Legyenek S0,,Sk∈Q’ azon állapotai M’-nek amelyekre teljesül

S0=q’0, S1=δ’(S0,a1),,Sk=δ’(Sk-1,ak). A δ’ átmenetfüggvény definíciója miatt az is igaz, hogy q1∈S1,,qk∈Sk. Mivel qk∈F, ezért Sk∩F≠∅, tehát Sk∈F’. Következésképpen w∈L(M’) A fordított irányú tartalmazás igazolásához vegyünk egy w∈L(M’) szót és újra tegyük fel, hogy w= a1a2ak. Mivel w∈L(M’) vannak olyan S0,,Sk∈Q’ állapotok, hogy S0=q’0, S1=δ’(S0,a1),,Sk=δ’(Sk-1,ak).és Sk∈F’ Ez utóbbi tartalmazás miatt Sk∩F≠∅, tehát van olyan pk∈Sk, amelyre pk∈F. Másrészt a δ’definícoja miatt vannak olyan p0,,pk-1∈Q állapotok, amelyekre p0∈S0,,pk-1∈Sk-1, és p1∈δ(p0,a1),,pk∈δ(pk-1,ak). Mivel S0={q0}, az is igaz, hogy p0=q0, következésképpen w∈L(M). A3. Reguláris kifejezés, általa meghatározott nyelv A reguláris nyelvek 3 típusúak DEF: Legyen Σ egy ábécé. A Σ feletti reguláris kifejezésekhalmaza a (Σ∪{∅,(,),+,*}) halmaz legszűkebb olyan U részhalmaza, amelyre az alábbi

feltételek teljesülnek: • az ∅ szimbólum eleme u-nak • Minden a∈Σ-ra az a szimbolum eleme U-nak • Ha R1,R2∈U, akkor (R1)+(R2), (R1)(R2), és (R1)* is elemei U-nak. DEF: Legyen R egy Σ feletti reguláris kifejezés. Az R által meghatározott |R| nyelvet a következőképen definiáljuk: • Ha R=∅ (mint szimbólum), akkor |R|=∅ (mint nyelv) • Ha R=a (mint szimbólum), akkor |R|={a} (mint nyelv) • Ha R=(R1)+(R2), akkor |R|=|R1|∪|R2| • Ha R=(R1)(R2), akkor |R|=|R1||R2| • Ha R=(R1)*, akkor |R|=|R1| // Továbbá, egy L⊆Σ* nyelvről azt mondjuk, hogy reguláris nyelv, ha reprezentálható reguláris kifejezéssel, vagyis, ha van olyan Σ feletti R reguláris kifejezés, melyre L=|R|. TÉTEL: Tetszőleges Σ ábécé esetén a következők egymással megegyeznek: • a Σ feletti 3 típusú nyelvek osztálya • a Σ feletti automatával felismerhető nyelvek osztálya • a Σ feletti reguláris nyelvek osztálya. LEMMA: Tetszőleges Σ ábécé esetén

minden Σ feletti L reguláris nyelv generálható 3 típusú nyelvtannal. BIZ: A bizonyítást az L-et reprezentáló reguláris kifejezés struktúrája szerinti indukcióval végezzük. (i) Legyen L=|R|, ahol R=∅. Ez esetben L=∅ generálható a G=({S},Σ,∅,S) nyelvtannal mivel egyetlen terminális szó sem vezethető le az S-ből. Továbbá G 3 típusú, mivel egyetlen szabálya sincs (ii) Legyen L=|R|, ahol R=|a|. Ekkor L={a} generálható a G=({S},Σ,{Sa},S) nyelvtannal ami nyilvánvalóan 3 típusú. (iii/a) Tegyük fel, hogy L=|R| ahol R=(R1)+(R2). Ekkor L=L1∪L2, ahol L1=|R1| és L2=|R2| Σ feletti reguláris nyelvek. Mivel R1 és R2 részkifejezései R-nek, az indukció feltevés értelmében L1 és L2 generálhatók a G1=(N1,Σ,P1,S1) és G2=(N2,Σ,P2,S2) 3 típusú nyelvtanokkal. Az általánosság megszorítása nélkül az is feltehető, hogy N1∩N2=∅. Megmutatjuk, hogy L is generálható 3 típusú nyelvtannal. Legyen G=(N1∪N2∪{S},Σ,P1∪P2∪{SS1,SS2},S),

ahol S egy új szimbólum Ekkor nyilvánvaló, hogy G is 3 típusú, és L(G)=L1∪L2. (iii/b) Tegyük fel, hogy L=|R| ahol R=(R1)(R2). Ekkor L=L1L2, ahol L1=|R1| és L2=|R2| Σ feletti reguláris nyelvek. Csakúgy mint az a) pontban, az indukció feltevés értelmében most is feltehető, hogy L1 és L2 generálhatók G1 és G2 3 típusú nyelvtanokkal. Legyen most G=(N1∪N2,Σ,P,S1), ahol P a legszűkebb olyan szabályhalmaz, amire teljesülnek a következő feltételek: • Ha AxB∈P1, akkor AxB∈P • Ha Ax∈P1, akkor AxS2∈P • P2 minden eleme P-nek is eleme. Megint csak nyilvánvaló, hogy G is 3 típusú, és L(G)=L1L2 (iii/c) Tegyük fel, hogy L=|R| ahol R=(R1)*. Ekkor L=L1*, ahol L1=|R1| egy Σ feletti reguláris nyelv. Az indukció feltevés értelmében L1 generálható az a) pontban szereplő G1 3 típusú nyelvtannal. Legyen G=(N1∪{S},Σ,P,S) az a nyelvtan, amelyben S egy uj nemterminális, P pedig a legszűkebb olyan szabályhalmaz, amire teljesülnek a

következő feltételek: • SS1, Sλ∈P • Ha AxB∈P1, akkor AxB∈P • Ha Ax∈P1, akkor AxS∈P. Nyilvánvaló, hogy G is 3 típusú, és könnyen igazolható, hogy L(G)=L1*. A4. A 3 típusú nyelvek automatával való felismerhetősége DEF:Tetszőleges G=(N,Σ,P,S) nyelvtan esetén az AB alakú szabályokat láncszabályoknak nevezzük.Amennyiben P-ben nincsenek lancszabályok,azt mondjuk,hogy G láncszabálymentes LEMMA:Legyen G=(N,Σ,P,S) környezetfüggetlen nyelvtan.Megadható olyan G’=(N,Σ,P’,S) láncszabálymentes környezetfüggetlen nyelvtan, amelyre L(G’)=L(G).Amennyiben G 3 típusú,úgy G’ is 3 típusú lesz. LEMMA:Legyen G=(N,Σ,P,S) 3 típusú láncszabálymentes nyelvtan.Akkor van olyan G’=(N’,Σ,P’,S) 3 típusú nyelvtan,hogy L(G’)=L(G). és P’ -ben minden szabály AaB vagy Aλ alakú , ahol A,B∈N és a∈Σ LEMMA: Tetszőleges Σ ábécé feletti 3 típusú nyelv felismerhető automatával. BIZ: Vegyünk egy Σ ábécé feletti 3 típusú

nyelvet. Akkor L=L(G), valamely G=(N,Σ,P,S) 3 típusú nyelvtanra A tétel igazolásához elegendő megadni egy olyan M=(Q,Σ,δ,q0,F) automatát amelyre L(M)=L(G). A korábbi lemmák értelmében feltehető, hogy G láncszabálymentes és, hogy minden P-beli szabály AaB vagy Aλ alakú. Konstruáljuk meg M-et a következőképpen: • Q=N • q0=S • F={A∈N|Aλ∈P} • minden A∈N és a∈Σ esetén δ(A,a)={B∈N|AaB∈P}. Annak igazolásához, hogy L(M)=L(G), elegendő megmutatnunk, hogy tetszőleges n≥1, A,B∈N és w∈Σ* esetén A⇒nwB akkor és csak akkor ha (A,w)|n(B,λ). Az ekvivalenciát n szerinti teljes indukcióval bizonyíthatjuk be. Ebből már következik, hogy L(M)=L=(G) Valóban, legyen w∈L(G). Akkor a G nyelvtanra tett megszorítások értelmében van olyan B∈N, hogy Bλ∈P és S⇒*wB⇒w. A fenti ekvivalencia miatt ekkor (S,w) |*(B,λ), másrészt az F definíciója miatt B∈F. Következésképpen w∈L(M) Megfordítva legyen w∈L(M). Akkor

(S,w) |*(B,λ) valamely B∈F-re. Mivel B∈F, az is igaz, hogy Bλ∈P. Másrészt az ekvivalencia miatt S⇒*wB, tehát S⇒wB⇒w és így w∈L(G). A5. Az automatával felismerhető nyelvek regulárisak (Kleene tétele) LEMMA: (Kleen tétel) Tetszőleges Σ ábécé feletti, automatával felismerhető nyelv reguláris. BIZ: Vegyünk egy M=(Q,Σ,δ,q0,F) automatát. Megmutatjuk, hogy L(M) reprezentálható reguláris kifejezéssel Korábban kimondot tétel értelmében feltehetjük, hogy M determinisztikus. Az is feltehető, hogy Q={1,,n} és, hogy q0=1. Tetszőleges 0≤k≤n és 1≤i,j≤n esetén legyen Li,j(k) azon x szavakból álló nyelv amelyekre ( i,x)|*(j,λ) de úgy, hogy i és j között az automata legfeljebb az {1,,k} halmazba eső állapotokat érinti. Formálisan: Li,j(0)={x∈Σ*|(i,x) )|(j,λ) és ha (i,x) |+(i,x) |+ (j,λ) akkor i’ ∈{1,,k}} Megjegyezzuk,hogy i,j∈{1,,k} is leghetséges Észrevesszük, hogy L(M)=∪j∈FL1,j(n). Ezért

amennyiben minden j∈F esetén az L1,j(n) nyelv rerezentálható reguláris kifejezéssel, úgy L(M) is. Elegendő tehát azt igazolni, hogy minden j∈F esetén az L1,j(n) regurális. Ennél azonban többet igazolunk: k szerinti indukcióval megmutatjuk, hogy minden 1≤i,j≤n-re az Li,j(k) nyelv reguláris. k=0 esetben: Li,j(0)= {a∈Σ| δ(i,a)=j}, ha i≠j {a∈Σ|δ(i,a)=j}∪{λ}, ha i=j Mindkét esetben Li,j(0) reguláris. (Korábbi észrevétel: minden véges nyelv reguláris) Tegyük fel, hogy minden 1≤i,j≤n esetén Li,j(k) reguláris. Bebizonyítjuk, hogy Li,j(k+1) is az Az i állapotból a j-be kétféleképpen juthatunk el úgy, hogy közben legfeljebbb az {1,,k+1} halmazba eső állapotokat érintjük. Egyrészt úgy, hogy legfeljebb az {1,,k} halmazba eső állapotokat érintjük, tehát k+1-et nem. Másrészt úgy, hogy k+1-et is érintjük Ez utóbbi esetben i-ből indulink, elérjük k+1-et, majd valahányszor visszatérünk oda. Miután legutoljára elhagytuk,

elérjük j-t Következésképpen Li,j(k+1) felírható a következöképpen: Li,j(k+1)= Li,j(k)∪ Li,k+1(k)( Lk+1,k+1(k))* Lk+1,j(k). Továbbá az indukció feltevés értelmében az Li,j(k), Li,k+1(k), Lk+1,k+1(k),és Lk+1,j(k) nyelvek mindegyike reguláris. Következésképpen Li,j(k+1) is reguláris, mivel reguláris nyelvekből állítottuk elő az egyesítés, a konkatenáció és iteráció segítségével. A6. Pumpáló lemma reguláris nyelvekre LEMMA: Legyen L⊆Σ* tetszőleges reguláris nyelv. Akkor megadható olyan (L-től függő) k>0 egész szám, hogy minden w∈L esetén, ha |w|≥k, akkor vannak olyan w1,w2,w3∈Σ* szavak, melyekre teljesülnek az alábbi feltételek: 1) w=w1w2w3 2) 0<|w2|≤k 3) minden n≥0, w1w2nw3∈L. BIZ: Mivel L reguláris, van olyan M=(Q,Σ,δ,q0,F) determinisztikus automata, melyre L=L(M). Legyen k=||Q|| Bebizonyitjuk, hogy ez a k megfelelő lesz. Vegyünk egy w∈L szótúgy, hogy |w|≥k vagyis, w=a1a2ak’, ahol k’≥k. Mivel

w∈L, vannak olyan q1,q2,,qk’∈Q állapotok melyekre: |(q2,a3.ak’) . . |(qk’-1,ak’) . . |(qk’,λ) , továbbá qk’∈F. Mivel k’≥k=||Q||, a skatulya-elv alapján a q0,,qk’ sorozatban van legalább két megegyező állapot, vagyis van olyan 0≤i,j≤k’ számpár, melyre i<j és qi=qj. Továbbá i és j választhatók úgy, hogy a qi+1,.,qj sorozatban már nincsenek megegyező elemek Legyenek w1=a1ai, w2=ai+1aj, és w3=aj+1ak’ Megmutatjuk, hogy w1,w2,w3 kielégíti mindhárom feltételt. 1) Az, hogy w=w1w2w3 nyilvánvaló. 2) Az, hogy |w2|≤k indirekt módon látható be. Ha ugyanis |w2|=j-i>k, akkor a qi+1,,qj sorozat legalább k hosszúságú lenne és akkor szerepelne benne legalább két megegyező állapot. 3) Megmutatjuk, hogy minden n≥0-ra w1w2nw3∈L. A w1, w2, w3 szavak definícióját felhasználva a fenti konfiguráció sorozat az alábbi módon írható fel: (q0,w1w2w3) |*(qi,w2w3) |(qi,w3) |(qk’,λ). Tehát az is

teljesül, hogy (qi,w2) |*(qi,λ) és ezért minden n≥0-ra (qi,w2n) |*(qi,λ). Következésképpen minden n≥0-ra (q0,w1w2nw3) |*(qi,w2nw3) |(qi,w3) |(qk’,λ), vagyis w1w2nw3∈L. A7. A reguláris nyelvek osztályának zártsági tulajdonságai (reguláris műveletek, Boole műveletek). TÉTEL: A reguláris nyelvek osztálya zárt a reguláris műveletekre nézve. BIZ: Azt kell igazolni, hogy ha L1,L2⊆Σ* reguláris nyelvek, akkor L1∪L2, L1L2 és L1 is azok. Akkor mondjuk, hogy egy L⊆Σ* nzelv reguláris, ha van olyan R, Σ feletti reguláris kifejezés, amely által reprezentált nyelv éppen L, vagyis melyre |R|=L teljesül. Legyenek tehát R1 és R2 olyan reguláris kifejezések, melyekre |R1|=L1 és |R2|=L2. A reguláris kifejezések definíciója szerint (R1)+(R2), (R1)(R2) és (R1)* is reguláris kifejezések.Továbbá a reguláris kifejezés által rerezentált nyelv definíciója értelmében |(R1)+(R2)|=L1∪L2, |(R1)(R2)|=L1L2 és

|(R1)*|=L1.Tehát az L1∪L2, L1L2 ésL1* nyelvek is reprezentálhatók reguláris kifejezéssel, ezért regulárisak. DEF: Legyenek M1=(Q1,Σ,δ1,q1,F1) és M2=(Q2,Σ,δ2,q2,F2) teljesen definiált és determinisztikus automaták .Definiáljuk az M=(Q1×Q2,Σ, δ,[q1,q2],F) automatát úgy hogy minden p1∈Q1 és p2∈Q2 állapot és a∈Σ input szimbólum esetén δ([p1,p2],a) = [δ(p1,a) , δ(p2,a) ]. Továbbá legyeen F a Q1×Q2 direkt szorzat egy tetszőleges részhalmaza . Akkor M-et az M1 és M2 direktszorzatának hívjuk. LEMMA: A reguláris nyelvek osztálya zárt a metszetre és a kivonásra. BIZ: Vegyünk két reguláris nyelvet: L1-et és L2-t. Tudjuk, hogy léteznek olyan M1=(Q1,Σ,δ1,q1,F1) és M2=(Q2,Σ,δ2,q2,F2) teljesen definiált és determinisztikus automaták, melyekre L1=L(M1) és L2=L(M2). Továbbá legyen M=(Q1×Q2,Σ,δ,[q1,q2],F) az M1 és M2 direkt szorzata, ahol F-et a következő módon választjuk meg: (a) Legyen F=F1×F2. Könnyű igazolni, hogy ekkor

L(M)=L(M1)∩L(M2) Tetszőleges x∈Σ* esetén: x∈L(M) ⇔ ∃[r1,r2]∈F1×F2 úgy, hogy ([q1,q2],x)|M*([r1,r2],λ) ⇔ ∃r1∈F1 és ∃r2∈F2 úgy, hogy (q1,x)|M1(r1,λ) és (q2,x)|M2*(r2,λ) ⇔ x∈L1 és x∈L2 ⇔ x∈L1∩L2. (b) Legyen F=F1×(Q2-F2) Az (a) esethez hasonló módon igazolható, hogy ekkor L(M)=L(M1)-L(M2). TÉTEL: A reguláris nyelvek osztálya zárt a Boole műveletekre nézve. BIZ: Fent bizonyítottuk, hogy a reguláris nyelvek osztálya zárt az egyesítésre. Ezután beláttuk, hogy zárt a metszésre. Ebből a lemmából következik, hogy zárt a komplementer képzésre is, mivel minden L⊆Σ* nyelvre igaz, hogy L=Σ*-L. A8. Környezetfüggetlen nyelvek levezetési módjai (általános, bal- és jobb oldali) és ezek kapcsolata. ALAPFOGALMAK: Az α0⇒α1⇒.⇒αn alakú kifejezéseket derivációknak vagy levezetéseknek hívjuk Amennyiben a fenti deriváció során minden i=1,.,n esetén αi-t úgy kapjuk, hogy αi-1-ben a bal (jobb)

oldalról nézve legelső nemterminálist helyettesítjük egy rá vonatkozó szabály jobb oldalával, akkor a derivációt bal (jobb) oldali derivációnak hívjuk, és rá az α0⇒lα1⇒l.⇒lαn (α0⇒rα1⇒r⇒rαn) jelölést használjuk. LEMMA: Tetszőleges X∈(N∪Σ) és w∈Σ* esetén a következő három állítás ekvivalens: • X⇒*w • X⇒l*w • X⇒r*w. BIZ: A bal és jobboldali levezetések között fennálló szimmetria miatt csak az első és a második állítás ekvivalenciáját bizonyítjuk be. Nyilvánvaló, hogy ha X⇒l*w akkor X⇒w is fennáll mivel a bal oldali levezetés a korlátozás nélküli levezetésnek speciális esete. Fordítva, tegyük fel, hogy X⇒*w. Akkor X⇒nw, valamilyen n≥0-ra Az n szerinti idukcióval bizonyítunk. n=0 esetén X=w ami csak úgy lehet, hogy X∈Σ. Ezért nyilvánvaló, hogy X⇒l*w (=X). Tegyük fel, hogy X⇒n+1w. Akkor ez a deriváció felírható X⇒X1.Xk⇒nw1wk=w alakban, ahol k≥1, XX1.Xk∈P és

minden 1≤i≤k-ra teljesül X⇒niwi, ni≤n Tehát az indiukció feltevés miatt Xi⇒lniwi is fennáll. Akkor viszont X ⇒l X1X2.Xk ⇒l w1X2.Xk ⇒l w1w2.Xk ⇒l w1w2.wk=w A9. Derivációs fa fogalma, levezetések és derivációs fák közötti kapcsolatok DEF: Legyen X∈(N∪Σ). Az X gyökerű derivációs fák halmazán fák legszűkebb olyan DX halmazát értjük, amelyre teljesülnek az alábbi feltételek: (i) Az a fa amelynek egyetlen szögpontja van és annak címkéje X, eleme DX-nek. (X-el jelöljük) (ii) Ha Xλ∈P, akkor az a fa , melynek gyökere X-szel van címkézve, a gyökerének egyetlen leszármazottja van aminek címmkéje λ, eleme DX-nek. (X[λ]-val jelöljük) (iii) Ha XX1.Xn∈P és t1∈DX1,,tn∈DXn, akkor az a fa, melynek gyökere X-szel van címkézve, a gyökérből n él indul rendre a t1,.,tn fák gyökeréhez, eleme DX-nek(X[t1 ,,tn]) Amennyiben X∈Σ ,úgy az (ii) és az (iii) feltételek soha nem teljesülnek,tehát ekkor DX={X}. DEF:Legyen

t egy X gyökerű derivációs fa.Akkot t magasságát h(t) -vel, t határát fr(t)-vel jelöljük,és az alábbi módon definiáljuk: (i) Ha t=X ,akkor h(t) = 0 és fr(t) = X (ii) Ha t=X[λ] akkor h(t)=1 ,és fr(t)= λ. (ii) Ha t= X[t1 ,.,tn] ,akkor h(t)= 1+ max{ h(ti) | 1≤ i ≤ n} és fr(t)=fr(t1) fr(tn) TÉTEL: Tetszőleges (N∪Σ) és α∈(N∪Σ)* esetén X⇒α akkor és csak akkor áll fenn, ha van olyan t∈DX derivációs fa amelyre fr(t)=α. BIZ: (a) Először azt igazoljuk, hogy ha X⇒*α, akkor akkor van olyan t∈DX derivációs fa amelyre fr(t)=α. A feltétel azt jelenti, hogy X⇒nα valamilyen n≥0-ra. Az állítást n szerinti indukcióval bizonyítjuk Az n=0 esetben X=α. Ezért az egyetlen szögpontú t=X fa megfelelő lesz, mert erre t∈DX és fr(t)=X (=α) Legyen most n≥0 és tegyük fel, hogy az állítás minden n-nél nem nagyobb számra teljesül. Tegyük fel továbbá hogy X⇒n+1α. Akkor X ⇒ X1.Xk ⇒ nα1αk = α, ahol teljesülnek a

következők: XX1.Xk egy P-beli szabály és minden 1≤i≤k esetén Xi⇒niαi, ahol ni≤n (n=n1+.+nk) Mivel ni≤n, az indukció feltevés miatt minden 1≤i≤k-ra van olyan ti∈DXi, hogy fr(ti)=αi. Legyen t=X[t1,.,tk]A derivációs fa, és határának definíciójából következik, hogy: t∈DX és fr(t)=fr(t1).fr(tk)=α1αk=α (b) Megfordítva, tegyük fel, hogy az X gyökerű t derivációs fára teljesül, hogy fr(t)=α. A t magassága szerinti indukcióval igazoljuk, hogy ekkor X⇒*α. Legyen h(t)=0. Akkor t=X, tehát fr(t)=α=X Következésképpen X⇒*α (=X). Most legyen h(t)=n+1, és tegyük fel, hogy az állítás minden n-nél nem magasabb derivációs fa esetén fennáll. Akkor t=X[t1,,tk], valamilyen k≥1 szám és t1∈DX1,,tk∈DXk derivációs fák esetén A fenti definíció miatt XX1.Xk∈P Vezessük be az αi=fr(ti) jelölést minden 1≤i≤k-ra Akkor egyrészt α=α1αk, másrészt az indukció feltevés miatt minden 1≤i≤k-ra Xi⇒*αi.

Következésképpen X⇒X1Xk⇒*α1.αk=α A10. Veremautomata fogalma, felismerés végállapottal és üres veremmel, ezek ekvivalenciája. DEF: Veremautomatának nevezzük a P=(Q,Σ,Γ,δ,q0,Z0,F) rendszert, ahol: • Q egy véges halmaz, az állapotok halmaza • Σ az input ábécé • Γ a verem ábécé • q0∈Q a kezdőállapot • Z0∈Γ a verem kezdősyimbólum • F⊆Q a végállapotok halmaza • δ: Q×(Σ∪{λ})×ΓPf(Q×Γ*) az átmenetfüggvény. DEF: A P által végállapotokkal felismert nyelven az Lf(P)={w∈Σ*|(q0,w,Z0)|(q,λ,γ), ahol q∈F és γ∈Γ} nyelvet értjük. DEF: A P által üres veremmel felismert nyelven az L∅(P)={w∈Σ*|(q0,w,Z0)|(q,λ,λ), ahol q∈Q} nyelvet értjük. TÉTEL: A veremautomatakkál végállapottal felismerhető nyelvek osztálya megegyezik a veremautomatával üres veremmel felismerhető nyelvek osztályával. BIZ: Először azt igazoljuk, hogy ha egy nyelv felismerhető egy P=(Q,Σ,Γ,δ,q0,Z0,F) veremautomata

végállapotaival, akkor megadhato olyan P’=(Q’,Σ,Γ ’,δ’,q0’,Z0’,F’) veremautomata amelyre L∅(P’)=Lf(P). Definiáljuk P’-t úgy hogy: • Q’=’∪{q0’,qe}, ahol q0’ és qe új állapotok • Γ’=Γ∪{Z0’}, ahol Z0’ egy új szimbólum • F’ tetszőleges részhalmaza Q’-nek • δ’ az alábbi módon definiált átmenetfüggvény: (1) δ’(q0’,λ,Z0’)={(q0,Z0Z0’)} (2) minden q∈Q, a∈(Σ∪{λ}), Z∈Γ esetén { δ(q,a,Z)∪{(qe,λ)} ha a=λ és q∈F δ’(q,a,Z)= { { δ(q,a,Z) ha a≠λ vagy q∉F. (3) minden Z∈Γ’-re δ’(qe,λ,Z)={(qe,λ)}. Az L∅(P’)=Lf(P).egyenlőség a következő számolásal igazolható: w∈Lf(P) ⇔ (q0,w,Z0) |P* (q,λ,γ) ahol q∈F (def. szerint) ⇔ (q0’,w,Z0’) |P’ (q0,w,Z0Z0’) ((1) miatt) |P’* (q,λ,γZ0’) ahol q∈F ((2) miatt) = (q,λ,Z1.ZkZ0’) (γ=Z1.Z2) |P’ (qe,λ,Z2.ZkZ0’) ((2) miatt) |P’* (qe,λ,λ) ((3) miatt) ⇔ w∈L∅(P’). (def. szerint) A

bizonyítás második részében azt kell igazolnunk, hogy ha egy nyelv felismerhető egy P=(Q,Σ,Γ,δ,q0,Z0,F) veremautomatával üres veremmel, akkor megadható olyan P’=(Q’,Σ,Γ’,δ’,q0’,Z0’,F’) veremautomata amelyre Lf(P)=L∅(P). Definiáljuk P’-t a következő módon: • Q’=Q∪{q0’,qf}, ahol q0’ és qf új állapotok • Γ’=Γ∪{Z0’}, ahol Z0’ egy új szimbólum • F’= {qf} • δ’ az alábbi módon definiált átmenet függvény: (1) δ’(q0’,λ,Z0’)={(q0,Z0Z0’)} (2) minden q∈Q, a∈(Σ∪{λ}), Z∈Γ esetén δ’(q,a,Z)=δ(q,a,Z) (3) minden q∈Q esetén, δ’(q,λ,Z0’)={(qf,λ)} Az Lf(P’)=L∅(P) egyenlőseg a következő számolással adódik: w∈L∅(P) ⇔ (q0,w,Z0) |P* (q,λ,λ) ahol q∈Q ⇔ (q0’,w,Z0’) |P’ (q0,w,Z0Z0’) |P’* (q,λ,Z0’) ahol q∈Q |P’ (qf,λ,λ) ⇔ w∈ Lf(P’) . (def. szerint) ((1) miatt) ((2) miatt) ((3 ) miatt) (def. szerint) A11. A környezetfüggetlen nyelvek

veremautomatákkal való felismerhetosége LEMMA: Tetszőleges környezetfüggetlen nyelv felismerhető veremautomatával. BIZ: Vegyünk egy tetszőleges G=(N,Σ,R,S) környezetfüggetlen nyelvtant. Legyen P=({q},Σ,Γ,δ,q,Z0,∅) az a veremautomata amelyben: • Γ=N∪Σ • Z0=S • δ átmenetfüggvény pedig a következő módon van definiálva: (1) minden A∈N-re δ(q, λ ,A)={(q,α)|Aα∈R} (2) minden a∈Σ-ra δ(q,a,a)={(q,λ)}. Megmutatjuk, hogy L∅(P)=L(G). Ehhez elegendő igazolni, hogy minden X∈(N∪Σ) és w∈Σ* esetén X⇒*w akkor és csakis akkor áll fenn, ha (q,w,X)|(q,λ,λ) ugyanis ez az X=S esetben éppen állításunkat igazolja. Először is tegyük fel, hogy X⇒nw valamilyen n≥0-ra. Teljes indukcióval haladunk tovább Ha n=0, akkor X=w∈Σ teljesül, ezért a (2) pont szerint (q,w,X)=(q,w,w)|(q,λ,λ). Ha X⇒n+1w, akkor ez a deriváció X⇒X1.Xk⇒nw1wk=w alakban írható. Tehát XX1Xk∈R és Xi⇒niwi minden 1≤i≤k-ra, ahol ni≤n

Akkor az (1) pont miatt (q,X1.Xk)∈δ(q,λ,X), másrészt az indukció feltevés miatt azt kapjuk, hogy minden 1≤i≤k esetén (q,wi,Xi)|*(q,λ,λ). Innen kapjuk, hogy (q,w,X) = (q,w1.wk,X) | (q,w1.wk,X1Xk) |* (q,w2.wk,X2Xk) . . . |*(q,wk,Xk) |* (q,λ,λ). Az is megfigyelhető, hogy a felismerés során P a w-nek egy bal oldali levezetését szimulálja. A fenti gondolatnenethez hasonlóan, a (q,w,X)|*(q,λ,λ) feltevésből kiindulva, az átmenetek során alkalmazott (1) típusú átmenetek száma szerinti indukcióval igazolhatjuk, hogy X⇒*w. A12. A veremautomatákkal felismerhető nyelvek környezetfüggetlenek LEMMA: Minden veremautomatával felismerhető nyel környezetfüggetlen. BIZ: Vegyünk egy tetszőleges P=(Q,Σ,Γ,δ,q0,Z0,F) veremautomatát. Megadunk hozzá egy olyan G=(N,Σ,R,S) környezetfüggetlen nyelvtant, amire teljesül L(G)=L∅(P). Definiáljuk G-t a következőképpen: • Legyen S egy új szimbólum • Legyen

N={S}∪{[qZr]|q,r∈Q,Z∈Γ} • legyen R szabályok legszűkebb olyan halmaza, amire teljesülnek a következő feltételek: (1) minden q∈Q-ra legyen S[q0Z0q] szabály R-ben (2) minden q∈Q, a∈(Σ∪{λ}), Z∈Γ-ra, ha (s0,Z1.Zk)∈δ(q,a,Z) (ahol k≥1, Z1,,Zk∈Γ) , akkor minden s1,.,sk∈Q sorozatra legyen [qZsk]a[s0Z1s1][sk-1Zksk] szabály R-ben, (3) minden q∈Q, a∈(Σ∪{λ}), Z∈Γ-ra, ha (s0,λ)∈δ(q,a,Z), akkor legyen [qZs0]a szabály Rben. Elegendő megmutatni, hogy minden q,r∈Q, Z∈Γ és w∈Σ* esetén (q,w,Z)|*(r,λ,λ) akkor és csak akkor áll fenn, ha [qZr]⇒w. (Ugyanis ezen ekvivalencia a q=q0 és Z=Z0 esetben éppen az L(G)=L∅(P) egyenlőséget jelenti.) Először tegyük fel, hogy [qZr]⇒n w valamilyen n≥1-re. Teljes indukciót alkalmazunk Az n=1 esetben, vagyis [qZr]⇒w esetben [qZr]w∈R. Ez az R szabályhalmaz definíciójának (3) pontja miatt csak úgy lehet, w=a∈(Σ∪{λ}) és (r,λ)∈δ(q,a,Z). Következésképpen

(q,w,Z)=(q,a,Z)|(r,λ,λ) Most tegyük fel, hogy [qZr]⇒n+1w, ahol n≥1. Akkor, figyelembe véve R definícióját, ez a deriváció az alábbi alakban írható: [qZr] ⇒ a[s0Z1s1].[sk-1Zksk]⇒naw1wk=w, ahol k≥1, [qZr]a[s0Z1s1].[sk-1Zksk]∈R, r=sk, minden 1≤i≤k-ra [si-1Zisi]⇒niwi, és ni≤n Akkor egyrészt (s0,Z1.Zk)∈δ(q,a,Z) másrészt, az indukció feltevés miatt minden 1≤i≤k-ra (si-1,wi,Zi)|*(si,λ,λ). Következésképpen (q,w,Z) = (q,aw1.wk,Z) | (s0,w1.wk,Z1Zk) |* (s1,w2.wk,Z2Zk) . . |* (sk-1,wk,Zk) |* (sk,λ,λ) = (r, λ,λ) . Az ekvivalencia megfordítását hasonló módon, a (q,w,Z)|n(r,λ,λ) feltételben szeteplő n szerinti indukcióval bizonyíthatjuk be. A13. Pumpáló lemma környezetfüggetlen nyelvekre (Bar-Hillel lemma) LEMMA: Legyen L⊆Σ* tetszőleges környezetfüggetlen nyelv. Akkor megadhatók olyan (L-től függő) p,q>0 egész számok, hogy minden w∈L esetén, ha |w|>p, akor vannak olyan w1,w2,w3,w4,w5∈Σ*

szavak, melyekre teljesülnek az alábbi feltételek: (1) w=w1w2w3w4w5 (2) |w2w3w4|≤q (3) w2w4≠λ (4) minden n≥0-ra, w1w2nw3w4nw5∈L. BIZ: Legyen L=L(G), ahol G=(N,Σ,P,S) egy környezetfüggetlen nyelvtan. Feltehetjük, hogy G láncszabály- és λ-mentes. Legyen n=||N|| és legyen k=max{|α||Aα∈P}. Definiáljuk a p és q számokat a következőképpen: p=kn és q=kn+1. Megmutatjuk, hogy ez a p és q megfelelő lesz. Vegyünk egy w∈L szót, melyre |w|>p. Akkor van olyan t∈DS derivációs fa, melyre fr(t)=w és h(t)>n Következésképpen t-ben van olyan, S-től valamely levélhez vezető út melynek hossza legalább n+1 és amelyen ezért legalább n+1 nemterminális szimbólum szerepel. Mivel N-ben összesen n darab nemterminális van ezért van olyan nemterminális is amely ezen az úton legalább kétszer előfordul. Tekintsük ezek közül azt a nemterminálist, amelyik ezen úton a terminális levéltől indulva a gyökér felé legelőször megismétlődik,

és jelöljük ezt A-val. Továbbá legyen t’’ a t-nek azon részfája, melynek gyökere A-nak a levéltől nézett első előfordulása és legyen t’ a t-nek azon részfája, melynek gyökere A-nak a második előfordulása.(Nyilvánvaló módon t’ , t’’∈DA és t’’ a t’ -nek is részfája) Legyenek w1,w2,w3,w4,w5∈Σ* szavak az alábbi feltételekkel meghatározva: • w3=fr(t’’) • w2 és w4 olyan, hogy fr(t’)=w2w3w4 • w1 és w5 olyan, hogy fr(t)=w1w2w3w4w5. Ekkor a lemmában szereplő valamennyi feltétel teljesül, mert: (1) mert: fr(t)=w (2) mert: a legelső olyan nemterminálist választottuk, amelyik ismétlődik és ezért h(t’)≤n+1 (3) mert: G láncszabály- és λ-mentes (4) mert: az a derivációs fa amelyet úgy kapunk, hogy t’-ből töröljük t’’-t a gyökere kivételével tetszőleges n-szer ismételhető úgy, hogy S gyökerű derivációs fát kapunk és a kapott derivációs fa határa w1w2nw3w4nw5 lesz. A14. A

környezetfüggetlen nyelvek osztályának zártsági tulajdonságai (reguláris műveletek, Boole műveletek). TÉTEL: A környezetfüggetlen nyelvek osztálya zárt a reguláris műveletekre nézve. BIZ: Azt kell igazolni, hogy ha L1,L2∈Σ* környezetfüggetlen nyelvek, akor L1∪L2, L1L2 és L1 is azok. Evégett legyenek G1=(N1,Σ,P1,S1) és G2=(N2,Σ,P2,S2) környezetfüggetlen nyelvtanok, melyekre L1=L(G1) és L2=L(G2). Az általánosság megszorítása nélkül feltehetjük, hogy N1∩N2=∅ Mindhárom müvelet esetén konstruálunk egy G környezetfüggetlen nyelvtant, amely rendre az L1∪L2, L1L2 és L1* nyelveket generálja. • Legyen G=(N1∪N2∪{S},Σ,P1∪P2∪{SS1,SS2},S), ahol S egy új szimbólum. Akkor L(G)=L1∪L2 • Legyen G=(N1∪N2∪{S},Σ,P1∪P2∪{SS1S2},S). Akkor L(G)=L1∪L2 • Legyen G=(N1∪{S},Σ,P1∪{SS1S,Sλ},S). Akkor L(G)=L1*. LEMMA: A környezetfüggetlen nyelvek osztálya nem zárt a metszetre. BIZ: Megadunk két olyan örnyezetfüggetlen

nyelvet, amelynek metszete nem környezetfüggetlen. Legyen L1={ambmcn|m,n≥0}. Akkor L1 környezetfüggetlen mivel generálható az alábbi környezetföggetlen nyelvtannal: SAB AaAb|λ BcB|λ. Hasonlóan látható be, hogy L2={ambncn|m,n≥0} is környezetföggetlen. Legyen L=L1∩L2={anbncn|m,n≥0}. Indirekt módon bebizonyítjuk, hogy L nem környezetfüggetlen. Tegyük fel, hogy L környezetfüggetlen Akkor a Bar-Hillel lemma szerint vannak olyan p,q>0 számok, hogy minden w∈L szóra, melynek hossza nagyobb mint p, teljesülnek az ezen lemmában szereplő feltételek. Vegyük a w=apbpcp szót ami nyilván L-ben van. Mivel |w|=3p, az is igaz, hogy |w|>p Akkor a pumpáló lemma szerint w felírható w=w1w2w3w4w5 alakban, ahol minden n ≥0-ra w1w2nw3w4nw5∈L. Vizsgáljuk meg hogyan helyezkedhetnek el a w2 és w4 részszavak a w-ben. Megállapíthatjuk, hogy sem w2, sem w4 nem tartalmazhat két különböző betűt, mert ekkor például a w1w2w2w3w4w4w5 szóban a betűk

sorrendje nem abc lenne. Tehát mind w2 mind w4 legfeljebb egy fajta betűt tartalmaz Ez viszont ellentmondáshoz vezet, mert ha így van, akkor n-et növelve a w1w2nw3w4nw5 szóban csak legfeljebb két fajta betűnek a száma növekszik, ami ellent mond annak, hogy w1w2nw3w4nw5∈L. LEMMA: A környezetfüggetlen nyelvek osztálya nem zárt a komplementer műveletre. BIZ: Legyenek L1,L2∈Σ* környezetfüggetlen nyelvek. A de Morgan azonosság szerint L1∩L2=L1∪L2(!!!Az egész jobb oldal fölött egy vonalnak kellene lennie!!!) Továbbá, a környezetfüggetlen nyelvek osztálya zárt az egyesítésre. Ezért, ha a komplementer képzésre zárt lenne, akkor zárt lenne az metszésre is, ami viszont ellentmondáshoz vezetne. B1. Szintaxis megadása környezetfüggetlen nyelvtannal, az elemzés alapfeladata A környezetfüggetlen nyelvtanok alkalmasak progamozási nyelvek szintaxisának a megadására. Egy PL programozási nyelv szintaxisát le lehet írni egy

GPL=(N,Σ,P,S) környezetfüggetlen nyelvtannal, ahol a PL nyeelvű programok Σ* azon elemei amelyek levezethetők S-ből a P-beli szabályok segítségével. Ismert jelöléseinket alkalmazva azt mondhatjuk, hogy a PL nyelvű programok éppen L(GPL) elemei. A gyakorlatban fontos feladat annak eldöntése, hogy egy, a felhasználó által megírt program megfelel-e a szintaktikai előírásoknak, hiszen csak ebben az esetben tudja a számítógép aztelfogadni és végrehajtani. Mi felel meg a felhasználó által írt programnak? Nem más, mint Σ* egy w eleme. Tehát annak eldöntése, hogy w megfelel-e PL szintexisának, vagyis, hogy szintaktikusan helyes-e, ekvivalens annak a kérdésnek a megválaszolásával, hogy w∈L(GPL) teljesül-e. Ez a w szó elemzésével válaszolható meg Az elemzés alapfeladata: Adjunk meg olyan algoritmust, amely tetszőleges G=(N,Σ,P,S) környezetfüggetlen nyelvtan és w∈Σ* szó esetén eldönti, hogy w∈L(G) teljesül-e! || Olyan

algoritmusokat keresünk tehát, amelyeknek inputként adható egy G nyelvtan és egy w∈Σ* szó, outputként pedig “igen” vagy “nem” választ adnak aszerint, hogy w∈L(G) vagy w∉L(G). Az ilyen algoritmusokat elemzési algoritmusoknak nevezzük. Az elemzési algoritmusok egyfajta csoprtosítása a következő lehet: • felülről-lefelé (top-down) algoritmusok. • alulról-felfelé (bottom-up) algoritmusok. B2. Az általános felülről lefelé haladó elemzési algoritmus ALGORITMUS: Felülről lefelé haladó általános elemzési algoritmus. Input: Egy nem balrekurzív G=(N,Σ,P,S) környezetfüggetlen nyelvtan és egy w=a1.an, n≥0 input szó Output: “Igen” jelzés és a w szónak egy baloldali levezetése, ha w∈L(G). Különben “nem” jelzés Módszer: • Minden A∈N esetében rögzítsük le A alternatíváinak egy sorrendjét Aγ1|γ2|.|γk alakban Az A iedik alternatívájára Ai-vel hivatkozunk • Az elemzés (s,i,α,β) alakú konfigurációk

sorozata, ahol: ♦s∈{q,t,b} az elemzés állapota. Értéke lehet q (normál), t (elfogadó) vagy b (backtrack) Kezdőértéke q. ♦i egy pointer melynek értéke 1≤i≤n+1, ahol n az input szó hossza. Ha 1≤i≤n, akkor i pointer aire mutat Ha i=n+1, akkor an+1=$, ahol $ egy olyan szimbólum ami nincs Σ-ban Az i kezdőértéke: 1. ♦ α egy verem, melynek teteje a jobb végén van. Tartalmazza az elemzés mindenkori történetét, hogy backtrack esetén tudjuk mely alternatívákat választottuk korábban és, hogy elfogadás esetén rendelkezésünkre álljon a bal oldali levezetés. Ezt a vermet passzív veremnek nevezzük Kezdőértéke: λ. ♦ β egy verem, mejnek teteje a bal végén van. Tartalmazza a levezetett bal oldali mondatformának azt a részét amelyet még ki kell terjeszteni. Ezt a vermet aktív veremnek nevezzük, a tetején lévő szimbólumot pedig aktív szimbólumnak, amit vagyx illeszteni kell (ha terminális), vagy kiterjeszteni (ha nemterminális).

Kezdőértéke: S • A konfigurációk halmazán megadunk egy | átmeneti relációt. Minden (s,i,α,β) konfigurációhoz legfeljebb egy (s’,i’,α’,β’) konfiguráció van, melyre (s,i,α,β)|(s’,i’,α’,β’). Ezen konfigurációt a következőképpen határozható meg: Az átmeneti relációt definiáló rész (1) pontjából indulva megkeressük az első olyan pontot, melyben szereplő feltétel teljesül (s,i,α,β)-ra. Ezen őpontban leírtaknak megfelelően számítjuk ki a rákövetkező (s’,i’,α’,β’) konfigurációt. • Kezdő konfiguráció: (q,1,λ,S). A befejező konfigurációk alakja: (t,n+1,α,λ), ahol α egy terminálisokból és alternatívákból álló sorozat. Az teljesül, hogy: w∈L(G) akkor és csakis akkor áll fenn, ha (q,1,λ,S).|*(t,n+1,α,λ). Az elemzési algoritmus: 1. C:= (q,1,λ,S); 2. Amíg van olyan C’, melyre C|C’, legyen C:=C’; 3. Ha C:=(t,n+1,α,λ) valamely α-ra, akkor az output: “igen”,

különben “nem” Amennyiben az output “igen”, α-ból törölve a terminális szimbólumokat, a megmaradó alternatíva sorozat wnek egy bal oldali levezetését adja. Átmeneti reláció: (1) Kiterjesztés: Ha a C=(q,i,α,Aβ), vagyis az aktív szimbólum nemterminális, akkor C|C’, ahol C’=(q,i,αA1,γ1β), és γ1 az A első alternatívája. (2) Sikeres input illesztés: Ha C=(q,i,α,aβ) és a=ai, vagyis az aktív szimbólum terminális és illeszkedik és illeszkedik az input pointer által mutatott input szimbólumhoz, akkor C|C’, ahol C’=(q,i+1,αa,β). (3) Sikeres elemzés: Ha C=(q,n+1,α,λ), akkor C|C’, ahol C’=(t,n+1,α,λ), vagyis elérjük a befejező konfigurációt. (4) Sikertelen input illesztés: Ha C=(q,i,α,aβ) de a≠ai, vagyis az aktív szimbólum terminális, de nem illeszkedik az input pointer által mutatott input szimbólumhoz, akkor C|C’, ahol C’=(b,i,α,aβ). (5) Backtrack az inputban: Ha C=(b,i,αa,β), akkor C|C’,

ahol C’=(b,i-1,α,aβ) (6) Ha C=(b,i,αAj+1,γj+1β) akkor az alábbi esetek lehetségesek: (i) Ha A-nak van j+1-edik alternatívája is, akkor C|C’, ahol C’=(q,i,αAj+1,γj+1β). (ii) Ha i=1, A=S és S-nek csak j alternatívája van, akkor nincs átmenet semelyik konfigurációba. (iii) Ha az előző feltételek egyike sem teljesül, akkor C|C’, ahol C’=(b,i,α,Aβ). DEF: Legyen k≥0 egy egész szám. Akkor: • tetszőleges α∈(N∪Σ)*-ra: FIk(α)={w|α⇒*wx∈Σ és |w|=k vagy (|w|<k és x=λ)} • tetszőleges L⊆(N∪Σ)*-ra FIk(L)=∪α∈LFIk(α) • tetszőleges u∈Σ*-ra {{u}, ha |u|<k FIk(u)= { {{w}, ha u=wx, ahol |w|=k. DEF: Legyenek L1 , L2 ⊆Σ* nyelvek ,és k≥0.Akkor L1 ⊕k L2 ={ FIk(xy) | x ∈ L1 ,y ∈ L2 } ALGORITMUS: FIk(A) halmazok kiszámítása. Input: Egy G környezetfüggetlen nyelvtan. Output: Minden A∈N-re FIk(A) halmaz. Módszer: FIk(A)-t iteráljuk a H0(A),H1(A),. sorozattal Algoritmus: (1) Legyen minden a∈Σ és i≥0

esetén Hi(a)={a}. (2) Legyen minden A∈N-re H0(A)={x∈Σ*|Axα∈P ahol (|x|=k) vagy (|x|<k és α=λ)} és legyen i=0. (3) Minden A∈N-re H0(A),.,Hi(A) már ismertek Legyen Hi+1(A)=Hi(A)∪{x∈Σ*|x∈Hi(X1) ⊕k .⊕kHi(Xn) valamely AX1.Xn esetén} (4) Ha minden A∈N-re Hi(A)= Hi+1(A), akkor álljunk meg, különben legyen i=i+1 és menjünk vissza (3)-ra. DEF: Legyen A∈N és k≥1. Akkor FOk(A)=∪{FIk(β)|S⇒*αAβ, valamilyen α,β∈(N∪Σ)-ra}. ALGORTMUS: A FOk(A) halmazok kiszámítása. Input: Egy G környezetfüggetlen nyelvtan és egy k≥1 egész szám. Output: Minden A∈N-re FOk(A). Módszer: FOk(A)-t iteráljuk a H0(A),H1(A),. sorozattal Algoritmus: (1) Legyen i=0, H0(S)={λ} és minden A≠S-re H0(A)=∅. (2) Mnden A∈N-re H0(A),.,Hi(A) már ismertek Legyen Hi+1(A)=Hi(A) ∪{x∈Σ*|x∈FIk(βHi(B)) valamely BαAβ szabály esetén}. (3) Ha minden A∈N-re Hi(A)= Hi+1(A), akkor álljunk meg, különben legyen i=i+1 és menjün (2)-re. Mivel minden

A∈N-re Hi(A) ⊆Σ*,k ,nyilvánvaló ,hogy az algoritmus véges sok lépés után vmely i-re megáll. B4. Az LL(k) és az erősen LL(k) nyelvek definíciója, és ekvivalanciájuk a k=1 esetben Az erősen LL(k) feltétel eldönthetősége. DEF: Legyen k≥1 egy egész szám. Azt mondjuk, hogy a G nyelvtan LL(k), ha valahányszor teljesülnek az • S⇒l*wAα⇒wβα⇒wx • S⇒l*wAα⇒wγα⇒wy • FIk(x)=FIk(y) feltételek, mindannyiszor β=γ. DEF: Legyen k≥1. Azt mondjuk, hogy G erősen LL(k), ha tetszőleges A∈N és Aβ, Aγ különböző szabályok esetén teljesül, hogy FIk(βFOk(A))∩FIk(γFOk(A))=∅, ahol βFOk(A)={βx|x∈FOk(A)}. TÉTEL: G akkor és csakis akkor erősen LL(1), ha LL(1). BIZ: Egy korábbi tételből tudjuk, hogy ha G erősen LL(1), akkor LL(1) is. A megfordítást indirekt módon bizonyítjuk, vagyis feltesszük, hogy G nyelvtan LL(1), de nem erősen LL(1). Ez esetben van két olyan különböző Aβ és Aγ szabály melyekre

FI1(βFO1(A))∩FI1(γFO1(A))=∅, vagyis van olyyan a∈(Σ∪{λ}), hogy a∈ FI1(βFO1(A))∩FI1(γFO1(A)). A következő esetek lehetségesek: (a) a∈Σ. ekkor az a∈ FI1(βFO1(A))∩FI1(γFO1(A)) tartalmazás négyféleképpen valósulhat meg, melyek mindegyike ellentmondáshoz fog vezetni. (a1) a∈FI1(β) és a∈FI1(γ). Ekkor léteznek az • S⇒l*wAα⇒wβα⇒wax’ • S⇒l*wAα⇒wγα⇒way’ levezetések, továbbá teljesül FI1(ax’)=FI1(ay’)=a. Ezért mivel G nyelvtan LL(1), β=γ-nak is teljesülnie kell, ami ellentmondás. (a2) β⇒*λ, a∈FO1(A) és a∈FI1(γ). Ekkor léteznek az • S⇒l*wAα⇒wβα⇒wα⇒wax’ • S⇒l*wAα⇒wγα⇒way’ levezetések, továbbá teljesül FI1(ax’)=FI1(ay’). Ezért mivel G nyelvtan LL(1), β=γnak is teljesülnie kell, ami ellentmondás (a3) γ⇒*λ, a∈FO1(A) és a∈FI1(β). Ennek az esetnek a bizonyítása az (a2)-höz hasonlóan történik (a4) β⇒*λ, a∈FO1(A) γ⇒λ. Ekkor léteznek az •

S⇒l*wAα⇒wβα⇒wα⇒wax’ • S⇒l*wAα⇒wγα⇒wα⇒wax’ levezetések, továbbá teljesül FI1(ax’)=FI1(ax’). Ezért mivel G nyelvtan LL(1), β=γ-nak is teljesülnie kell, ami ellentmondás. (b) a=λ.Ekkor a λ∈ FI1(βFO1(A))∩FI1(γFO1(A)) tartalmazás úgy valósulhat meg, hogy β⇒*λ, γ⇒λ, továbbá λ∈FO1(A). Ezért léteznek az (c) • S⇒l*wAα⇒wβα⇒wα⇒w • S⇒l*wAα⇒wγα⇒wα⇒w levezetések, továbbá w után λ áll és teljesül, hogy FI1(λ)=FI1(λ). Ezért mivel G nyelvtan LL(1), β=γ-nak is teljesülnie kell, ami megintcsak ellentmondás. ALGORITMUS: Az erősen LL(k) feltétel eldöntése. Input: Egy G környezetfüggetlen nyelvtan és k≥1 egész szám. Output: “Igen”, ha G erősen LL(k), különben “nem”. Algoritmus: (1) Válasszunk egy olyan A nemterminálist melynek legalább két alternatívája van. (2) Válasszunk két különböző Aβ és Aβγ szabályt és számoljuk ki a

(FIk(βFOk(A)))∩(FIk(γFOk(A))) halmazt. Amennyiben ez a metszet nem üres, akkor G nem lehet erősen LL(k), tehát áljjunk meg és adjunk az outputra “nem” jelzést. (3) Ha választható A-nak újabb két alternatíva-párja, akkor ismétejük (2)-t. (4) Ha választható újabb nemterminális, akkor ismétejük (1)-et. (5)Adjunk az outputra “igen” jelzést. B5. Az erősen LL(k) nyelvek elemzése: elemző tábla kosntukciója és az elemzési algoritmus. Az M elemző tábla a következőképpen konstruálható: M sorai az N∪Σ∪{$} halmaz elemeivel, oszlopai pedig a Σ*,k halmaz elemeivel vanna kcímkézve. Ha A∈N, akkor M-nek az A sorhoz és u∈Σ*,k oszlophoz tartozó M(A,u) eleme azt a tevékenységet írja le amit akkor kell végezni, ha az elemzés során A-t kell kiterjeszteni és u az előre nézett szó. Ha pedig a∈Σ, akkor M-nek az a sorhoz és az u∈Σ*,k oszlophoz tartozó M(A,u) eleme azt adja meg, hogy mit kell csinálni, ha az előre nézett szó u

és a-t kell illeszteni az elemzendő szóhoz. Ennek megfelelően M definíciója a következő: (1) Minde A∈N és u∈Σ*,k esetén, ha u∈FIk(βFOk(A)) és Aβ a j-edik szabály, akkor M(A,u)=(β,j) ,k (2) Minden a∈Σ és u∈Σ* esetén, ha u=av, akkor legyen M(a,u)=pop (3) Legyen M($,λ)=elfogadás (4) Minden más X∈(N∪Σ∪{$}) és u∈Σ*,k esetén legyen M(X,u)=hiba. ALGORITMUS: Erősen LL(k) elemzési algoritmus. Input: G nyelvtan (ami erősen LL(k)) M elemző táblája és z∈Σ* szó. Output: “Igen”, ha z∈L(G). Különben “nem” Módszer: • Sorszámozzuk meg G szabályait • Az elemzés (x,a$,π) alakú konfigurációk sorozata, ahol ♦ x∈Σ* egy szó, az elemzendő szó hátralevő része ♦ α∈(N∪Σ)* a levezetett bal mondatforma azon része, amely még további kiterjesztéseket és illesztéseket tartalmaz. Egy veremnek tekintjük, melynek teteje a bal végén van ♦ $ az elemzendő szó végét jelző szimbólum, $∉(N∪Σ). ♦ π

szabályok sorszámaiból alkotott sorozat. Egy sornak tekintjük, melynek eleje π jobb oldali végén van. • Kezdő konfiguráció: (z,S$,λ). A befejező konfigurációk (λ,$,π) alakúak A konfigurációk közötti átmenetet | -val jelöljük. Az átmeneti reláció úgy van definiálva, hogy z∈L(G) akkor és csakis akkor teljesül, ha (z,S$,λ)|*(λ,$,π). Az elemzési algoritmus: (1) C:=(z,S$,λ) (2) Amíg van olyan C’, melyre C|C’, legyen C:=C’ (3) Ha C=(λ,$,π) alakú, valamely π-re, akkor output: “igen”, különben “nem”. Amennyiben az output “igen”, π adja z egy bal oldali levezetését. Átmeneti reláció: Tegyük fel, hogy az (x,Xα,π) konfigurációban vagyunk, ahol Xα∈(N∪Σ)*$. Képezzük u=FIk(x)-et. (1) Ha X=A∈N és M(A,u)=(β,j), akkor (x,Xα,π)|(x,βα,πj). (a verem tetjén egy nemterminális állt amelyet kiterjesztettünk.Az alkalmazott szabály sorszámát outpuutra adjuk) (2) Ha X=a∈Σ és M(A,u)=pop, akkor

(x,Xα,π)|(x’,α,π), ahol x=ax’.(Az illesztendő terminális illeszkedik az elemzendő szóhoz.) (3) Ha M(X,u)=elfogadás (X=$, α=λ és u=λ egyidejűleg teljesülnek), akkor nincs átmenet. (4) Ha M(X,u)=hiba, akkor nincs átmenet. B6. Az általános alulról felfelé haladó elemzési algoritmus ALGORITMUS: Alulról felfelé haladó általános elemzési algoritmus. Input: Egy G=(N,Σ,P,S) ciklusmentes és λ-mentes környezetfüggetlen nyelvtan és egy w=a1.an∈Σ*, n≥1 szó. Output: “Igen” jelzés és a w szónak egy jobb oldali levezetése, ha w∈L(G). Különben “nem” jelzés Módszer:: • Rögzítsük le a szabályok egy sorrendjét. • Az elemzés (p,i,α,β) alakú konfigurációk sorozata, ahol ♦ p∈{q,b,t}, az elemzés állapota. Értéke q=normál, t=elfogadó vagy b=backtrack állapot Kezdő értéke: q. ♦ i az input szóba mutató pointer, melynek értéke 1≤i≤n+1, ahol n az input szó hossza. Kezdő értéke: 1. ♦ α egy verem,

melynek teteje jobb végén van. Tartalmazza az input szó elolvasott részéből redukálásokkal keletkezett (N∪Σ)*-beli szót. Kezdő értéke: λ ♦ β egy verem, melynek teteje a bal végén van. Tartalmazza az elemzés történetét, vagyis a végrehajtott shiftelések és redukálások sorozatát. Kezdő értéke: λ • A konfigurációk sorozatán megadunk egy | átmeneti relációt, amely egyértelműen megadja, hogy egy (p,i,α,β) konfigurációból mely (p’,i’,α’,β’) konfigurációba megyünk át. Ha egy konfigurációban vagyunk, akkor az átmeneti relációt definiáló rész (1) lépésétől elindulva az első olyan lépést alkalmazzuk, ami alkalmazható a konfigurációra. Ez a lépés határozza meg a következő konfigurációt • Kezdő konfiguráció: (q,1,λ,λ). A befejező konfigurációk alakja (t,n+1,S,γ) ahol γ egy s (shift) szimbólumból és szabályok sorszámaiból képzett sorozat. Az teljesül, hogy w∈L(G) akkor és csakis akkor,

ha (q,1,λ,λ)|*(t,n+1,S,γ). Az elemzési algoritmus: (0) Kezdő konfiguráció beállítása: C : =(q,1,λ,λ). (1) Redukálási kísérlet: Amíg redukálni lehet, vagyis C=(q,i,αγ,β)alakú és van olyan szabály ami Aγ alakú, addig C|C’, ahol C’=(q,i,αA,jβ) és ahol j az Aγ szabály sorszáma, és ez a legelső olyan szabály, amely szerint redukálás hajtható végre. Ha már nem lehet redukálni, akkor továbblépünk (2) Shiftelés: Ha C=(q,i,α,β) és i≠n+1, akkor C|C’, ahol C’=(q,i+1,αai,sβ), ahol ai az elemzendő szó iedik betűje. Menjünk (1)-re (mert ha lehet akkor redukáljuk) (3) Elfogadás: Ha C=(q,n+1,S,β), vagyis az inputot végigolvastuk, és az első veremben S van, akkor C|C’, ahol C’=(t,n+1,S,β). Az algoritmus álljon le és adjon “igen” jelzést az outputra. A második veremből törölve az s-eket a megmaradó szabály sorszámokból álló sorozat w-nek egy jobb oldali levezetését adja. (4) Átmenet backtrack

állapotba: Ha C=(q,n+1,α,β), de α≠S, akkor C|C’, ahol C’=(b,n+1,α,β). (5) Backtrack vérehajtása: (egymást kizáró esetek:) (i) Ha C=(b,i,αA,jβ), a j-edik szabály Aγ és az αγ redukálható egy további Bγ’ szabály szerint is, akkor C|C’, ahol C’=(q,i,α’B,kβ) és k>j a Bγ’ szabály sorszáma és a j-edik után ez a legelső olyan szabály, amely szerint αγ szón redukálás hajtható végre. Menjünk (1)re (ii) Ha C=(b,i,αA,jβ), a j-edik szabály Aγ és i≠n+1 de αγ nem redukálható más szabállyal, akkor a redukálást állítsuk vissza és shifteljünk, vagyis legyen C|C’, ahol C’=(q,i+1,αγai,sβ). Menjünk (1)-re (iii) Ha C=(b,n+1,αA,jβ), a j-edik szabály Aγ de αγ nem redukálható más szabállyal és már shiftelni sem tudunk, akkor a redukálást állítsuk vissza és maradjunk backtrack állapotban, vagyis legyen C|C’, ahol C’=(b,n+1,αγ,β). Menjünk (5)-re (iv) Ha C=(b,i,αa,sβ) és i>1,

akkor állítsuk vissza a shiftelést, vagyis legyen C|C’, ahol C’=(b,i-1,α,β). Menjünk (5)-re (v) Ha egyik feltétel sem teljesül, akkor w∉L(G), ezért az algoritmus álljon le, és adjon “nem” jelzést az outputra. B7. Az LR(k) nyelvtan definíciója és az LR(k) elemzéshez szükséges fogalmak bevezetése (nyél, járható prefix, LR(k) elem, érvényesség, LR(k) táblák és azok kiszámítása). DEF:Alulról felfelé elemzések esetében fontos fogalom a nyél , ami nem más , mint egy jobb mondatforma levezetésében a legutoljára alkalmazott szabály jobb oldala. DEF: Legyen k≥0 egész szám. Azt mondjuk, hogy a G nyelvtan LR(k), ha valahányszor teljesülnek az • S⇒r*αAw⇒rαβw • S⇒r*γBx⇒rγδx=αβy • FIk(w)=FIk(y) feltételek, mindannyiszor α=γ, A=B és β=δ. DEF: Legyen γ jobb mondatforma, γ≠S. Azt mondjuk, hogy β a γ nyele, ha van olyan Aβ szabály, melyre S⇒r*αAw⇒rαβw=γ. DEF: Azt mondjuk, hogy γ∈(N∪Σ)*

járható prefix,ha van olyan αβw jobb mondatformamelynek nyelve β és teljesül rá, hogy γ prefixe αβ-nak. DEF: Az [Aβ1.β2,u] alakú párokat LR(k) elemeknek nevezzük, ahol Aβ1β2∈P és u∈Σ*, k. DEF: Azt mondjuk, hogy az [Aβ1.β2,u] LR(k) elem érvényes az αβ1 járható prefixre, ha létezik S⇒r*αAw⇒αβ1β2w deriváció úgy, hogy u=FIk(w). LR(k) táblák: Adott γ járható prefix esetén a γ-ra érvényes LR(k) elemek halmazát Vk(γ)-val jelöljök. Minden γ-ra Vk(γ) véges halmaz. A Vk(γ)-kat LR(k) tábláknak hívjuk Egy Vk(γ) halmazban lévő járható prefixeket egymás alá írva táblázatszerű elrendezést kapunk. Bevezetjük a τ = {Vk(γ) | γ járható prefix} jelölést. ALGORITMUS: Vk(γ) meghatározása. Input: G nyelvtan és γ=X1.Xn szó ,ahol X1Xn ∈(N∪Σ) Output: Vk(γ) halmaz Módszer:: Kiszámoljuk a Vk(λ),Vk(X1), . , Vk(X1Xn) halmazokat Algoritmus:: (a) Vk(λ) kiszámítása (1) (Inicializálás.)Minden Sα ∈ P esetén

legyen [ Sα ] ∈ Vk(λ) (2) (Lezárás) Mindaddig , amíg Vk(λ) bővíthető , a Vk(λ) minden [A.Bβ,u] alakú elemére és Bδ P beli szabályra,legyen [Bδ,v] ∈ Vk(λ) minden v∈ Fi k(βu) -ra (b) Tegyük fel , hogy Vk(X1.Xi-1) -et már kiszámoltuk Ekkor kiszámítjuk a Vk(X1Xi) -t (1) (Léptetés) Minden [Aα . Xi β,u] alakú Vk(X1Xi-1) -beli elem esetén legyen [Aα . Xi β,u] ∈ Vk(X1Xi) (1) (2) (Lezárás) Mindaddig,amíg Vk(X1.Xi) bővíthető , a Vk(X1Xi) minden [Aα Bβ,u] alakú elemére, és Bδ P-beli szabályra ,legyen [B.δ,v] ∈ Vk(X1Xi) minden v∈ Fi k(βu) -ra B8. Az LR(k) feltétel átfogalmazása (LR(k) tétel), a tevékenység és a goto táblák definíciója. Az LR(k) elemzési algoritmus TÉTEL: G akkor és csakis akkor LR(k), ha minden T∈τ LR(k) táblára igaz, hogy ha T-ben van [Aβ.,u] alakú elem, akkor nincs benne egy olyan másik [Bβ1.β2,v] elem, melyre u∈EFFk(β2v) (Röviden: minden LR(k) tábla konzisztens.) Tevékenység tábla: az

f tevékenység tábla oszlopai Σ*,k elemeivel vannak címkézve. A T∈τ sorhoz és az u∈Σ*,k oszlophoz tarozó f(T,u) sor azt írja le, hogy mit kell tenni, ha a vizsgált járható prefixre LR(k) elemek halmaza T, az előrenézett szó pedig u. Goto tábla: A g goto tábla oszlopai N∪Σ elemeivel vannak címkézve. A T=Vk(γ) sor és az X oszlop által meghatározott elem Vk(γX), tehát g(T,X)=Vk(γX). ALGORITMUS: LR(k) elemzési algoritmus. Input: G (LR(k)) nyelvtan LR(k) elemző (tevékenység, goto) táblája és w∈Σ* szó. Output: “Igen”,ha w∈L(G), különben “nem”. Módszer: • Az elemzés (x,αT,π) alakú konfigurációk sorozata, ahol: ♦ x∈Σ* egy szó, az elemzendő szó hátralévő része. ♦ αT∈(τ∪N∪Σ)*, ahol α tartalmazza a járható prefixet úgy, hogy ennek minden prefixe után αban benne van a rá érvényes LR(k) tábla is. Egy veremnek tekintjük, melynek teteje a jobb végén van. ♦ π egy, a szabályok sorszámaiból

alkotott sorozat. Egy sornak tekintjük, melynek teteje a bal végén van. • Kezdő konfiguráció: (w,T0,λ), ahol T0=Vk(λ). A befejező konfigurációk (λ,T0αT,π) alakúak A konfigurációk közötti átmenetet | -val jelöljük. Az átmeneti reláció úgy van definiálva, hogy w∈L(G) akkor és csakis akkor teljesül, ha a kezdő konfigurációból elértünk egy olyan (λ,T0αT,π) konfigurációt, melyre f(T,λ)=elfogadás. Az elemzési algoritmus: (1) C:=(w,T0,λ) (2) Amíg van olyan C’, melyre C|C’, legyen C:=C’. (3) Ha C=(λ,T0αT,π) alakú, valamely π-re, és f(T,λ)=elfogadás, akkor output: “igen”, különben “nem”. Amennyiben az output “igen”, akkor 1π adja w egy jobb oldali levezetését, ahol 1 az egyetlen S bal oldalú szabály sorszáma. Átmeneti reláció: Tegyük fel, hogy az (x,αT,π) konfigurációban vagyunk. Képezzük u=FIk(x)-et (1) f(T,u)=(redukálás,j), akkor αT veremből törlünk 2|β| darab szimbólumot, ahol Aβ a

j-edik szabály. Tegyük fel, hogy a veremben marad γT’ Akkor (x,αT,π)|(x,γT’AT’’,jπ) ahol T’’=g(T’,A). (2) Ha f(T,u)=shift, akkor (x,αT,π)|(x’,αTaT’,π) ahol x=ax’ és T’=g(T,a) (3) Ha f(T,u)=elfogadás (csak úgy lehet ,ha T-ben van [Sα.,λ] alakú elem és u=λ egyidejűleg teljesülnek), akkor nincs átmenet. (4) Ha f(T,u)=hiba, akkor nincs átmenet. B9. Egyszerű precedencia nyelvtanok definíciója, eldönthetősége Egyszerű precedencia elemzési algoritmus. DEF: Egy G=(N,Σ,P,S) környezetfüggetlen nyelvtan egyszerű precedencia nyelvtan, ha rá a következők teljesülnek: • G ciklusmentes és λ-mentes • G egyértelműen redukálható • minden X,Y∈(N∪Σ)-ra a <,= és > relációk közül legfeljebb egy áll fenn X és Y között. KÖVETKEZMÉNY: Tetszőleges G környezetfüggetlen nyelvtanról eldönthető, hogy egyszerű precedencia nyelvtan-e. ALGORITMUS: Egyszerű precedencia elemzési algoritmus. Input: G

egyszerű precedencia nyelvtan, precedencia mátrix és w∈Σ* szó. Feltesszük továbbá, hogy G szabályai meg vannak számozva. Output: “Igen”, ha w∈L(G), különben “nem”. Módszer: • Az elemzés ($α,x$,π) alakú konfigurációk sorozata, ahol: ♦α∈(N∪Σ)*, az elemzendő szó már beolvasott részéből redukált járható prefix. Egy veremnek tekintjük, melynek teteje a jobb végén van. ♦ x∈Σ* egy szó, az elemzendő szó hátralévő része. ♦ teljesül továbbá, hogy αx⇒r*w ♦π szabályok sorszámaiból alkotott sorozat. Egy sornak tekintjük, melynek teteje a bal végén van. • Kezdő konfiguráció: ($,w$,λ). A befejező konfigurációk ($S,$,π) alakúak A konfigurációk közötti átmenetet |-val jelöljük. Az átmeneti reláció úgy van definiálva, hogy w∈L(G) akkor és csakis akkor teljesül, ha ($,w$,λ)|*($S,$,π) valamely π-re és ekkor π adja w egy jobb oldali levezetését. Az elemzési algoritmus: (1) C:=($,w$,λ)

(2) amíg van olyan C’, melyre C|C’, legyen C:=C’ (3) Ha C=($S,$,π) alakú, valamely π-re, akkor az output “igen”, különben “nem”. Amennyiben az output “igen”, akkor π adja w egy jobb oldali levezetését. Átmeneti reláció: Tegyük fel, hogy a C=($α,x$,π) konfigurációban vagyunk, ahol α∈(N∪Σ)* és x∈Σ. Legyen X a $α verem tetején lévő szimbólum (vagyis $α=α’X) és legyen a az x$ első betűje.(vagyis ax’ =x$) (1) Ha (precedencia mátrix szerint) X<a vagy X=a, akkor C|C’, ahol C’=($αa,x,π). (2) Ha (precedencia mátrix szerint) X>a, akkor keressük mega $a veremben fölülről lefelé az első olyan helyet, ahol két veremszimbólum között < áll fenn, vagyis legyen β a legrövidebb szó, melyre $α=α’β és α’ utolsó és β első betűje között < áll fenn. Ekkor: • ha β egy Aβ szabály jobb oldala, akkor redukáljunk, vagyis C|C’, ahol C’=(α’A,x$,jπ) • különben ,vagyis ha β

egyetlen szabálynak sem jobb oldala, akkor nincs átmenet. (3) Különben nincs átmenet