4.2. Az automaták megadása

Egy automatát akkor tekintünk adottnak, ha a hozzá tartozó halmazok és függvények adottak. Egy automatát tehát úgy lehet megadni, hogy megadjuk a hozzá tartozó halmazokat és függvényeket. Ezen halmazok és függvények minden olyan típusú megadása lehetséges, ami a halmazok és függvények megadásánál szokásos.

4.2.1. Véges automaták megadása Cayley táblázattal

Véges halmazok és függvények megadásánál szokásos a művelettáblával történő megadás. Automaták művelettáblás megadását automaták Cayley táblázatának (ejtsd: kéjli) is hívjuk Cayley francia matematikus emlékére és tiszteletére, aki véges csoportok művelettábláinak leírására vezette be ezt a táblázatos módszert.

4.2.1.1. Véges Mealy-automata Cayley táblája

A táblázat bal felső sarkába írjuk az automata nevét, első sorában felsoroljuk az állapotait, első oszlopában pedig a bemenő jeleit. A táblázat (i+1)- edik sorában és (j+1)- edik oszlopában szerepel egy két dimenziós vektor, melynek első tagja azt mondja meg hogy az automata a j- edik állapotból az i- edik bemenő jel hatására melyik állapotába megy át, a másik tagja pedig azt mutatja, hogy a j- edik állapot az i- edik bemenő jel hatására milyen kimenőjelet ad ki.

4.2.1.2. Véges Moore-automata Cayley táblája

A táblázat bal felső sarkába írjuk az automata nevét, első sorában felsoroljuk az állapotait, első oszlopában pedig a bemenő jeleit. Minden állapot fölé beírjuk az állapotjelét. Így az első sor két rész-sorra oszlik. A táblázat (i+1)- edik sorában és (j+1)- edik oszlopában szerepel az az állapot, amibe az automata a j- edik állapotból az i- edik bemenő jel hatására átmegy.

4.2.1.3. Véges kimenőjel nélküli automata Cayley táblája

A táblázat bal felső sarkába írjuk az automata nevét, első sorában felsoroljuk az állapotait, első oszlopában pedig a bemenő jeleit. (Ezesetben az állapotjel maga az állapot, így nem kell az első sorban levő állapotok fölé írni az állapotjelet mint az előző esetben.) Itt is a táblázat (i+1)- edik sorában és (j+1)- edik oszlopában szerepel az az állapot, amibe az automata a j- edik állapotból az i- edik bemenő jel hatására átmegy.

4.5. példa - A csengő, mint automata

Vegyünk egy villamos csengőt. a 1 és a 2 jelöljék azon helyzeteket, mikoris nyomjuk vagy nem nyomjuk a csengőt. A csengő kezdetben az q 0 kezdőállapotban van, ami annak felel meg, hogy nem cseng. Az a 1 jel hatására, vagyis a csengő megnyomására átmegy a csengő a q 0 állapotból a q 1 állapotba. Megszakítva a csengő nyomását, vagyis az a 2 jel hatására a csengő átmegy nem csengő, azaz az q 0 állapotba. Leírásunkat táblázatba foglalva jutunk el a csengő következő absztrakt modelljéhez:


A q0 q1
a1 q 1 q 1
a2 q 0 q 0

A táblázat mutatja, hogy mely jel hatására mely állapotból mely állapotba megy át az automata. Például a 3. sor 3. oszlopában levő q 0 azt jelenti, hogy a 2 hatására a q 1 állapotból az q 0 állapotba megy át az automata. Táblázatos megadásnál iniciális automata esetén rendszerint az első oszlop jelzi a kezdőállapot oszlopát (azaz annak megadását, hogy különféle bemenő jelek hatására a kezdőállapotból mely állapotokba megy át az automata). ★

Megjegyezzük, hogy némely feladatoknál célszerű a táblázatos megadásban a sorok és oszlopok szerepeinek felcserélése, vagyis ekkor az oszlopok a bemenőjeleket (illetve a λ- t, ha az automata bemenőjel nélkül is állapotot válthat), míg a sorok az automata állapotait reprezentálják. Mindenképpen célszerű jelezni a táblázat bal felső sarkában, hogy a bemenőjelek, illetve az állapotok hol találhatóak. Elfogadó automaták esetén a végállapotokat is meg kell jelölni, pl. bekeretezéssel. A biztonság kedvéért a kezdőállapotot külön is jelezhetjük, pl. egy nyilacskával.

Parciális automata esetén a táblázat néhány helye üresen maradhat, amit ∅ jelölhet. Itt jegyezzük meg, hogy nem-determinisztikus automaták esetén a táblázat cellái az állapotok-, illetve a kimenőjelek halmazának részhalmazait tatralmazzák.

4.2.2. Véges automaták megadása gráfokkal

Véges automaták megadásának egy másik szokásos módja a címkézett irányított gráffal történő megadás.

4.2.2.1. Véges Mealy-automata megadása gráffal

A gráf minden egyes csúcsa meg van címkézve egy állapottal, a csúcsokból kivezető minden irányított él (mely hurokél is lehet) pedig meg van címkézve egy két dimenziós vektorral. Ezen vektor első komponense egy bemenő jel, a második pedig egy kimenőjel. Determinisztikus esetben minden csúcsból pont annyi él vezet ki, ahány bemenő jel van és az élek, valamint azok címkéi adják meg, hogy egy adott állapotból egy adott bemenő jel hatására az automata milyen kimenőjellel reagál és melyik állapotba megy át. Nevezetesen, a bemenőjeleket az élek címkéinek első komponense, a kimenőjeleket az élek címkéinek második komponense, az állapot átmeneteket pedig az élek kezdő- és végcsúcsainak címkéi adják meg. Egy él kezdőcsúcsában lévő állapot az él címke első (bemenő jel) komponense hatására épp abba az állapotba megy át, mellyel az él végcsúcsa van megcímkézve.

4.2.2.2. Véges Moore-automata megadása gráffal

A gráf minden egyes csúcsa meg van címkézve egy két dimenziós vektorral, melynek első komponense egy állapot, a második komponense pedig ezen állapot állapotjele. A csúcsokból kivezető minden irányított él (mely hurokél is lehet) meg van címkézve egy bemenő jellel. (Determinisztikus esetben itt is) minden csúcsból pont annyi él vezet ki, ahány bemenő jel van és az élek, valamint azok címkéi adják meg, hogy egy adott állapotból egy adott bemenő jel hatására az automata melyik állapotba megy át. Nevezetesen, a bemenőjeleket az élek címkéi, az állapot átmeneteket és az állapotjeleket pedig az élek kezdő- és végcsúcsainak címkéi adják meg. Egy él kezdő csúcsában lévő címke első (állapot) komponense az él címke (bemenő jel) hatására épp abba az állapotba megy át, ami az él végcsúcsában levő címke első (állapot) komponense. Az átmenet utáni állapotjel pedig az él végcsúcsában levő címke második (kimenőjel) komponense.

4.2.2.3. Véges kimenőjel nélküli automata megadása gráffal

Csaknem olyan szerkezetű gráffal történik a megadás mint a Moore-automata esetén. Az egyedüli lényeges különbség, hogy a csúcsok itt az állapotokkal vannak megcímkézve (és nem két dimenziós vektorokkal mint a Moore-automata esetén). Tehát a gráf minden egyes csúcsa meg van címkézve egy állapottal, a csúcsokból kivezető minden irányított él (mely hurokél is lehet) pedig meg van címkézve egy bemenő jellel. Most is igaz a (teljesen definiált) determinisztikus esetre, hogy minden csúcsból pont annyi él vezet ki, ahány bemenő jel van és az élek, valamint azok címkéi adják meg, hogy egy adott állapotból egy adott bemenő jel hatására az automata melyik állapotba megy át. Nevezetesen, a bemenőjeleket az élek címkéi, az állapot átmeneteket pedig az élek kezdő- és végcsúcsainak címkéi adják meg. Egy él kezdőcsúcsában lévő állapot címke az él címke (bemenő jel) hatására épp abba az állapotba megy át, ami az él végcsúcsában levő állapot címke értéke.

Itt jegyezzük meg, hogy elfogadó automata esetén szokás a végállapotokat pl. dupla körrel rajzolni, míg a kezdőállapot jelölésére szokás az adott állapotba egy plusz bemenő nyilat rajzolni.