Eloszo
A T*DK 'sorozat' kovetkezo peldanya, ezuttal Formalis nyelvek es automatak targyhoz. Szerencsere itt ha a gyakot ertetted, akkor kb mindennek mennie is kell, de ahogy en eszrevettem, nehez egy osszeallo kepet kapni a tananyag egeszerol. Pedig egeszen osszefugg minden, es igy a vizsga is jelentosen egyszerubbe valik. Aztan mar csak par definiciot kell bevagni, otosert meg par bizonyitast. Forrasaim az orai jegyzetek, illetve az azota nyilvanossa tett vizsgak megoldasai.
/!\ Disclaimer /!\
Nagyon fontos, hogy az itt leirtak CSAK a megertest segitik. Sok helyen csak elmagyarazok dolgokat, es nem irom le formalisan, meg csak ugy megjegyzem, hogy "ja ennek ez a jele". Erosen ajanlom, hogy ha valaki nem tud formalizalni dolgokat, nem tudja a jeloleseket, akkor miutan megert itt egy temat, azonnal nezze meg hozza a formalizalast.
Tartalomjegyzek
Ha valami [WiP], akkor eppen dolgozok rajta.Ha valami [SOONish], akkor meg el sem kedztem.
Ha valami [nFIX], akkor reszemrol kesz, de nem erzem teljesnek.
Az ilyen fejezetekben a linkek nem mindig mukodnek.
Elozetes attekintes
Kicsit rendhagyo leszek, es nem az alapfogalmakkal kezdem. Helyette, mivel itt egyszeru fogalmak vannak, eloszor leirnam, hogy mi az a vegso nagy osszefuggo latkep amit meg akarunk szerezni. Aztan kezdjuk csak el boncolgatni, hogy mar tudjuk, miert csinaljuk.
Lenyegeben van negy fajta nyelvtipus, ehhez negy grammatika, es mindhez egyfajta eloallitasi modszer. A legjobb, hogy ahogy a tipusok sorszama novekszik, ugy tartalmazzak egymast (ez a Chomsky hierarchia), novekvo sorrendben. Szoval minden harmas tipus kettes is, de nem minden kettes harmas, minden kettes egyes, de nem minden egyes kettes, vagyis minden harmas egyes, de nem minden egyes harmas, etc. Ja igen, az elso tipus 0, es nem 1. Osszesen igy 3-ig megyunk fel. Az alapjan vannak besorolva, hogy milyen szabalyok alapjan allitjak elo az adott tipusu nyelv szavait. Errol majd kesobb. De ez alapjan is vannak kb elnevezve. A 3. tipus a regularis kifejezesek (regularis nyelvek). 2. a kornyezetfuggetlen, 1. a kornyezetfuggo, 0. pedig a 'nem besorolhato', illetve neha rekurzivan felsorolhato (enumeralhato) nyelvek.
A szabalyok amiket mondtam (amivel besoroljuk oket a heirarchiaba) az egyes nyelvtipusokhoz tartozo (azonos sorszamu) grammatikak (neha generativ grammatikak) szabalyai. Ezekkel lehet nyelveket csinalni. Szoval egy 1-es tipusu grammatika csinal 1-es tipusu nyelvet, vagyis egyben 2-es es 3-as tipusut is. Ezen kivul kb mindegyik tipushoz vannak automatak. 3. a veges automatak, amik elegge butak, pl nincs igazan memoriajuk. 2. a veremautomatak, amiben mar van memoria. 1. a Turing gepek (nincs koze a Turing teszthez), amiknek egyik noveltuma, hogy nincs olyan algoritmizalhato dolog a mai napig, amit ne tudnanak megcsinalni. Ertelemszeruen amit veges automata tud azt verem automata is, es persze tranzitiven tovabb Turing gep is.
Amit igazan ossze kell szedni ebbol, hogy ha egy sorszamot mondanak, akkor tudd, hogy az most melyik csoport (kornyezetfuggo, kornyezetfuggetlen, regularis), es hogy azt milyen automata allitja elo, illetve mik tartoznak ala (pl minden harmas kettes is, de nem minden kornyezetfuggetlen regularis). Ezen kivul csak a gyakorlatrol ismeretes eljarasokat kell tudni, mondjuk nem determinisztikus veges automatat determinisztikussa tenni, vagy hogy mi a kulonbseg a prefix es a valodi prefix kozt. Ha nagyon szuperek akarunk lenni akkor a lemmakat es bizonyitasokat is.
Alapfogalmak
Szoval nyelvekrol van szo, es nyelvek abc-kbol allnak. Fokepp nem emberek altal beszelt nyelvek. Kb mindig azt akarjuk majd kihozni valamibol, hogy csinalunk egy grammatikat vagy automatat, es akkor az milyen nyelvet allit elo, vagyis milyen szavakat ismer fel. Igy kompilaljak a programozasi nyelveket is (pl megfelelo zarojelezes, kifejezesekben az operatorok rendben vannak, kifejezes maguk, etc). Egy nyelv szavakbol, a szavak jelekbol allnak (mint dimat2 kodolas elmeletben). Rgo jelek (karakterek, szimbolumok) sorozata egy szo. Egymas utan lehet fuzni (konkatenalni) ket szot azzal, hogy a jeleiket egymas utan irod. Egy szot meg is lehet forditani igy. Ertelemszeruen ha egy szo jeleinek sorozata benne van egy masikban, akkor reszszava (substring) annak a masik szonak. Ha a legelejen akkor prefix, ha a legvegen akkor suffix (egyebkent inflix, de ez nem kell most). Minden szonak resszeva, prefixe, suffixe az ures szo (epszilon a jele, neha lambda), illetve onmaga. Az ures szo az a szo ami nulla jelbol all. Minden mas valodi resszo, prefix, suffix.
Itt alljunk is meg kicsit, mert van egy konnyen eltevesztheto dolog. Egy nyelvben levo osszes szo (vagyis egy adott abc-bol eloallithato osszes szo) altalaban V* jellel van irva, es lezartnak hivjuk (majd mindjart meglatjuk miert). Ekkor az ures szo is benne van (V az abc jele). V+, ha nincs benne. Ez a pozitiv lezart, mert minden szo hossza szigoruan pozitiv (nem nulla). De ez nem jelenti azt, hogy V+ az csak a lezartbol kiszedve az ures szot, mert mivan, ha a nyelvnek (a nyelvet alkoto abc-nek) eredetileg is resze volt az ures szo? Errol meg beszelunk kicsit kesobb. Na a lenyeg, hogy ha azt kerdeznek, hogy ha w = ux, vagyis u az w prefixe, x pedig suffixe, akkor hogyan tudom megallapitani hogy valodiak-e? Nos, egyszeruen ha u es x a lezartbol vannak, akkor nem biztos, hogy valodiak, hiszen lehetnek az ures szo is. Mindig gondoljuk at, hogy egy dolog lehet-e semmi is (majd regularis kifejezesnek es veremautomata mukodesenel is elojon).
Na nezzuk kicsit ezt a lezart dolgot. A neve amugy Kleene-lezart. Valojaban a lezart az az adott abc osszes letezo hatvanyanak unioja. Az elso hatvany az abcbol kepezheto jelsorozatok 1 hosszu szavai, a masodik a 2 hosszu, stb. Konvencio szerint a 0. hatvany az az ures szot tartalmazo nyelv. Egyebkent a nyelvek halmazok, szoval az unio, metszet, etc tulajdonsagok ugyanugy mukodnek. Egy ujdonsag a konkatenacio. Ket szo egymas utan fuzese ertelemszeru, ket nyelvve kb ugyanez. Ha a nyelveim L1 es L2, akkor ha siman egymas utan leirom: L1L2, akkor ez a konkatenacio jelolese (neha ponttal jelolik). Ez azt jelenti, hogy fogom L1 szavait, es mindhez hozzafuzom L2 osszes szavat. Vagyis nagyon nem kommutativ. Ellenben asszociativ, es az uniora disztributiv. Ezen kivul az ures nyelv (amiben nincs szo, nem pedig az ures nyelvet tartalmazo nyelv) a nulleleme. Mert ha valamivel ossze akarod fuzni, akkor az ures nyelvet kapod (semmihez sem fuzod hozza a nyelvet). Ez forditva is igaz (a semmihez probalod hozzafuzni). Az ures szot tartalmazo nyelv az egysegelem, az hagyja helyben a dolgokat (a semmit fuzod a szavak ele, a semmit fuzod a szavaidhoz). Ezek a reguaris muveletek. Unio, konkatenacio, lezaras (hatvanyozas nem, metszet sem).
Grammatikak
Ahogy a elozetes attekintesnel irtam, szinte minden nyelv eloallithato grammatikaval. Egy grammatika olyan szimbolumok es szabalyok osszessege, amivel adott 'alaku' jelsorozatokat allitasz elo. Ezek a szavak, amik nyelveket alkotnak. Szoval adott szabalyu nyelveket allitasz elo. Pl csak a-betuvel kezdodo szavak nyelve, vagy tukorszavak nyelve, paratlan hosszu tukorszavak nyelve, stb. Nagyon sok varacio van. Egy nyelv tartalmazhat veges sok szot (pl x es y karakterekbol allo 2 hosszu szavak), vagy vegtelen sokat (csak g betubol allo szavak, barmely hosszan).
Egy grammatika egy rendezett negyessel van jelole. G = (N,T,P,S). Neha mas a sorrend, vagy P helyett R, de ki lehet talalni, hogy mi micsoda. Jelen esetben P a szabalyok halmaza. Ezek olyan (a,b) parok, akol a N eleme, b pedig (N∪T)* beli (N es T uniojanak lezartja). Neha ugy is jelolik, hogy a nyil b. N es T halmazokban szimbolumok vannak, es szigoruan sincs kozos elemuk. Azert, mert nagyon mas szerepet toltenek be. T-ben olyan karakterek vannak, amik a nyelv betui (jelei). N-ben pedig amolyan valtozok. Pl ha A N beli, akkor lesz olyan szabaly, amiben A-t lecserelem valamilyen T beli elemre (akar tobbre is), vagy valamilyen N es T beli elemek kombinaciojara. Ez bonyolultabb, mint ahogy hangzik, de nem az. S egy specialis N beli szimbolum, mert mindig ebbol indulunk ki. Szoval ha van egy olyan szabalyom, hogy (S,Ab), akkor S helyett beirhatom, hogy Ab. Ekkor ha van egy (A,a) szabalyom, akkor Ab-bol lesz ab. Ebbol mar vilagosabb N es T elnevezese. T a terminalisok halmaza, mert ha csak ilyenek vannak a szoban, akkor terminal az eljaras (veget er). N a nemterminalisok halmaza. Ertelemszeruen egy szabaly bal oldalan mindig kell nemterminalis, a jobb oldalan pedig az van, amit akarsz, de legalabb egy valami. Az a valami lehet az ures szo is. Pl ha az elozo (S,Ab) szabaly melle lenne (A,ures szo), akkor lehetne S -> Ab -> b. Mindig veges sok szabalyunk van egy grammatikaban. Amugy az ilyen Ab, vagy uXv 'kevert' alaku cuccokat, hogy terminalis es nemterminalis is van benne mondatformanak hivjuk.
Az ilyen levezetesi szabalyok (neha produkcios szabalyok) ami alapjan a Chomsky hierarchia beosztja a nyelvtipusokat/grammatikatipusokat. Legalabbis 1-tol felfele, hiszen a 0. az everything goes kategoria. Az 1-es tipus a kornyezetfuggo nyelvek. Ilyenkor ha valami uAv mondatformat mar kihoztam (u es v is valami mondatforma, nem biztos, hogy terminalisok), akkor A-t nem cserelhetnem le az ures szora. Az ilyenekre mondjak, hogy hossz nem csokkento grammatika. Specialisan (S,ures szo) sem lehet, kiveve akkor es csakis akkor, ha nincs (valami,S) szabaly. Egy sem.
A kettes tipus erre nagyon hajaz, de egy nemterminalist barmikor 'eltuntethetek'. Vagyis A -> v alaku szabalyok, ahol v egy tetszoleges mondatforma, A pedig nemterminalis. A lenyeg, hogy A-nak nincs kornyezete, ezert is kornyezetfuggetlen. A harmas tipus kicsit hasonlo csak. Ott ha A -> v, akkor v biztos, hogy terminalis (tobb is lehet), vagy pedig A -> vB, ahol v tovabbra is biztos, hogy terminalis (vagy tobb), B pedig biztos, hogy nemterminalis. Ezt neha jobblinearis nyelvtannak is hivjak. Gondoljunk bele, hogy ha egy egyes tipusu nyelvben a nemterminalis oldalain levo u vagy v kozul az egyik terminalis mondatforma, a masik pedig az ures szo, akkor az pont ilyen. Jobb vagy bal linearis, attol fuggoen, hogy melyiket hagyjuk el.
Minden tipushoz van egy ugynevezett normal forma is. Egyeshez ez a Kuroda normal forma (lol). Ilyenkor csak bizonyos alaku szabalyok lehetnek. Ezek: (A,a), (A,B), (A,BC), (AB,CD), ahol ABCD N beli, a T beli. (S,uresszo) nem lehet tovabbra sem, csak ha nincs (valami,S) szabaly. A kettesekhez van a Chomsky normal forma, itt csak (A,a) es (A,BC) lehet. (S,uresszo) csak ha nincs (valami,S). A harmashoz harmas normal forma, ahol csak (A,aB) vagy (A,uresszo) lehet. Itt nincs kulon epszilon szabaly.
A normal formara hozashoz vannak kifejezett eljarasok, ezek voltak gyakorlaton. Ilyenek az epszilon-mentesites, lancmentesites, redukalo grammatikava teves (aktivak, elerhetok), hosszredukcio, illetve alterminalisok bevezetese. Ezek mindegyike olyasmi menetu, hogy egy halmazba kiveszel adott szabaly szerint elemeket, aztan a kovetkezo halmazba ugy veszel elemeket, hogy az elozo halmazbelieket vizsgalod valamilyen tulajdonsagra. Szoval epszilon-mentesiteskor eloszor leirod azokat a nemterminalisokat, amikbol kozvetenul levezetheto az ures szo (van olyan szabaly, hogy (X,uresszo)). Kovetkezore azokat, amikbol levezhetohetoek az elozoleg leirtak (vagyis van (Y,X) szabaly). Aktivak kikeresese kb ugyanez, de ott az kell, ami egybol terminal, nem az, ami egybol ures szoba visz. Elerhetoeknel van egy kis kulonbseg, hogy van egy 0. halmaz, amibe beirod a kezdoszimbolumot, aztan minden kovetkezo halmazba azt, ami levezetheto az elozo halmaz valamelyik elemebol. Az alterminalisos a legegyszerubb. Minden terminalishoz bevezetesz egy (segitokeszen hasonlo jelu) nemterminalist, amiknek az egyetlen szabalya az, hogy az a terminalis levezetheto beloluk. A lancszabaly es hosszredukcio egymasra hasonlit. Lanctalanitasnal ha egy nemterminalisbol levezetheto egy masik (nem kozvetlenul mindenkepp), akkor annak a szabalyait leirod helyette, ahogy vannak. Szoval ha van (A,B) es (B,C) es (C,X) meg (C,Y), akkor A-hoz B C X es Y minden szabalyat leirod. Ellenben ha (A,B) es (B,xC) van, akkor C nem ilyen. A hosszredukcio majdnem ez visszafele. Ha van egy (A,cddF) szabalyod, akkor csinalsz helyette (A,cZ1) (Z1,dZ2) (Z2,dF), szabalyt, ahol Z1 es Z2 teljesen uj nemterminalis. Mindig erdemes a vegen atgondolni, hogy N es T hogyan valtozott. Pl ha volt olyan nem elerheto, hogy csakis abbol lehetett volna levezetni egy terminalis, akkor annak is bucsut mondunk. Illetve meg valami: ha valami aktiv es elerheto, akkor hasznosnak nevezik. Akkor redukalt egy grammatika, ha minden nemterminalisa hasznos.
Automatak
Ez a legkonnyebb resze a tananyagnak, de ezt lesz itt a legnehezebb elmagyaraznom annak grafikus jellemebol adodoan. Ha gyakorlaton ment/erted az automatak mukodeset, akkor erdemesebb inkabb az orai jegyzetbol kiolvasni a szepen formalizalt definiociokat. Egyebkent ez sem olyan nagy baj, elvegre ezek leprogramozhato dolgok, vagyis pusztan elmeleti sikon is ertelmezhetoek, ami nem is arthat nekunk. Szoval itt maradjunk a technikai reszleteknel.
Egy automata is nagyjabol azt csinalja, mint egy grammatika, csak maskepp. Egyfajta 'alaku' jelsorozatokat allit elo, vagyis ebbol allo adott szabalyu nyelveket keszit. Itt is a szopromblema az egyik vizsgalando dolog, vagyis hogy egy jelsorozat (szo) az automata altal generalt nyelv eleme-e, vagy sem. Itt ez ugy mukodik, hogy az automata beolvassa a szot (jelrol-jelre, egyszerre csak egy karaktert), es ha elfogado allapotban all meg, akkor a szo a nyelv eleme. Ha nem akkor nem, illetve akkor sem, ha nem all le a mukodesben (de ez nekunk nem igazan jelenik meg). Egy grammatikanal ugye azt vizsgaltuk, hogy van-e olyan levezetes-sorozat, hogy a vizsgalando szot le tudjuk vezetni (szoval ha S-bol elkezdunk szabalyokat alkalmazni, vegul lesz-e olyan csak terminalisakbol allo mondatforma, hogy az pont a vizsgalando szo). Annyi kulonbseg lesz majd mondjuk verem automataknal, hogy pl ures veremmel elfogado automata lehet, hogy vegig tud menni a szon es nem akad el, sot, meg lehet az is, hogy elfogado allapotban all meg, de ha akkor nem ures a verem, a szo megsem lesz a nyelv eleme. Erre meg azert visszaterunk kesobb.
Eloszor beszeljunk a veges automatakrol. Ugye ezek allitjak elo a harmas tipusu nyelveket. Ket fajta van. Determinisztikus, es nem determinisztikus. A kulonbseg gyakorlatban elegge egyertelmu, hogy ha determinisztikus, akkor 'mindig tudjuk, merre menjunk'. Nezzuk meg a formalis definiciot, es meglatjuk a kulonbseget mas ertelemben is. Egy grammatika ugye (N,T,P,S) negyes volt. Egy automata egy rendezett otos (Q,T,Ł,q0,F). T ugyanaz, mint a grammatikaban, a terminalisok, vagyis a nyelv jelei. q0 nagyjabol S megfeleloje, a kezdeti 'valami', es Q beli. Ł is nagyjabol P megfeleloje, valamilyen lekepezes (allapot-atmeneti). Q az megint 'valamilyen valtozok' halmaza, nevezetesen allapotok. Q es T ertelemszeruen diszjunkt, mert mocskosul mas dolgok itt mar tenyleg. Ellenben F reszhalmaza Q-nak, az elfogado allapotok halmaza. Ha ez ures, akkor az automata csak az ures nyelvet fogadja el. Ha q0 F beli, akkor pedig az ures szo is a nyelv eleme, hiszen mar akkor is elfogadjuk, ha nincs benne egy T beli elem sem, mert el sem kezdtunk semmit csinalni.
Az allapotok kicsit hasonloak, mint szabalyok. Itt Ł-ben olyan elemek, vannak, hogy (q0a,q2) vagy (q2c,q1) (neha (q0,a,q2) jeloles, vagy Ł(q0,a) = q2). Ezt azt jelenti, hogy: (ha ebben az allapotban vagyunk, es ilyen jelet olvasunk be, akkor ebbe az allapotba kerulunk). Ritkan hasonlo betuzessel van, mint a grammatikak. Legyen most a kezdoallapot S, es masik ket allapot A es B, nem pedig q sorszamozas. Ekkor (Sa,B) es (Bc,A) lenne az elozo pelda megfeleloje. Vagyis valahol hasonlit a grammatika szabalyaihoz, de megis mas. Szoval Ł egy lekepezes QxT halmazbol Q halmazba. Ezeket az allapotokat leginkabb ugy kell elkepzelni, hogy eppen mi tortenik. Mondjuk ha T = {a, b}, szoval a nyelv csak a es b betukbol all, es ugy akarom, hogy csak paros szamu b lehet benne, akkor 'elnevezhetek' allapotoakt az alapjan, hogy most paros vagy paratlan b van benne (ez kifejezetten olyan automata lenne, ami az ures szot is elfogadja, vagyis q0 F eleme).
Ez volt a determinisztikus automata. A nem determinisztikusnal ket jelentos kulonbseg van. Eloszor is, hogy az allapot-atmeneti lekepezes messzirol sem injektiv, mert lehet (Sa,B) es (Sa,C) is egyszerre. Neha olyan is van, hogy elhagyunk egy szabalyt, de akkor igazabol mas tortenik. Tegyuk fel, hogy az elozo determinisztikus automataban, ahol T = {a, b}, nem irjuk fel az (Sb,valami) szabalyt. Ekkor az automata nem feltetlenul nem determinisztikus, mert ez csak annyit jelent, hogy egy nem megnevezett hiballapotba kerul (hibaallapot az, ahonnan mar sehogy sem jossz ki). Nem determinisztikus esetben ez sokkal jellemzobb, de nem lesz csak ettol nem determinisztikus egy automata. Hanem attol, hogy Ł nem Q halmazba kepez le, hanem valamilyen 2Q halmazrendszer reszhalmazaba. Magyarul egy allapotbol ugyanazzal a belvasott betuvel tobb allapotba is mehetunk. Egyebkent eddig nem hoztam ilyen peldat, de az is teljesen valid, ha nem masik allapotba megyunk (peldaul a hibaallpot is tokre ilyen). Itt amugy Ł helyett MŁ jelolest szoktak hasznalni. Ezen kivul az is jellemzo nem determinisztikus automatara, hogy tobb kezdoallapot van. Determinisztikusnal ilyen nincs, elvegre az a determinisztikussag jelentese, hogy mindig meghatarozza, hova visz a lekepezes. Ha mar rogton tobb kezdopont van, azt is valahogy el kene tudni dontenie.
Meg nehany szo a veges (nem)determinisztikus automatakrol. Egyfelol siman at lehet alakitani egyiket a masikka, sot meg harmas tipusu grammatikava is, szoval mindket fajtaval le lehet irni egy harmas tipusu nyelvet. Masfelet azert nem, mert nagyon limitalt memoriaja van egy ilyen automatanak. Peldaul tukorszot nem lehet vele csinalni, mert nem tudom hogyan megjegyezni, hogy eddig mik voltak leirva (erre tokeletes egy verem mondjuk). Vagy nem tudok olyant, hogy n darab a betu utan valami, mert nem tudok tetszoleges n szamot leszamolni. Olyan, hogy barmennyi a utan, vagy pontosan ot darab a utan valami, igen. Erre egy egesz kulon fejezetet akarok szanni, de ami regularis kifejezessel leirhato, azt lehet veges automataval is leirni. Illetve olyan is van, hogy egy automataban vannak 'felesleges', vagy nem elerheto allapotok, ilyenkor lehet minimalizalni. Szoval ha egy minimalis automataban valami nem levezetheto a kezdoallapotbol, rgo nem elerheto (azaz az automata nem osszefuggo), akkor az az automata igazabol nem is minimalis, hiszen meg lehet redukalni.
A memoriaigenyt kijavitando, adunk az automatahoz egy verem tipusu (First In First Out) tarolot. Szoval a veges automata rendezett otoset kiegeszitjuk ket elemmel. A verem (vagy veremszimbolumok halmaza) Z, es a verem kezdoszimboluma, z0 (neha #), szoval a jeloles: (Z,Q,T,Ł,#,q0,F). A lekepezes is modosul valamennyire, itt Ł ZxQx(T∪{ures szo}) -> Z*xQ. Magyarul mondjuk (#,q0,a) -> (a,q1), vagyis ha q0 allapotban a verem tetejen # van, es amit beolvasok az a, akkor a verem tetejere kerul a, es atmegyek q1 allapotba. Azert volt az unio az ures szot tartalmazo halmazzal, mert van, hogy 'semmit sem olvasok be, megis tortenik valami'. Ez nem teljesen igaz, de olyasmi. Itt kicsit modosul a szoproblema is. Szoval ha pl azt akarnam ellenorizni, hogy abaaba eleme a nyelvnek, akkor nem sorra haladok a karaktereken, hanem ugy kell elkepzelni, hogy minden karakter elott es utan van egy epszilon (az ures szo, ures karakter, semmi). A tukorszonal fasza pelda ez, mert ott ugy van elmagyarazva, hogy 'az automata egyszer csak tudja, hogy van a szo kozepe'. Nem igazan ez a helyzet, mert az automata ugye azt sem tudja, hogy tukorszavakat csinal. Hanem azt, hogy eddig ezek a szabalyok voltak alkalmazhatoak, most pont az epszilonos illik ide, es az elozo peldanal az abaEPSZILONaba resznel fogja tudni alkalmazni.
Egyfajta ertelmezes az is, hogy minden allapotvaltaskor vagy berakunk valamit a verembe, vagy kiveszunk valamit (push es pop). Ha olyan a szabaly, hogy a legfelso szimbolumot a veremben 'epszilonnal helyettesiti', akkor azt jelenti, hogy kivettuk, es az alatta levo szimbolum van most legfelul. Egy ures veremmel elfogado automata utolso szabalya mindig ilyen, es akkor urul ki az automata. Ez nem jelenti azt, hogy mindig # az utolso amit kiveszunk, mert akar az elso lepesben is kivehetnenk. Sot, igy ugye azt is latjuk, hogy lehet, hogy a verem az elso lepesben kiurul, de nem fogadjuk el rogton a szot, hiszen az automata halad tovabb. De sajnos nem mindig eldontheto egy szorol, hogy okes-e, mert az automata kerulhet ciklusba, nem all le a mukodese. Ez mar a veges automataknal is elofordulhatott amugy. Pl egy vegtelen hosszu szonal mikor allna le? Namarmost, mivel a veremautomata a veges automata fejlesztese, igy elo tud allitani minden harmas tipusu nyelvet, de minden kettes tipusut is (kornyezetfuggetlen nyelvek).
Ugy tudom ez mar nem a torzsanyag resze, de az egyes tipusu nyelvek Turing gepekkel eloallithatoak, amik olyan 'verem' automatak, hogy nem mindig a memoria legfelso elemet erjuk el, hanem minden atmenetnel csinalunk valamit (ir, olvas, frissit) azon a memoriacimen amin eppen vagyunk, aztan vagy jobbra, vagy balra lepunk egyet (persze csak ha nem a legszelen vagyunk).
Regularis kifejezesek
Volt mar rola szo korabban, hogy a regularis muveletek az (iterativ) lezaras, az unio es a konkatenacio. Azert ez a nevuk, mert a harmas tipusu nyelvek (a regularis nyelvek) zartak ezekre a muveletekre (nem lep ki a halmazbol, nem lesz masfele nyelv), vagyis a regularis kifejezesek lezartjai, egymassal valo unioja es konkatenacioja is regularis kifejezes. Szoval egy regularis kifejezes felepitesekor ezeket a muveleteket hasznalhatjuk. Egyszerusitve kicsit, a + (unio, VAGY (neha | a jele)), * (lezart, VALAMENNYI) es . (konkatenacio, UTAN (neha nincs jele, csak egymas utan irjak a dolgokat)) operatoraink vannak. Meg a zarojelezes. Fontos, hogy * muveletigyene nagyobb, mint . aminek pedig nagyobb, mint +. Szoval a + b.b* azt jelenti, hogy: a VAGY (b UTAN VALAMENNYI b), nem pedig azt, hogy (a VAGY b) UTAN VALAMENNYI b. Megjegyzem a valamennyi 0 is lehet.
A muveleteken kivul vannak az ugyenevezett elemi regularis kifejezesek. Ezek az ures halmaz, epszilon, es a (tetszoleges szimbolum). Mi igazan csak utobbit hasznaljuk. Az elozo peldaban a es b ilyen. Ezen kivul ugye regularis kifejezesek lezartja, pozitiv lezartja, unioja, konkatenaltja is regularis kifejezes, de ugyanez igaz regularis nyelvekkel is. Van egy olyan definicio is, hogy egy adott jelek feletti (adott abc feletti) regularis kifejezes, de ebben csak annyi a kulonbseg, hogy a T beli (ahol T a jelek halmaza, azaz T az abc).
Ezeken kivul bizonyos regularis kifejezeseket lehet egyszerusiteni is. Peldaul a konkatenacio disztributiv az uniora. Szoval (a+b).a* = (a.a* + b.a*). Mindket oldalrol. Az unio asszociativ mindket oldalrol. Epszilonnal konkatenalas olyan, mintha semmi sem tortenne. Egyebkent mivel harmas tipusu nyelveket lehet leirni igy, automatakbol is ugyesen lehet kiolvasni regularis kifejezeseket. Pl ha kezodallapotban van onmaga mutato nyil, mondjuk legyen rajta b, akkor biztos, hogy b* lesz a kifejezes eleje, mert mielott barhova atmegyek, irhatok tesztolegesen sok b-t.
Egyebek
Nehany dolog, amit mindenkepp meg akartam emliteni, de igazan nem tudtam beszoritani sehova konzekvensen.
Az elso, es legegyszerubb ilyen dolog a tukorszavakkal (palindroma, szimmetrikus szo) kapcsolatos. Nagyon ertelemszeruen tunik, hogy egy tukorszo leirhato ugy, hogy u = wx, ahol x az w visszafele. Ez hatarozottan egy tukorszo, de paros hosszu. Ellenben pl 'racecar' nem az. Nem tudom hol ketfele bontani. Kicsit az ilyen szavakat leiro veremautomata is mashogy mukodik. Volt korabban, hogy pl abccba ugy generalodik, hogy abc-t eler, aztan lesz egy epszilon a ket c kozt, es utana mindig kidobja a verem tetejerol ha ugyanazt a karaktert kapja. Ez csak a paros hosszunal mukodik. Paratlan hosszunal, ha jol emlekszem nem is tudjuk levzetni, mert kozepen egy karakter lenne, aztan utana hiaba tukorszonak megfelelo karakter jonne, siman vegigolvasna az egesz szot, mintha az elso fele lenne. Ehhez kell pl Turing gep.
Egy masik dolgo a veremautomatakkal, egy kifejezetten undoritoan kinezo formalis definicio, a veremautomata altal felismert nyelv.
N(A)={w∈T*| z0q0w ⇒*A p és p∈ Q}
Kiolvasva, az olyan T* beli szavak (vagyis csak terminalisakbol allok, azaz a nyelv tenyleges szavai), hogy a nagyon kezdoallapotbol (veremben is csak a kezdoszimbolum van, kezdoallapotban vagyunk, es w egy karaktere sem lett meg beolvasva) valahany lepesben p allapotba kerulunk (szoval nem akadtunk el).
Kiolvasva, az olyan T* beli szavak (vagyis csak terminalisakbol allok, azaz a nyelv tenyleges szavai), hogy a nagyon kezdoallapotbol (veremben is csak a kezdoszimbolum van, kezdoallapotban vagyunk, es w egy karaktere sem lett meg beolvasva) valahany lepesben p allapotba kerulunk (szoval nem akadtunk el).
Vegul egy fontos dolog, a Bar-Hiller lemma. Alapjaraton a pumpalo lemmahoz van koze, de kettes tipusu nyelvekhez. A pumpalo lemma lenyege, hogy ha felbonthato egy szo xvy alakra, akkor (nem ures) x es y tovabb hatvanyozhato (ha xvy legfeljebb p hosszu, ahol ez a p a pumpalo hossz). De csak ha a szo adott s hosszu legalabb. Na a Bar-Hiller lemmaban ot reszre bontjuk a szot harom helyett. Legyen u = vxyzw. Ekkor ha u megfelelo s hosszu volt, akkor xyz legfeljebb p hosszu, x es z nem ures szo, ellenben barhanyszor hatvanyozhatnam oket. Szoval roviden kell egy kettes nyelv, abban legalabb s hosszu szo amit vxyzw reszekre bontok, ahol xyz legfeljebb p hosszu, x es z nem ures, es igy barhanyszor hatvanyozom oket is az adott nyelv elemei. Ezekkel lehet megvizsgalni (indirekt), hogy egy adott nyelv hanyas tipusu.