Determinisztikus automaták

Egy régi postban már láttunk regexeket, amikkel "pontosan a reguláris nyelvek jelölhetők". Egy input stringre vagy illeszkedik egy regex, vagy nem; ha vesszük az összes stringet, amire illeszkedik az R regex, ezt mondjuk jelölhetjük L(R)-rel (a |R| jelölés is futhat még), és az R regex által megadott nyelvnek hívjuk (mert stringek akármilyen halmazát nyelvnek mondjuk). A regex többek közt azért jó, mert végtelen nyelveket is lehet véges regexekkel jelölni, tehát eggyel kulturáltabb dolog, mint mondjuk a nyelv elemeinek felsorolása egyesével egy kőtáblán. 

Egy másik eszköz, amivel szintén lehet nyelveket megadni, a véges automata. Ebből a "véges" szó annyira be van drótozva, hogy nem is mondjuk ki mostanzól. Egy automatának vannak

• állapotai, véges sok, legalább egy van - az állapothalmaz jele általában Q
• bemenő ábécéje, jele általában Σ, olyan szavakat fogad el vagy utasít el, melyek Σ betűiből állnak
• kezdőállapota, jele általában q₀, Q-beli (nyilván. állapot.)
• végállapotHALMAZa, jele általában F ⊆ Q
• átmenetFÜGGVÉNYe, δ: Q×Σ → Q. Azaz egy állapot és egy betű ismeretében egy állapot az eredmény.

Ha ezeket egyetlen rendszerként kezeljük, akkor rendszerint M = (Q,Σ,δ,q₀,F) szokott lenni a sorrend (egyébként: a zárójelekből többféle van. Ez a kerek zárójel, ha ebbe felsorolunk dolgokat, az listát eredményez, tehát a sorrend és a multiplicitás is számít. A kapcsos halmazt deklarál, ott a sorrend nem számít és a multiplicitás sem. Mivel itt számít, hogy az első koordináta az állapothalmaz, a második az input jelek halmaza stb. ezért kerek zárójelet használunk. Az egyenlőség pedig egy értékadó egyenlőség: ezt az öt dolgot így együtt jelöljük M-mel.)

Egy automatát gráfként le is lehet rajzolni: az állapotok lesznek a csúcsok, és az átmenetek a címkézett élek: ha δ(q,a)=p, akkor ebből egy q-ból p-be menő, a-val címkézett nyíl lesz. A kezdőállapotot valamiféle bemenőnyíllal szokás jelölni, a végállapotokat pedig vagy kimenőnyíllal, vagy duplán karikázva.

Például:

Ez egy automata, állapotai Q={q₀, q₁, q₂, q₃}, q₀ a kezdőállapot, q₂ az egyetlen végállapot, a bemenő ábécé {a,b}, az átmenetfüggvény pedig (figyel) például q₁-ből a hatására q₀-ba viszi az automatát.

Vagyis, a δ függvényt úgy érdemes fejben interpretálni, mint "ha p állapotban vagyok és az a jelet kapom, akkor menjek át q állapotba", ezt fejezzük ki δ(p,a)=q-val.

Ezt értelemszerűen ki lehet terjeszteni szavakra is: "ha p állapotban vagyok és a w stringet kapom, akkor betűnként végigolvasva és minden betű olvasásakor a δ szerint megfelelő állapotba átlépve eljutok a q-ba", ezt fejezzük ki δ(p,w)=q-val. Ha a δ egyértelmű, hogy melyik átmenetfüggvény, akkor szokás elhagyni is az egészet és simán pw=q-t írni.

A fenti automata pl. ha q₁-ben megkapja az aabaa stringet, akkor a q₀,q₁,q₃,q₂,q₃ állapotok végiglátogatása után q₃-ba jut, tehát q₁aabaa=q₃.

Az automata akkor fogadja el az input szót, ha az q₀-ból egy végállapotba viszi, és elutasítja, ha nem végállapotba. (formálisan elfogadja w-t, ha q₀w ∈ F.) Az összes M által elfogadott szó nyelve pedig L(M).

A fenti automata például akkor fogad el egy szót, ha az páros sok a-t tartalmaz és van benne legalább egy b betű. Ezt onnan láthatjuk most, hogy a bal felső állapotból a szó hatására a bal alsóba kell jussunk. Az a betű mindenképp a bal-jobb térfelet váltja, tehát ha páros sok jön belőle, akkor a bal oldalon, ha páratlan sok, akkor a jobb oldalon végzünk. Lefelé pedig csak a b betűvel lépünk, tehát abból is kell egy. Ezek után teljesen mindegy, ha jön további b betű, az már nem váltja az állapotot.

Erre van regex is, pl.

(aa)*b(ab*ab*)*+a(aa)*b(ab*ab*)*ab*

hát nem túl szép, nem túl rövid, nem túl elegáns, de jobbat nem tudok. (aki igen: feel free to comment :-) ) A regex első fele kezeli azt az esetet, mikor az első b előtt is és utána is páros sok a betű jön, a második fele meg azt, mikor páratlan-páratlan sok. (Hozzáteszem, hogy most klasszikus, elméleti regexről beszélek, ezért nem használok pl. lookaheadet. Majd fogok.)

Nem véletlen, hogy ehhez az M automatához van ekvivalens (ugyanazt a nyelvet jelölő, mint amit az automata elfogad, avagy L(M)=L(R)) R regex, mert

pontosan a reguláris nyelvek ismerhetők fel automatával.

Sőt, van olyan algoritmus is, ami az input regexből készít egy ekvivalens automatát. Ez azért jó, mert a regexes postban nem beszéltem arról, hogy hogy is lehet regexet illeszteni, vagyis eldönteni, hogy az input R regex illeszkedik-e az input szövegre vagy sem - nos, ezt például automatával már könnyű, hiszen csak végig kell olvasnunk. Tehát illesszünk regexet úgy, hogy először készítünk egy vele ekvivalens véges automatát, majd annak beadjuk a stringet. (Az automata O(m) lépésben végigolvassa az m hosszú input stringet, tehát gyors is az illesztés.)

OK?

NEM

mert a regex - DFA konverzió (btw a DFA a Deterministic Finite Automaton rövidítése) exponenciális méretű automatát is eredményezHET legrosszabb esetben! Például az Σ*aΣΣΣ..Σ regex, ahol az a után n darab Σ áll, ami annyit mond, hogy hátulról az n+1. betű a kell legyen (erről nem állítom, hogy gyakorlati oldalról feltétlen motivált lenne, viszont kegyetlenül el tud bánni az algoritmusunkkal), az ezzel ekvivalens legkisebb automata is 2ⁿ állapotú, ami

gombócból is sok.

(déja vu.)

Ezért valójában nemdeterminisztikus automatákat szokás használni, üres átmenettel, mert arra

van lineáris konverzió

és sokat nem ront az illesztési sebességen. Lesz róluk post.

folytköv