Véges automata

A véges automata (angolul finite state machine vagy finite automaton) egy primitív számítógép számítási modellje, amely néhány állapotból és néhány átmenetből áll, és képes elfogadni vagy elutasítani a neki átadott szót.

Példa

A véges automatát informálisan egy állapotdiagrammal írjuk le, amely az automatát ábrázolja:

Az automata állapotokból épül fel, az ábrán ez három kerek állapot: q₀, q₁ és q₂. Ezen állapotok között átmenetek vannak, ezek a nyilak. Az automatában ezenkívül kell lennie kezdőállapotnak, ez a q₀ állapot. A kezdőállapotot gyakran úgy ábrázolják, hogy belemutat egy nyíl, amely egyetlen állapotból sem indul ki. Az automatában továbbá jellemzően van végállapot, azt dupla vonallal rajzoljuk, tehát az ábrán ez a q₂ állapot.

Az így felépített automata bizonyos szavakat elfogad. Az automatába szavakat adunk, és az automata megpróbálja elfogadni őket. Ha elfogadja, az automata IGEN-nel válaszol, ha nem fogadja el, NEM-mel. A mi automatánk az „a, b, c” betűkből álló szavakat próbálja elfogadni, ezért megpróbálhatjuk elfogadtatni az „abbc” szót.

A q₀ kezdőállapotban kezdünk, és a bemeneten az „abbc” szó van. Ezután követjük a nyilakat.

A szót a megszokott módon balról jobbra olvassuk, vagyis elsőként az „a” szimbólumot vesszük. Az „a” bemenethez tartozó nyíl a q₁ állapotba vezet, ezért átmegyünk oda, és az „a” szimbólumot töröljük a szóból. A bemeneten a „bbc” szó marad:

A „b” bemenethez tartozó nyíl visszamutat a q₁ csúcsba. Ismét töröljük az első betűt, és a bemeneten a „bc” szó marad. Újra a q₁ állapotban maradunk. Végül a bemeneten a „c” szó van. A q₁ állapotból a „c” bemenethez tartozó nyíl a q₂ állapotba küld minket.

A bemeneti szó összes betűjét kimerítettük, és a q₂ állapotban vagyunk, ami végállapot. Ez a véges automata tehát elfogadja az „abbc” szót.

Ha a végén nem elfogadó állapotban lennénk, az automata nem fogadná el a szót. Ugyanígy nem fogadná el a szót akkor sem, ha valamelyik állapotban nem lenne hová továbbmenni. Például az „ab” bemenetnél a q₁ állapotba jutnánk, és ott megállnánk – az automata az ilyen szót nem fogadja el. Ha az „aabbc” szót próbálnánk ki, megint pechünk van, mert a q₁ állapotból nem vezet nyíl az „a” betűre.

A véges automata tehát szavak valamilyen halmazának felismerésére szolgál. A gyakorlatban az automatát használhatnánk például arra, hogy megállapítsuk, a megadott bemeneti szó érvényes e-mail-cím-e.

A véges automata definíciója

Az előző intuitív elképzelést a véges automatáról formalizálnunk kell, hogy az automatákkal tovább és jobban tudjunk dolgozni.

Azt mondjuk, hogy a véges (determinisztikus) automata egy ⟨Q, Σ, δ, q₀, F⟩ ötös, ahol

• Q az állapotok véges halmaza,
• Σ (nagy szigma) az ábécé (szimbólumok/betűk véges halmaza),
• δ: Q × Σ ⟶ Q az átmeneti függvény,
• q₀ ∈ Q a kezdőállapot,
• F ⊆ Q a végállapotok (elfogadó állapotok) halmaza.

Ha visszatérünk az előző automatához,

azt mondhatjuk, hogy a Q állapothalmazban három állapot van: Q = {q₀, q₁, q₂}. A Σ ábécé azokat a betűket tartalmazza, amelyekből szavakat építhetünk, és amelyeket az automata aztán elfogad vagy elutasít. Itt ez valószínűleg a Σ= {a, b, c} ábécé, de lehet tetszőleges bővebb halmaz is. A q₀ kezdőállapot a q₀ állapot, ezen nincs mit változtatni. A végállapotok halmazában ennél az automatánál csak egy állapot van: F = {q₂}.

Az átmeneti függvény alatt azt a három nyilat értjük a betűkkel. Ha összezavar a δ: Q × Σ ⟶ Q jelölés, az csak azt jelenti, hogy a δ egy függvény (talán helyesebben leképezés), amely két paramétert vesz: egy állapotot a Q-ból és egy betűt a Σ-ból. A függvény meghívása után új állapotot ad vissza. Az átmeneti függvényünket táblázattal így definiálhatnánk:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Ha tehát meghívjuk a függvényt δ(q₁, c) alakban, a harmadik sort alkalmazzuk, és a függvény a q₂ állapottal válaszol – ugyanúgy, mint a diagram. Ha a q₁ állapotban vagyunk, és a bemeneten a „c” betű van, akkor a q₂ állapotba jutunk. Mielőtt formálisan definiáljuk, mit jelent, hogy az automata elfogad egy szót, a fogalom intuitív megértésére támaszkodunk, és megmutatunk még néhány példát.

További példák

1. Készíts automatát, amely bináris ábécé felett működik, azaz Σ= {0, 1}, és csak azokat a szavakat fogadja el, amelyek egyesre végződnek. Pl. elfogadja az 1, 01, 000001, 0101011 szavakat.

   

   Az automatánknak két állapota van – a q₀ kezdőállapot és a q₁ végállapot. Valahányszor a bemeneten az 1 számjegy van, átmegyünk a q₁ végállapotba, és ott is maradunk. Ezzel szemben ha a bemeneten a 0 számjegy van, akkor a q₀ állapotba megyünk, amely nem végállapot, és abban is maradunk.

2. Szerkessz bináris ábécé feletti automatát, amely csak azokat a szavakat fogadja el, amelyeknek a kezdőbetűje különbözik a végbetűjétől.

   

   Az automata már az első lépésben két „részautomatára” oszlik. Ha a szó nullával kezdődik, az automata a bal oldali részbe lép, és ott is marad, ha egyessel kezdődik, a jobb oldali részbe kerül. Innen már megszokott a menet: ha a bal oldali részben vagyunk, és a bemeneten 1 van, végállapotba kerülünk, és ott is maradunk. Ha a bemeneten 0 van, a q₁ állapotba kerülünk, amely nem végállapot.

   Az előző automatákkal ellentétben ennek az automatának több végállapota van, azaz F = {q₃, q₄}.

3. Szerkessz bináris ábécé feletti automatát, amely csak azokat a szavakat fogadja el, amelyek nem tartalmaznak két nullát egymás után.

   

   Ez az automata két okból érdekes: az első, hogy elfogadja az üres szót. Az automatába megpróbálhatunk üres szót adni, és az automata elfogadja, ha a kezdőállapot egyben végállapot is, ami ennél az automatánál így is van. Mivel az üres szó olyan szó, amely nem tartalmaz két nullát egymás után, ez így helyes. A másik érdekesség, hogy ennek az automatának minden állapota végállapot. Az egyetlen eset, amikor az automata nem fogadna el egy szót, az, ha egy állapotból nem vezetne ki átmenet. Ez a q₁ állapotban történik, amelynek nincs átmenete a 0-ra, mert akkor a szó két nullát tartalmazna egymás után.

4. Szerkessz automatát a {-,+,.,0,1,…,9} ábécé felett, amely csak azokat a szavakat fogadja el, amelyek számot ábrázolnak. Ez azt jelenti, hogy vagy egész számot, például 2, 548, 98263, vagy tizedes törtet (a programozásban szokásos tizedesponttal), például 5584.48, 3.14, és mindkettőt mínuszjeles negatív változatban is: -2, -548, -3.14, valamint kifejezetten kiírt pluszjellel is, azaz +2, +548, +3.14. Ezenkívül képesnek kell lennünk a 0.123 számot csak .123 alakban is leírni (a kezdő nulla nélkül), mégpedig mindkét előjellel. Bevezetünk egy segédjelölést: ahelyett, hogy tíz átmenetet írnánk ki a tíz számjegyre, az N szimbólumot használjuk.

   

5. Szerkessz bináris ábécé feletti automatát, amely csak a 0ⁿ1ⁿ alakú szavakat fogadja el, ami azt jelenti, hogy a szavak elején adott számú nulla áll, és utána ugyanannyi egyes következik. Ilyen szavak például a 0011, 00001111, 01.

   Ilyen automatát nem lehet építeni, mert sehol sem tudjuk „megjegyezni” a nullák számát. Több „részautomatát” kellene létrehoznunk, hasonlóan a második példához, csak hogy ezekből a „részautomatákból” végtelen sok kellene, minden n értékhez egy.

Az automata számításának formalizálása

A véges automatát magát már formálisan definiáltuk. Ezenkívül még meg kell határoznunk, hogy egy ilyen automata tulajdonképpen mit csinál, vagyis definiálnunk kell az automata számítását.

Az automata konfigurációja: azt mondjuk, hogy a ⟨q, w⟩ ∈ Q × Σ^∗ pár az automata konfigurációja, ahol q az aktuális állapot, amelyben az automata van, és w a szónak az eddig el nem olvasott része. A Σ^∗ a Σ ábécé lezárását jelöli, azt a halmazt, amely az összes olyan szót tartalmazza, amelyet a Σ ábécé betűiből össze lehet állítani. A lezárásnak része az üres szó is, amelyet ε jelöl.

Ha adott a ⟨Q, Σ, δ, q₀, F⟩ automata, és a w szót próbáljuk elfogadtatni, akkor az automata a ⟨q₀, w⟩ kezdeti konfigurációban van. Ha visszatérünk az automatához

és a w = abbc szót akarjuk elfogadtatni, akkor a kezdeti konfiguráció ⟨q₀, abbc⟩ lesz.

A számítás lépését relációként definiáljuk, ↦ jelöléssel, a (Q × Σ^∗) × (Q × Σ^∗) halmazok között, vagyis az automata konfigurációi között. Legyen w = w₀w₁… w_n a w szó eddig el nem olvasott része. Azt mondjuk, hogy a ⟨q₁, w₀w₁… w_n⟩ és a ⟨q₂, w₁… w_n⟩ pár a ↦ relációban áll, ezt így írjuk

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

akkor és csak akkor, ha δ(q₁, w₀) = q₂. Visszatérve a példánkhoz, a kezdeti konfiguráció ⟨q₀, abbc⟩. A diagramról látjuk, hogy az „a” bemenetre továbbléphetünk a q₁ állapotba. Felírhatjuk tehát, hogy

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

mert δ(q₀, a) = q₁. Ezzel végrehajtottunk egy számítási lépést – megnéztük, melyik állapotba kell mennünk az adott bemenetre (= a szó még el nem olvasott részének első betűjére), átmentünk oda, és a szó el nem olvasott részéből töröltük az első betűt. Így új konfigurációt kaptunk.

A számítási lépés relációjának reflexív és tranzitív lezárását ↦ ^∗ jelöli. Ha tehát felírjuk, hogy K₁ ↦ ^∗ K₂, ahol K₁, K₂ az automata konfigurációi, az azt jelenti, hogy a K₁ konfigurációból néhány számítási lépéssel eljuthatunk a K₂ konfigurációba, vagyis létezik a konfigurációknak olyan véges sorozata, hogy:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Például a mi automatánkban ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, mert ha két számítási lépést végzünk, megmarad a „bc” szó, és a q₁ állapotban maradunk. Vagyis létezik a konfigurációknak ez a sorozata:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Az automata elfogadja a w szót akkor és csak akkor, ha létezik olyan q_f ∈ F, hogy $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Ez azt jelenti, hogy az automata akkor és csak akkor fogadja el a w szót, ha létezik a számítási lépéseknek olyan sorozata, hogy a sorozat végén a teljes szót elolvastuk, és az automata egy végállapotában vagyunk. Azt, hogy a teljes szót elolvastuk, az fejezi ki, hogy a konfigurációban a szó helyén ε áll, ami az üres szó. A mi automatánk elfogadja az abbc szót, mert létezik a konfigurációknak ez a sorozata:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

és a q₂ állapot végállapot, q₂ ∈ F.

Az automata által elfogadott nyelv az összes olyan szó halmaza, amelyet az automata elfogad. Az A automata nyelvét L(A) jelöli. Igaz tehát, hogy L(A) ⊆ Σ^∗ és

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ elfogadja a }w\text{ szót}\}$$

Reguláris nyelv az olyan nyelv, amelyet valamilyen véges automata elfogad.

Két véges automata ekvivalens, ha ugyanazt a nyelvet fogadják el. Vagyis az A₁ és A₂ automaták ekvivalensek, ha L(A₁) = L(A₂).

Források

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools