4.6. Automaták ekvivalenciája, Gill tétele

A közös T, V halmazokkal bíró A=(Q, T, V, d, f) és A '=(Q ', T, V, d ', f ') automaták pQ és qQ ' állapotait egymással ekvivalens állapotoknak mondjuk (jelekben: pq), ha p és q az A, illetve B automatában ugyanazt a leképezést indukálja, azaz φ p, A =φ q, B . Magukat az A és B automatákat ekvivalenseknek nevezzük, ha bármelyikük bármely állapotához van a másiknak ezzel az állapottal ekvivalens állapota, azaz F A =F B . Speciálisan, két iniciális automatát akkor mondunk ekvivalensnek, ha kezdőállapotaik ekvivalensek egymással.

17. Tétel. Tetszőleges A automatával ekvivalens automaták M halmazában létezik olyan Q- izomorfiától eltekintve egyértelműen meghatározott A ' automata, amely bármely M- beli automatának Q- homomorf képe. A '- ként választható bármely M- beli automatához tartozó redukált automata.

Mint már korábban láttuk, egy Moore-automata tekinthető speciális Mealy-automatának. Az elmélet kiépítése folyamán fontos szerepet tölt be Arthur Gill (ejtsd: gill, zsill) következő eredménye, mely azt igazolja, hogy információ átalakítás szempontjából a két automata fogalom ekvivalens.

18. Tétel. (Gill tétele) Bármely Mealy-automatához létezik vele ekvivalens Moore-automata. Emellett, ha a Mealy-automata véges, akkor a hozzá megkonstruált, vele ekvivalens Moore-automata is választható végesnek.

Bizonyítás. Legyen A=(Q, T, V, d, f) tetszőleges Mealy-automata. Egy vele ekvivalens Moore-automatát a következőképp konstruálhatunk meg:

Legyen A '=(Q ', T, V, d ', f '), ahol Q '=QQ×T, továbbá tetszőleges q '∈Q ', aT párra

d '(q ', a)=(q ', a) ha q '∈Q,

d '(q ', a)=(d(q, a '), a) ha q '=(q, a ')∈Q×T,

f '(q ', a)=f(q, a) ha q '∈Q,

f '(q ', a)=f(d(q, a '), a) ha q '=(q, a ')∈Q×T.

Mutassuk meg, hogy minden qQ, wT * esetén f(q, w)=f '(q, w). Nyilván elegendő nem üres szavakra szorítkoznunk. Legyen tehát a 1, …a n T és tekintsük a q, q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n-1=d(q n-2, a n-1) állapotokhoz a b 1=f(q, a 1), b 2=f(q 1, a 2), …, b n =f(q n-1, a n ) kimenőjeleket. Világos, hogy ekkor definíció szerint f(q, a 1⋅⋅⋅a n )=b 1⋅⋅⋅b n . Másrészről, d ' és f ' definíciója alapján d '(q, a 1)=(q, a 1), d '((q, a 1), a 2)=(d(q, a 1), a 2)=(q 1, a 2), d '((q 1, a 2), a 3)=(d(q 1, a 2), a 3)=(q 2, a 3), illetve f '(q, a 1)=f(q, a 1)=b 1, f '((q, a 1), a 2)=f(d(q, a 1), a 2)=f(q 1, a 2)=b 2, f '((q 1, a 2), a 3)= =f(d(q 1, a 2), a 3)=f(q 2, a 3)=b 3, …, f '((q n-2, a n-1), a n )=f(d(q n-2, a n-1), a n )=f(q n-1, a n )=b n . Azt kaptuk tehát, hogy minden qQ- ra és wT *- ra f(q, w)=f '(q, w). Így minden A- beli állapothoz létezik vele ekvivalens A '- beli állapot. Természetesen az is igaz, hogy A ' minden A- ba eső állapotához van vele ekvivalens A- beli állapot. A és A ' ekvivalenciájához azt kell még megmutatnunk, hogy az A ' minden Q×T- beli állapotához is van az A automatának vele ekvivalens állapota. Ehhez legyen (q, a)∈Q×T. Mutassuk meg, hogy A ' ezen állapota ekvivalens az A automata d(q, a) állapotával, azaz f '((q, a), w)=f(d(q, a), w) minden wT * mellett fennáll. Nyilván most is elegendő nem üres szavakra szorítkoznunk. Legyen tehát a 1, …a n T.

Ekkor, az előbb kapott f(q, a 1⋅⋅⋅a n )=f '(q, a 1⋅⋅⋅a n ) egyenlőség fennállásának igazolásához hasonlóan bizonyítható, hogy f(q, a a 1⋅⋅⋅a n )=f '(q, a a 1⋅⋅⋅a n ). Viszont f(q, a a 1⋅⋅⋅a n )=f(q, a)f(d(q, a), a 1⋅⋅⋅a n ) és f '(q, a a 1⋅⋅⋅a n )==f(q, a)f '(d '(q, a), a 1⋅⋅⋅a n ) definíció szerint fennáll. d ' definíciója szerint d '(q, a)=(q, a), így f '(q, a a 1⋅⋅⋅a n )=f(q, a)f '((q, a), a 1⋅⋅⋅a n ). Másrészt f ' definíciója értelmében f '(q, a)=f(q, a). Mivel két kimenő szó pontosan akkor egyezik meg, ha betűről-betűre megegyezik, f '(q, a)=f(q, a) és f(q, a a 1⋅⋅⋅a n )=f '(q, a a 1⋅⋅⋅a n ) teljesülése ekkor f(q, a a 1⋅⋅⋅a n )=f(q, a)f(d(q, a), a 1⋅⋅⋅a n ) és f '(q, a a 1⋅⋅⋅a n )=f(q, a)f '((q, a), a 1⋅⋅⋅a n ) miatt azt jelenti, hogy f(d(q, a), a 1⋅⋅⋅a n )=f '((q, a), a 1⋅⋅⋅a n ). Ezzel kimutattuk, hogy az A automata d(q, a) állapota ekvivalens az A ' automata (q, a) állapotával. Tehát, valóban, az A automata ekvivalens az A ' automatával.

A tételhez azt fogjuk még igazolni, hogy A ' tekinthető Moore-automatának. Legyen g:Q ' → V tetszőleges olyan leképezés, melyre minden (q, a ')∈Q×T esetén g((q, a '))=f(q, a). ( g(q) értéke qQ mellett tehát lényegtelen azon túlmenően, hogy egy rögzített V- beli elemnek kell lennie.) Ekkor tetszőleges qQ, aT párra f '(q, a)=f(q, a), ahol (q, a)=d '(q, a). Mindemellett ha (q, a ')∈Q×T, úgy minden aT- re f '((q, a '), a)=f(d(q, a '), a), ahol (d(q, a '), a)=d '((q, a '), a). Tehát g:Q → V speciális megválasztásával kaptuk, hogy minden qQ ', aT párra f '(q, a)=g(d '(q, a)). A ' így valóban Moore-automata. (Érdekességként megjegyezzük, hogy g(q) értékére qQ esetén annyit kellett csak kikötni, hogy egy tetszőlegesen rögzített V- beli elem legyen.)

Végül, ha A véges, akkor Q, T, V rendre véges halmazok. Ekkor viszont Q '=QQ×T is véges, ami ( T és V végessége mellett) azt jelenti, hogy A ' véges. Ezzel a tételt teljesen bebizonyítottuk. ∎

6. Megjegyzés. Gill tétele lehetővé teszi, hogy bizonyos kérdésekben csupán Moore-automatákra szorítkozzunk, hiszen a tétel azt fejezi ki, hogy már Moore-automatákkal előállíthatók mindazok a leképezések, amelyek előállíthatók az általánosabb Mealy-automatákkal. Másrészt azt is meg kell jegyeznünk, hogy a Moore-automaták osztálya számos fontos konstrukcióra nézve nem zárt (állapothomomorf kép képzése, redukált automata meghatározása, stb.). Emiatt mégsem szorítkozhatunk minden vizsgálatnál csak a Moore-automaták osztályára. Végül megjegyezzük azt is, hogy hasonló konstrukcióval igazolható Gill tétele iniciális automatákra is.