4.5. Redukált automata. Véges determinisztikus automaták minimalizálása

Az előző fejezetben láttuk, hogy tetszőleges automata alfabetikus leképezések egy sokaságát indukálja. (Minden állapot indukál egy alfabetikus leképezést, melyek közül egyesek egybeeshetnek.) Jelölje F A ={φ q |qQ} egy A=(Q, T, V, d, f) által indukált leképezések sokaságát. Egy ilyen sokaságot az A automata által indukált leképezések családjának is fogunk hívni. Előfordulhat, hogy p, qQ, pq és mégis φ p =φ q . Most azzal a kérdéssel foglalkozunk, hogy ha egy F leképezés családhoz sikerül már olyan A automatát találnunk, melyre F A =F teljesül, hogyan tudjuk helyettesíteni A- t egy ugyanilyen tulajdonságú, de minimális állapotszámú A 0 automatával. (Természetesen ennek a dolognak akkor van igazán értelme, ha az állapothalmaz véges.) Definiáljunk egy A=(Q, T, V, d, f) Mealy-automata állapothalmazán egy ρ A relációt: q ρ A pφ q =φ p (azaz q ρ Q pf(q, w)=f(p, w) minden w bemenő szóra). Könnyen belátható, hogy az így definiált ρ A reláció kongruencia, s ráadásul a ρ A - hoz tartozó C A kompatibilis osztályozás maximális abban az értelemben, hogy minden más kompatibilis osztályozás C A - nak finomítása. Ezesetben C A - t az A automatához tartozó maximális kompatibilis osztályozásnak is hívjuk, az Aρ A faktorautomatát pedig az A -hoz tartozó redukált automatának mondjuk. Általában, egy A=(Q, T, V, d, f) Mealy-automatát redukáltnak nevezünk, ha tetszőleges p, qQ pár esetén p ρ A qp=q.

Ehhez két fontos megjegyzésünk van:

5. Megjegyzés.

1. Egy automatához tartozó redukált automata a legkisebb állapotszámmal (illetve végtelen automaták esetén a legkisebb számosságú állapothalmazzal) bíró olyan automata, amely ugyanazt a leképezés családot állítja elő, mint az illető automata.

2. Egy automata akkor és csak akkor redukált, ha Q- izomorf saját magával.

Egy A automata minimalizálásán az A- hoz tartozó A 0 redukált automata megszerkesztését értjük. Ebben a vonatkozásban az A 0 redukált automatát minimálisnak hívjuk. A következő, véges automaták minimalizálására szolgáló algoritmus D. D. Aufenkamp és F. E. Hohn nevéhez fűződik.

4.5.1. Aufenkamp-Hohn-féle minimalizációs algoritmus

Egy véges A=(Q, T, V, d, f) automata esetén az A 0 redukált automatához úgy jutunk el, hogy a

p, qQ:(p ρ A q⇔∀wT *:f(p, w)=f(q, w))

(azaz minden p, qQ pár esetén p ρ A q akkor és csak akkor, ha f(p, w)=f(q, w) bármely wT * esetén fennáll) relációhoz tartozó C A osztályozást osztályozások egy C 1, C 2, … sorozatán keresztül szerkesztjük meg, melyeket a következőképp definiálunk:

(i)∀p, qQ:(C 1[p]=C 1[q]⇔∀aT:f(p, a)=f(q, a))

(azaz minden p, qQ párra a C 1 osztályozás szerint p és q akkor és csak akkor esnek egy osztályba, ha ugyanazon bemenő jelre ugyanazon kimenőjellel reagálnak);

(i i) ha i ≥ 1C i+1[p]=C i+1[q]⇔C i [p]=C i [q]∀aT:C i [d(p, a)]=C i [d(q, a)].

(Azaz ha i ≥ 1, úgy a C i+1 osztályozás szerint p és q akkor és csak akkor esnek egy osztályba, ha egyrészt már C i szerint is egy osztályba esnek, másrészt pedig minden bemenő jel hatására egy és ugyanazon C i szerinti osztályba mennek át.)

Először megszerkesztjük a Q állapothalmaz C 1 szerinti osztályait, mikoris pontosan akkor tartozik két állapot egy osztályba, amikor minden egyes bemenő jel hatására ugyanazt a kimenőjelet adják ki. (Lásd (i).) Ezután minden egyes m>1- re megszerkesztjük a C m szerinti osztályokat egészen addig, míg C m =C m+1 teljesül. Látni fogjuk, hogy ilyen m létezik, s nagysága legfeljebb |Q|-1. Igazolni fogjuk, hogy ez a C m osztályozás épp a Q maximális kompatibilis osztályozása. Ezután a redukált automata megszerkesztése van csak hátra, melynek szerkezete AC m =(C m , T, V, d C m , f C m ), ahol minden C m [q]∈C m , aT- re d C m (C m [q], a)=C m [d(q, a)], illetve f C m (C m [q], a)=f(q, a). Speciálisan, ha az eredeti automata iniciális volt, és a kezdő állapota q 0 volt, akkor a redukált automata is választható iniciálisnak, éspedig úgy, hogy a kezdőállapotát C m [q 0]- nak választjuk.

4.5.2. Kiegészítés az Aufenkamp-Hohn minimalizációs algoritmushoz

Ha a célunk nem az automatához tartozó (redukált) minimális állapotszámú automata, hanem csupán a φ q 0 - t indukáló minimális iniciális automata meghatározása, akkor ehhez az A=(Q, T, V, q 0, d, f) minimalizálandó automata helyett annak a kezdőállapotból elérhető állapotok által meghatározott, azaz a Q '={≫d(q 0, w)|wT *} állapothalmazzal rendelkező A '=(Q ', T, V, q 0, d ', f ') iniciálisan összefüggő állapot-részautomatáját minimalizáljuk. (Emlékeztetőül: a ≫d(q 0, w)∈Q + szó utolsó betűjét jelenti.) A q 0- ból el nem érhető állapotok ugyanis nem játszanak szerepet a φ q 0 leképezés indukálásában (az összes q 0- ból elérhető állapot viszont igen). Mivel A végessége miatt ekkor a kezdőállapotból csak azok az állapotok érhetők el, melyek legfeljebb |Q|-1 hosszúságú szavakkal elérhetők, a Q állapothalmaz Q ' részhalmaza algoritmikusan meghatározható. Erre a következő módszer kínálkozik: Legyen először Q 0={q 0}. Ezután minden i ≥ 1- re legyen Q i+1={q|∃q '∈Q i , aT:d(q ', a)=q}. Ha valamely i ≥ 1- re elérjük, hogy Q i =Q i+1, akkor Q '=Q i . Nyilván az ilyen i- re i ≤ |Q|-1 teljesül.

Most meg fogjuk mutatni, hogy az algoritmus és a kiegészítő megjegyzésünk korrekt. Érvényesek a következő megállapítások:

1. Segédtétel. Tetszőleges p, qQ párra és i ≥ 1 természetes számra C i [p]=C i [q] akkor és csak akkor áll fenn, ha minden i- nél nem hosszabb wT * bemenő szóra f(p, w)=f(q, w).

Bizonyítás. Először azt igazoljuk, hogy tetszőleges p, qQ párra és i ≥ 1 természetes számra C i [p]=C i [q]- nek következménye, hogy minden i- nél nem hosszabb wX * bemenő szóra f(p, w)=f(q, w). Állításunkat teljes indukcióval fogjuk igazolni.

Ha i=1, akkor egy i- nél nem hosszabb szó vagy az üresszó, vagy a bemenő jelhalmaz egy eleme. Az üresszóra f(p)=λ minden pQ pár esetén fennáll, tehát f(p, λ)=f(q, λ)(=λ) akkor is igaz, ha speciálisan C 1[p]=C 1[q] valamely p, qQ- ra. Amennyiben viszont aT és C 1[p]=C 1[q], akkor f(p, a)=f(q, a) is teljesülni fog összhangban a C 1 osztályozás definíciójával.

Tegyük fel most, hogy valamely i ≥ 1- re igaz az állítás. Mutassuk meg, hogy ekkor i+1- re is igaz. Először észrevesszük, hogy minden olyan p, qQ párra, melyre C i+1[p]=C i+1[q] fennáll, definíciónk értelmében C i [p]=C i [q] is igaz. Ekkor viszont az indukciós feltevésünk miatt minden olyan wT *- ra, melyre w nem hosszabb i- nél, f(p, w)=f(q, w). Azt kell tehát csak belátnunk, hogy amennyiben egy w szó hossza i+1, akkor minden olyan p, qQ párra, melyre C i+1[p]=C i+1[q], fennáll a d(p, w)=d(q, w) egyenlőség. Igen ám, de ekkor w előáll w=a v alakban, ahol aT, s ugyanekkor vT * pedig i hosszúságú. Ekkor tehát f(p, w)=f(p, a v)=f(p, a)f(d(p, a), v), illetve f(q, w)=f(q, a v)=f(q, a)f(d(q, a), v). C i+1[p]=C i+1[q] fennállása mellett C 1[p]=C 1[q] is igaz, amiből f(p, a)=f(q, a) következik (lásd i=1 eset). Másrészt C i+1[p]=C i+1[q] definíció szerint azt is jelenti, hogy minden aT esetén C i [d(p, a)]=C i [d(q, a)]. Viszont az indukciós feltevésünk értelmében ekkor minden i hosszúságú vT * szóra f(d(p, a), v)=f(d(q, a), v). Ehhez figyelembe véve az előbb megállapított f(p, a)=f(q, a) egyenlőséget, fennáll az f(p, a)f(d(p, a), v)=f(q, a)f(d(q, a), v) egyenlőség is, ami épp azt jelenti, hogy f(p, a v)=f(q, a v). Ez viszont w=a v értelmében az f(p, w)=f(q, w) egyenlőséghez vezet.

Most azt tegyük fel, hogy adott p, qQ és i ≥ 1 mellett f(p, w)=f(q, w) teljesül minden wT *, |w| ≤ i feltételnek eleget tevő bemenő szóra. Igazoljuk teljes indukcióval, hogy ekkor C i [p]=C i [q].

Ha i=1 és minden aT- re (azaz minden wT *, |w|=1- re) f(p, a)=f(q, a), akkor C 1[p]=C 1[q] definíció szerint teljesül. Tegyük fel ezután indukciós feltevésként, hogy valamely rögzített i ≥ 1- re valahányszor egy p, qQ párra f(p, w)=f(q, w) minden |w| ≤ i- nek eleget tevő wT * bemenő szó esetén fennáll, mindannyiszor C i [p]=C i [q]. Legyen ezután minden i+1- nél nem hosszabb nem üres wT * bemenő szó esetén f(p, w)=f(q, w). Ekkor w=a v, ahol aT és vT *, ahol |v| ≤ i. Ez többek között azt jelenti, hogy minden aT- re és i- nél nem hosszabb vT *- ra f(d(p, a), v)=f(d(q, a), v). Indukciós feltevésünk értelmében így C i [d(p, a)]=C i [d(q, a)] tetszőleges aT esetén teljesül. Másrészt ha f(p, w)=f(q, w) minden i+1- nél nem hosszabb w, vT * bemenő szóra teljesül, úgy teljesül minden i- nél nem hosszabb bemenő szóra is. Ez viszont indukciós feltevésünk miatt C i [p]=C i [q]- t eredményezi. Ezt összevetve azzal, hogy C i [d(p, a)]=C i [d(q, a)] tetszőleges aT esetén teljesül, definíció szerint kapjuk, hogy C i+1[p]=C i+1[q]. Ezzel az állítást igazoltuk. ∎

2. Segédtétel. Ha valamely m ≥ 1 természetes számra C m =C m+1, akkor minden j, k ≥ m természetes számpárra C j =C k .

Bizonyítás. Állításunkhoz nyilván elég igazolni, hogy ha C m =C m+1 akkor C m+1=C m+2. Legyen tehát valamely m ≥ 1 természetes számra C m =C m+1, s legyen valamely p, qQ állapotpárra C m+1[p]=C m+1[q]. Ekkor viszont definíció szerint tetszőleges aT- re teljesülni fog a C m [d(p, a)]=C m [d(q, a)] egyenlőség. Viszont C m =C m+1 miatt így C m+1[d(p, a)]=C m+1[d(q, a)] is fenn fog állni. Ez viszont a feltételezett C m+1[p]=C m+1[q] egyenlőséggel együtt azt fogja definíció szerint eredményezni, hogy C m+2[p]=C m+2[q]. Vagyis azt kaptuk, hogy ha C m =C m+1, akor minden olyan p, qQ párra, melyre C m+1[p]=C m+1[q], fennáll C m+2[p]=C m+2[q] is. Ez pedig pontosan azt jelenti, hogy C m+1=C m+2. ∎

Most igazoljuk, hogy az Aufenkamp-Hohn féle algoritmus valóban korrekt.

16. Tétel. Az Aufenkamp-Hohn féle algoritmus véges sok lépésben minimális redukált automatát állít elő.

Bizonyítás. Ha C 1 szerint minden állapot egy osztályba esik, akkor minden állapot egy és ugyanazon kimenőjellel reagál egy és ugyanazon bemenő jelre. Ekkor C 1=C 2 nyilvánvaló. Ez esetben tehát a 2. Segédtétel értelmében a minimális automata egyetlen állapottal fog rendelkezni, s egy-egy bemenő jelre ez a redukált automata egy és ugynazon kimenőjelet adja ki, mint az eredeti automata bármelyik állapota.

Tegyük fel most, hogy |C 1|>1. Ha C 1=C 2, akkor m=1 és ismét a C 1 a kívánt maximális kongruencia osztályozás. Ellenkező esetben C 2- nek legalább eggyel több osztályt kell tartalmaznia mint C 1- nek, vagyis legalább három osztályt. Ezt folytatva lesz egy egyre finomodó osztályozás rendszerünk, ahol minden egyes osztályozás legalább eggyel több osztályt fog tartalmazni mint az előző. Tekintettel arra, hogy feltételeztük |C 1|>1- t, továbbá figyelembe véve, hogy legfeljebb |Q| számú osztálya lehet egy-egy osztályozásnak (hisz egy adott osztályozásnál minden osztálynak kell legalább egy Q- beli elemet tartalmaznia), azt kapjuk, hogy lesz olyan m ≤ |Q|-1, melyre C m =C m+1. Valóban, ha veszünk valamely m>1- re egy egyre finomodó olyan osztályozás rendszert, melyre C 1C 2⊃⋅⋅⋅⊃C m , akkor ha C 1- nek legalább két, C 2- ek legalább három, …, C m - nek legalább m+1 eleme van és összesen |Q| számú állapotunk van (vagyis legfeljebb |Q| számú osztálya lehet egy-egy osztályozásnak), akkor m+1 ≤ |Q| fennállása azt is jelenti, hogy m ≤ |Q|-1. Így viszont valóban lesz olyan m ≤ |Q|-1, mikoris C m =C m+1, ami a 2. Segédtétel értelmében azt is jelenti, hogy teszőleges i ≥ m- re C i =C m . Ez azonban az 1. Segédtétel miatt azt is eredményezi, hogy teszőleges olyan p, qQ állapotpárra, melyre C m [p]=C m [q], teljesülni fog a f(p, w)=f(q, w) egyenlőség, akármilyen hosszú is a tekintett wT * bemenő szó. Ezzel beláttuk, hogy C m egy kongruencia osztályozás, aholis m ≤ |Q|-1.

Be kell még látnunk, hogy C m valóban maximális kongruencia osztályozás, vagyis ha két állapot nem tartozik C m szerint egy osztályba, akkor az általuk indukált leképezések különbözőek. Legyen p, qQ két állapot, mely C m szerint nem tartozik egy osztályba. Ha már C 1 szerint sem tartoznak egy osztályba, akkor valamely aT- re f(p, a)≠f(q, a) és akkor valóban igaz, hogy φ p φ q . Ellenkező esetben van egy maximális k<m, hogy C k [p]=C k [q], ám C k+1[p]≠C k+1[q]. Ekkor viszont a 1. Segédtétel alapján van legalább egy olyan k+1 hosszúságú wT * szó, hogy d(p, w)≠d(q, w). (Nevezetesen, minden k+1- nél rövidebb wT * szóra C k [p]=C k [q] miatt f(p, w)=f(q, w), másrészről pedig C k+1[p]≠C k+1[q] miatt van legalább egy olyan k+1- nél nem hosszabb wT * szó, melyre f(p, w)≠f(q, w). A két állítás együttes fennállása azt jelenti, hogy f(p, w)≠f(q, w) legalább egy k+1 hosszú szóra teljesül.)

Be kell még látnunk azt is hogy a kiegészítő megjegyzésünk is korrekt. A fentiek alapján az is igaz, hogy ha az A automata iniciális és kezdőállapota q 0, akkor a redukált automatát is választhatjuk iniciálisnak oly módon, hogy kezdőállapotának a C m [q 0] osztályt választjuk. Ez az osztály is a φ q 0 leképezést fogja a redukált automatában indukálni ugyanúgy, mint ahogy a q 0 a φ q 0 leképezést indukálja A- ban.

Ha egy iniciális A=(Q, T, V, q 0, d, f) véges automatához keressük azt a minimális automatát, mely φ q 0 - t indukálja, először célszerű a Q állapothalmaz Q '={q '∈Q|q '=≫d(q 0, w), wT *} részhalmazát meghatározni, s azután a Q ' állapothalmaz által meghatározott A ' iniciális állapot-részautomatát minimalizálni. Világos ugyanis, hogy ez az A ' iniciális állapot-részautomata ugyancsak a φ q 0 - t indukálja, azaz A- ban a QQ '- beli, azaz az q 0- ból el nem érhető állapotok ugyanis φ q 0 indukálásában nem játszanak szerepet. Jelölje B a A- hoz tartozó iniciális redukált automatát, B ' pedig a A '- höz tartozó iniciális redukált automatát. Világos, hogy B ' ugyanúgy a φ q 0 - t fogja indukálni, mint B. Mivel Q ' részhalmaza a Q- nak, az is világos, hogy a B ' állapothalmaza részhalmaza a B állapothalmazának. Így ha Q' B jelöli a B ', továbbá Q B jelöli a B állapothalmazát, |Q' B | ≤ |Q B |.

Esetleg lehet olyan qQQ ' állapotunk, melyre φ q ∉{φ q '|q'Q '}. Ekkor azonban |Q' B |<|Q B |, vagyis ilyen esetben B nem egy minimális, φ q 0 leképezést indukáló automata. Tehát valóban, egy φ q 0 leképezést indukáló minimális automata keresésénel célszerű először a vizsgált A iniciálisan összefüggő állapot részautomatáját meghatározni, majd az Aufenkamp-Hohn féle algoritmust erre az iniciális állapot részautomatára alkalmazni.

Kérdés még, hogy a Q ' meghatározásához javasolt algoritmusunk korrekt-e. Az világos, hogy minden i ≥ 1- re a Q i halmaz definíció szerint a q 0- ból legfeljebb i hosszúságú szavakkal elérhető állapotok halmaza. Így azt kell csak kimutatnunk, hogy ha egy állapot q 0- ból elérhető, akkor elérhető |Q|-1- nél nem hosszabb bemenő szóval is.

Tetszőleges w, v, uT * esetén ≫d(q 0, w v)=≫d(q 0, w) mellett ≫d(q 0, w v u)=≫d(q 0, w u) nyilván fennáll. Így ha valamely qQ állapothoz van olyan w ' szó, hogy ≫d(q 0, w ')=q, akkor w ' megválaszható úgy, hogy bármely két különböző w '', w '''∈T * kezdőszeletére ≫d(q 0, w '')≠≫d(q 0, w ''') teljesüljön. Ekkor viszont w ' hossza legfeljebb |Q|-1 lehet, különben az ismétlődés elkerülhetetlen. Így megvizsgálva azt, hogy melyek azok az állapotok, melyek elérhetők a kezdőállapotból legfeljebb |Q|-1 hosszú szóval, megkapjuk Q '- t. Az is világos, hogy ha valamely k<|Q|-1- re a q 0- ból legfeljebb k hosszú szóval elérhető állapotok Q k halmaza egybeesik a q 0- ból legfeljebb k+1 hosszú szóval elérhető állapotok halmazával, úgy a q 0- ból elérhető összes állapotok halmaza Q k - val megegyezik. Valóban, ha a legfeljebb k hosszú bemenő szavakkal ugyanazokat az állapotokat érjük el mint a legfeljebb k+1 hosszú szavakkal, akkor minden l ≥ 0- ra a legfeljebb k hosszú hosszú bemenő szavakkal ugyanazokat az állapotokat érjük el mint a legfeljebb k+l, azaz bármilyen hosszú szavakkal. Az Aufenkamp-Hohn-féle minimalizációs algoritmushoz vett kiegészítő megjegyzésünk tehát ugyancsak korrekt. ∎

4.8. példa - Mealy-automata minimalizálása 1.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6},{x,y},{u,v,w},d,f)
Mealy-automatához tartozó A
                  0 minimális állapotszámú automatát! (d és f a következő táblázattal adott):

A a 1 a 2 a 3 a 4 a 5 a 6
x (a 2 ,u) (a 1 ,w) (a 1 ,u) (a 5 ,w) (a 4 ,u) (a 3 ,u)
y (a 3 ,v) (a 2 ,v) (a 4 ,v) (a 4 ,v) (a 3 ,v) (a 2 ,v)


Megoldás:
(I.) A feladat megoldásának első lépéseként különböző osztályokba fogjuk sorolni az
A automata belső állapotait. A kiinduló oszályokban két állapot akkor és csak akkor
esik egy osztályba, ha ugyanarra a bemenő jelre ugyanazzal a kimenőjellel reagálnak.

Jelen esetben:
C
                  1
                  ={a
                  1
                  ,a
                  3
                  ,a
                  5
                  ,a
                  6},{a
                  2
                  ,a
                  4}.
Ezek után a C
                  
                     i+1
-edik osztályozás esetén két állapot akkor esik egy
osztályba, ha egyrészt a Ci
                  
-edik osztályozás esetén is azonos
osztályba tartoztak, másrészt pedig minden bemenő jel hatására azonos
Ci
                  
-beli osztályban található állapotokba mennek át. Az osztályozás
véget ér, amennyiben Ci
                  
=C
                  
                     i+1
 valamely i ≥ 1 esetén.

Jelen esetben:
C
                  2
                  ={a
                  1
                  ,a
                  5},{a
                  3
                  ,a
                  6},{a
                  2
                  ,a
                  4}.
C
                  3
                  ={a
                  1
                  ,a
                  5},{a
                  3},{a
                  6},{a
                  2
                  ,a
                  4}.
C
                  4
                  ={a
                  1
                  ,a
                  5},{a
                  3},{a
                  6},{a
                  2
                  ,a
                  4}.
Mivel C
                  3
                  =C
                  4, ezért az osztályozás véget ért. A C3 osztályait
jelöljük valamely új betűvel, például b-vel:
b
                  1
                  ={a
                  1
                  ,a
                  5},b
                  2
                  ={a
                  3},b
                  3
                  ={a
                  6},b
                  4
                  ={a
                  2
                  ,a
                  4}.
(II.) Készítsük el az A automatával ekvivalens, minimális állapotszámú A
                  0 automatát,
mely állapothalmazát az osztályozás és az új jelölés bevezetése után kapott bi
                  
 betűk alkotják,
- a bemenő- és kimenőjeleinek halmaza megegyezik az A automata megfelelő jeleinek halmazával,
- az átmenetfüggvényét megkapjuk úgy, hogy megnézzük, hogy az adott bi
                  
 osztálybeli állapotok
az adott bemenő jel hatására mely bj
                  
 osztálybeli állapotokba mentek át az A automata esetén
- és végül az aktuális bi
                  
 osztályhoz tartozó kimenőjelet megkapjuk, ha megnézzük,
hogy az adott bi
                  
 osztálybeli állapotok az adott bemenő jel hatására mely
kimenőjelet szolgáltatták az A automata működése közben.
Jelen esetben:
A
                  0=({b
                  1
                  ,b
                  2
                  ,b
                  3
                  ,b
                  4},{x,y},(u,v,w),d',f'). Ahol d ' és f ' a következő táblázattal adott:
 

A 0 b 1 b 2 b 3 b 4
x (b 4 ,u) (b 1 ,u) (b 2 ,u) (b 1 ,w)
y (b 2 ,v) (b 4 ,v) (b 4 ,v) (b 4 ,v)


4.9. példa - Mealy-automata minimalizálása 2.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6
                  ,a
                  7},{x,y},{u,v,w},d,f)
Mealy-automatához tartozó A
                  0 minimális állapotszámú automatát!
Ahol d és f a következő táblázattal adott:

A a 1 a 2 a 3 a 4 a 5 a 6 a 7
x (a 2 ,w) (a 3 ,w) (a 2 ,w) (a 7 ,w) (a 6 ,w) (a 5 ,w) (a 4 ,w)
y (a 4 ,u) (a 2 ,v) (a 4 ,u) (a 2 ,v) (a 4 ,u) (a 5 ,v) (a 2 ,u)


Megoldás:
(I.)
C
                  1
                  ={a
                  1
                  ,a
                  3
                  ,a
                  5
                  ,a
                  7},{a
                  2
                  ,a
                  4
                  ,a
                  6}.
C
                  2
                  ={a
                  1
                  ,a
                  3
                  ,a
                  5
                  ,a
                  7},{a
                  2
                  ,a
                  4},{a
                  6}.
C
                  3
                  ={a
                  1
                  ,a
                  3
                  ,a
                  7},{a
                  5},{a
                  2
                  ,a
                  4},{a
                  6}.
C
                  4
                  ={a
                  1
                  ,a
                  3
                  ,a
                  7},{a
                  5},{a
                  2
                  ,a
                  4},{a
                  6}.
b
                  1
                  ={a
                  1
                  ,a
                  3
                  ,a
                  7},b
                  2
                  ={a
                  5},b
                  3
                  ={a
                  2
                  ,a
                  4},b
                  4
                  ={a
                  6}.
(II.)
A
                  0=({b
                  1
                  ,b
                  2
                  ,b
                  3
                  ,b
                  4},{x,y},(u,v,w),d',f').
Ahol d ' és f ' a következő táblázattal adott:
 

A 0 b 1 b 2 b 3 b 4
x (b 3 ,w) (b 4 ,w) (b 1 ,w) (b 2 ,w)
y (b 3 ,u) (b 3 ,u) (b 3 ,v) (b 2 ,v)


4.10. példa - Mealy-automata minimalizálása 3.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5},{x,y,z},{u,v},d,f)
Mealy-automatához tartozó A
                  0 minimális állapotszámú automatát!

A a 1 a 2 a 3 a 4 a 5
x (a 2 ,u) (a 2 ,v) (a 2 ,u) (a 5 ,v) (a 4 ,v)
y (a 4 ,u) (a 3 ,u) (a 1 ,u) (a 3 ,u) (a 3 ,u)
z (a 5 ,v) (a 5 ,u) (a 1 ,v) (a 5 ,u) (a 2 ,u)


Megoldás:
(I.)
C
                  1
                  ={a
                  1
                  ,a
                  3},{a
                  2
                  ,a
                  4
                  ,a
                  5}.
C
                  2
                  ={a
                  1},{a
                  3},{a
                  2
                  ,a
                  4,a
                  5}.
C
                  3
                  ={a
                  1},{a
                  3},{a
                  2
                  ,a
                  4,a
                  5}.
b
                  1
                  ={a
                  1},b
                  2
                  ={a
                  3},b
                  3
                  ={a
                  2
                  ,a
                  4
                  ,a
                  5}.
(II.)
A
                  0=({b
                  1
                  ,b
                  2
                  ,b
                  3},{x,y,z},(u,v),d',f').
 

A 0 b 1 b 2 b 3
x (b 3 ,u) (b 3 ,u) (b 3 ,v)
y (b 3 ,u) (b 1 ,u) (b 2 ,u)
z (b 3 ,v) (b 1 ,v) (b 3 ,u)


4.11. példa - Mealy-automata minimalizálása 4.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6
                  ,a
                  7
                  ,a
                  8},{x,y},{u,v},d,f)
Mealy-automatához tartozó A
                  0 minimális állapotszámú automatát!

A a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8
x (a 8 ,u) (a 3 ,v) (a 8 ,u) (a 1 ,v) (a 8 ,u) (a 4 ,u) (a 3 ,v) (a 5 ,v)
y (a 2 ,v) (a 1 ,u) (a 7 ,u) (a 2 ,v) (a 7 ,v) (a 2 ,v) (a 6 ,u) (a 3 ,v)


Megoldás:
(I.)
C
                  1
                  ={a
                  1
                  ,a
                  5
                  ,a
                  6},{a
                  2
                  ,a
                  7},{a
                  3},{a
                  4
                  ,a
                  8}.
C
                  2
                  ={a
                  1
                  ,a
                  5
                  ,a
                  6},{a
                  2
                  ,a
                  7},{a
                  3},{a
                  4},{a
                  8}.
C
                  3
                  ={a
                  1
                  ,a
                  5},{a
                  6},{a
                  2
                  ,a
                  7},{a
                  3},{a
                  4},{a
                  8}.
C
                  4
                  ={a
                  1
                  ,a
                  5},{a
                  6},{a
                  2},{a
                  7},{a
                  3},{a
                  4},{a
                  8}.
C
                  5
                  ={a
                  1},{a
                  5},{a
                  6},{a
                  2},{a
                  7},{a
                  3},{a
                  4},{a
                  8}.                            
Ebben az esetben - mivel a C
                  5 osztályozás esetén minden ai
                  
 állapot külön osztályba esik, -
az A automata már minimális, így tovább nem minimalizálható, azaz A
                  0=A. ★


4.5.3. Aufenkamp-Hohn féle minimalizációs algoritmus Moore-automatákhoz adaptált változata

Megjegyezzük először, hogy ha egy Moore-automatát Mealy-automatának tekintünk, s minimalizáljuk, az eredmény nem feltétlenül lesz Moore-féle automata (lásd Mealy és Moore automaták homomorfizmusa). Ha az A=(Q, T, V, d, g) Moore-automatához azt a minimális állapotszámú Moore-féle automatát akarjuk meghatározni, mely ugyanazt a leképezési családot indukálja, mint az eredeti Moore-automata, akkor az Aufenkamp-Hohn féle algoritmust egy kicsit módosítanunk kell.

Egy véges A=(Q, T, V, d, g) Moore-automata esetén az A 0 redukált Moore-automatához úgy jutunk el, hogy definiálunk egy kongruencia relációt a következőképpen:

p, qQ:(p ρ A q⇔∀a 1, …, a n T:g(p 1⋅⋅⋅p n )=g(q 1⋅⋅⋅q n )),

p 1=d(p, a 1), p 2=d(p 1, a 2), …, p n =d(p n-1, a n ),

q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n =d(q n-1, a n )

(azaz minden p, qQ pár esetén p ρ A q akkor és csak akkor, ha g(p 1⋅⋅⋅p n )=g(q 1⋅⋅⋅q n ) fennáll minden olyan p 1, …, p n , q 1, …, q n Q esetén, melyekre p 1=d(p, a 1), p 2=d(p 1, a 2), …, p n =d(p n-1, a n ), q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n =d(q n-1, a n ) fennáll valamely a 1, …, a n T bemenő jelek esetén).

Ekkor a ρ A relációhoz tartozó C A osztályozást osztályozások egy C 1, C 2, … sorozatán keresztül szerkesztjük meg, melyeket a következőképp definiálunk:

(i) ∀p, qQ:(C 1[p]=C 1[q]⇔∀aT:g(p)=g(q))

(azaz minden p, qQ párra a C 1 osztályozás szerint p és q akkor és csak akkor esnek egy osztályba, ha ugyanaz az állapotjelük);

(i i) ha i ≥ 1C i+1[p]=C i+1[q]⇔C i [p]=C i [q]∀aT:C i [d(p, a)]=C i [d(q, a)].

(Azaz ha i ≥ 1, akkor amint a Mealy-automatáknál, a C i+1 osztályozás szerint p és q akkor és csak akkor esnek egy osztályba, ha egyrészt már C i szerint is egy osztályba esnek, másrészt pedig minden bemenő jel hatására egy és ugyanazon C i szerinti osztályba mennek át.)

A továbbiakban formailag a Moore-automatákra adaptált Aufenkamp-Hohn féle eljárás csaknem teljesen megegyezik a Mealy-automatáknál tárgyaltakkal. Először megszerkesztjük a Q állapothalmaz C 1 szerinti osztályait, mikoris pontosan akkor tartozik két állapot egy osztályba, amikor ugyanaz az állapotjelük. (Lásd (i) pont, fentebb.) Ezután minden egyes m>1- re megszerkesztjük a C m szerinti osztályokat egészen addig, míg C m =C m+1 teljesül. Ugyanúgy mint Mealy-automaták esetén, ilyen m létezik, s nagysága legfeljebb |Q|-1. Ez a C m osztályozás épp a Q (Moore-változatú) maximális kompatibilis osztályozása. Ezután a Moore-féle redukált automata megszerkesztése van csak hátra, melynek szerkezete AC m =(C m , T, V, d C m , g C m ), aholis minden C m [q]∈C m , aT- re d C m (C m [q], a)=C m [d(q, a)], illetve g C m (C m [q])=g(q). Speciálisan, ha az eredeti automata iniciális volt, és a kezdő állapota q 0 volt, akkor a redukált automata is választható iniciálisnak, éspedig úgy, hogy a kezdőállapotát C m [q 0]- nak választjuk.

4.5.4. Kiegészítés az Aufenkamp-Hohn-féle minimalizációs algoritmus Moore-automatákhoz adaptált változatához

Ha a célunk nem az automatához tartozó (redukált) minimális állapotszámú Moore-automata, hanem csupán az a φ q 0 - t indukáló minimális iniciális Moore-automata meghatározása, akkor ehhez az A=(Q, T, V, q 0, d, g) minimalizálandó automata helyett annak a kezdőállapotból elérhető állapotok által meghatározott, azaz a Q '={≫d(q 0, w)|wT *} állapothalmazzal rendelkező A=(Q ', T, V, q 0, d ', g ') iniciálisan összefüggő állapot-részautomatáját minimalizáljuk. A q 0- ból el nem érhető állapotok ugyanis nem játszanak szerepet a φ q 0 leképezés indukálásában (az összes q 0- ból elérhető állapot viszont igen). Mivel A végessége miatt ekkor a kezdőállapotból csak azok az állapotok érhetők el, melyek legfeljebb |Q|-1 hosszúságú szavakkal elérhetők, a Q állapothalmaz Q ' részhalmaza algoritmikusan meghatározható. Erre ugyanaz a módszer kínálkozik mint Mealy-automaták esetén: Legyen először Q 0={q 0}. Ezután minden i ≥ 1- re legyen Q i+1={q|∃q '∈Q i , aT:d(q ', a)=q}. Ha valamely i ≥ 1- re elérjük, hogy Q i =Q i+1, akkor Q '=Q i . Nyilván az ilyen i- re i ≤ |Q|-1 teljesül.

4.12. példa - Moore-automata minimalizálása 1.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6},{x,y},{u,v,w},d,g)
Moore-automatához tartozó A
                  0 minimális állapotszámú automatát!
d és g függvények a következő táblázattal adottak:

  u v u u w w
A a 1 a 2 a 3 a 4 a 5 a 6
x a 4 a 1 a 4 a 1 a 1 a 3
y a 1 a 3 a 6 a 4 a 6 a 5


Megoldás:
(I.) A feladat megoldásának első lépéseként különböző osztályokba fogjuk sorolni az
A automata belső állapotait. A kiinduló oszályokban két állapot akkor és csak akkor
esik egy osztályba, ha ugyanarra a bemenő jelre ugyanazzal a kimenőjellel reagálnak.

Jelen esetben:
C
                  1
                  ={a
                  1
                  ,a
                  3
                  ,a
                  4},{a
                  2},{a
                  5
                  ,a
                  6}.
Ezek után a C
                  
                     i+1
-edik osztályozás esetén két állapot akkor esik egy
osztályba, ha egyrészt a Ci
                  
-edik osztályozás esetén is azonos
osztályba tartoztak, másrészt pedig minden bemenő jel hatására azonos
Ci
                  
-beli osztályban található állapotokba mennek át. Az osztályozás
véget ér, amennyiben C
                  
                     i
                  
=C
                  
                     i+1
 valamely i ≥ 1 esetén.

Jelen esetben:
C
                  2
                  ={a
                  1
                  ,a
                  4},{a
                  2},{a
                  3},{a
                  5
                  ,a
                  6}.
C
                  3
                  ={a
                  1
                  ,a
                  4},{a
                  2},{a
                  3},{a
                  5},{a
                  6}.
C
                  4
                  ={a
                  1
                  ,a
                  4},{a
                  2},{a
                  3},{a
                  5},{a
                  6}.
Mivel C
                  3
                  =C
                  4, ezért az osztályozás véget ért. A C
                  3 osztályait
jelöljük valamely új betűvel, például b-vel:
b
                  1
                  ={a
                  1
                  ,a
                  4},b
                  2
                  ={a
                  2},b
                  3
                  ={a
                  3},b
                  4
                  ={a
                  5},b
                  5
                  ={a
                  6}.
(II.) Készítsük el az A automatával ekvivalens, minimális állapotszámú A
                  0 automatát,
mely állapothalmazát az osztályozás és az új jelölés bevezetése után kapott bi
                  
 betűk alkotják,
- a bemenő- és kimenőjeleinek halmaza megegyezik az A automata megfelelő jeleinek halmazával,
- az átmenetfüggvényét megkapjuk úgy, hogy megnézzük, hogy az adott bi
                  
 osztálybeli állapotok
az adott bemenő jel hatására mely bj
                  
 osztálybeli állapotokba mentek át az A automata esetén
- és végül az aktuális bi
                  
 osztályhoz tartozó kimenőjelet megkapjuk, ha megnézzük,
hogy az adott bi
                  
 osztálybeli állapotok az adott bemenő jel hatására mely
kimenőjelet szolgáltatták az A automata működése közben.
Jelen esetben:
A
                  0=({b
                  1
                  ,b
                  2
                  ,b
                  3
                  ,b
                  4
                  ,b
                  5},{x,y},(u,v,w),d',g').
Táblázattal:
 

  u v u w w
A 0 b 1 b 2 b 3 b 4 b 5
x b 1 b 1 b 1 b 1 b 3
y b 1 b 3 b 5 b 5 b 4


4.13. példa - Moore-automata minimalizálása 2.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5},{x,y},{u,v},d,g)
Moore-automatához tartozó A
                  0 minimális állapotszámú automatát!

  u v v u u
A a 1 a 2 a 3 a 4 a 5
x a 2 a 4 a 4 a 2 a 3
y a 5 a 3 a 2 a 3 a 1


Megoldás:
(I.)
C
                  1
                  ={a
                  1
                  ,a
                  4
                  ,a
                  5},{a
                  2
                  ,a
                  3}.
C
                  2
                  ={a
                  1
                  ,a
                  5},{a
                  4},{a
                  2
                  ,a
                  3}.
C
                  3
                  ={a
                  1
                  ,a
                  5},{a
                  4},{a
                  2
                  ,a
                  3}.
b
                  1
                  ={a
                  1
                  ,a
                  5},b
                  2
                  ={a
                  4},b
                  3
                  ={a
                  2
                  ,a
                  3}.
(II.)
A
                  0=({b
                  1
                  ,b
                  2
                  ,b
                  3},{x,y},(u,v),d',g').
Ahol d ' és g ' a következő táblázattal adott:
 

  u u v
A 0 b 1 b 2 b 3
x b 3 b 3 b 2
y b 1 b 3 b 3


4.14. példa - Moore-automata minimalizálása 3.feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével az
A=({a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5},{x,y,z},{u,v,w},d,g)
Moore-automatához tartozó A
                  0 minimális állapotszámú automatát!

  u v v w w
A a 1 a 2 a 3 a 4 a 5
x a 2 a 4 a 4 a 2 a 3
y a 5 a 4 a 5 a 3 a 3
z a 1 a 3 a 2 a 5 a 4


Megoldás:
(I.)
C
                  1
                  ={a
                  1},{a
                  2
                  ,a
                  3},{a
                  4
                  ,a
                  5}.
C
                  2
                  ={a
                  1},{a
                  2
                  ,a
                  3},{a
                  4
                  ,a
                  5}.
b
                  1
                  ={a
                  1},b
                  2
                  ={a
                  2
                  ,a
                  3},b
                  3
                  ={a
                  4
                  ,a
                  5}.
(II.)
A
                  0=({b
                  1
                  ,b
                  2
                  ,b
                  3},{x,y,z},(u,v,w),d',g').
 

  u v w
A 0 b 1 b 2 b 3
x b 2 b 3 b 2
y b 3 b 3 b 2
z b 1 b 2 b 3


4.5.5. Minimalizációs algoritmus kimenőjel nélküli automatákra

Tetszőleges A=(Q, T, d) kimenőjel nélküli automata esetén valamely qQ állapot és nem üres w bemenő szó esetén a kimenő szót d(q, w)- vel azonosítottuk. Ha a bemenő szó az üresszó, akkor viszont kimenő szónak ugyancsak az üresszót tekintettük minden állapotra vonatkozóan, mint a Mealy-automatáknál.

Ezek szerint egy egymástól különböző p, qQ állapotpár nem tartozhat egy osztályba, ha valamely (nem feltétlen különböző) r, sQ állapotpárra és a, bT bemenő jelekre d(r, a)=p és d(s, b)=q. Másképp mondva, két p, qQ állapot csak úgy tartozhat egy osztályba, ha egyrészt minden aT- re d(p, a)=d(q, a), másrészt legalább egy r∈{p, q}- ra akárhogy is adjuk meg az sQ, aT párt, d(s, a)≠r.

Így az Aufenkamp-Hohn féle minimalizációs algoritmus helyett kimenőjel nélküli automatákra a következő algoritmust alkalmazzuk:

Egy véges A=(Q, T, d) kimenőjel nélküli automata esetén az A 0 redukált kimenőjel nélküli automatához is úgy jutunk el, hogy először képezzük a Q egy olyan Q 0 részhalmazát, mely tartalmaz minden olyan qQ állapotot, melyhez van olyan pQ, aT, hogy d(p, a)=q. Vezessük be továbbá a C 0=QQ 0 jelölést. Mindaddig, míg valamely i ≥ 0- ra C i üres nem lesz, hajtsuk végre a következő algoritmust:

Tegyük fel, hogy valamely i ≥ 0- ra Q i és C i adottak. Legyen valamely tetszőlegesen rögzített rC i - re Q i+1=Q i ∪{r}. Eután C i+1- t C i - ből úgy képezzük, hogy C i elemei közül elhagyunk minden olyan r '∈C i elemet, melyhez van olyan pQ i+1, hogy tetszőleges aT mellett d(r ', a)=d(p, a). Ha C i+1=∅, akkor készen vagyunk, különben növeljük eggyel i értékét, s ismételjük meg az előző lépést.

Világos, hogy Q végessége miatt ez az eljárás véges lépésben valamely i ≥ 0- ra véget ér, s az is könnyen igazolható, hogy a fenti algoritmus végén minden qQ- hoz tartozik pontosan egy olyan pQ i+1, hogy tetszőleges aT mellett d(q, a)=d(p, a). Ekkor megkapjuk a B=(Q ', T, d ') kimenőjel nélküli automatát, ahol Q '=Q i+1 és d '=d| Q '×T mellett B olyan (kimenőjel nélküli) állapot részautomatája lesz A- nak, hogy minden qQ- hoz található olyan pQ ', hogy tetszőleges aT mellett d(q, a)=d(p, a). Ez a B kimenőjel nélküli automata lesz az A kimenőjel nélküli automatához tartozó redukált automata.

4.5.6. Kiegészítés a minimalizációs algoritmus kimenőjel nélküli automatákra ismertetett változatához

Ha a célunk nem a kimenőjel nélküli automatához tartozó (redukált) minimális állapotszámú kimenőjel nélküli automata, hanem csupán az a φ q 0 - t indukáló minimális iniciális kimenőjel nélküli automata meghatározása, akkor ehhez az A=(Q, T, q 0, d) minimalizálandó kimenőjel nélküli automata helyett annak a kezdő állapotból elérhető állapotok által meghatározott, azaz a Q '={≫d(q 0, w)|wT *} állapothalmazzal rendelkező A=(Q ', T, q 0, d ') iniciálisan összefüggő (kimenőjel nélküli) állapot-részautomatáját minimalizáljuk. A q 0- ból el nem érhető állapotok ugyanis most sem játszanak szerepet a φ q 0 leképezés indukálásában (az összes q 0- ból elérhető állapotok viszont igen). Mivel A végessége miatt ekkor a kezdőállapotból csak azok az állapotok érhetők el, melyek legfeljebb |Q|-1 hosszúságú szavakkal elérhetők, a Q állapothalmaz Q ' részhalmaza algoritmikusan meghatározható. Erre itt is a következő módszer kínálkozik: Legyen először Q 0={q 0}. Ezután minden i ≥ 1- re legyen Q i+1={q|∃q '∈Q i , aT:d(q ', a)=q}. Ha valamely i ≥ 1- re elérjük, hogy Q i =Q i+1, akkor Q '=Q i . Nyilván az ilyen i- re i ≤ |Q|-1 teljesül. A q 0- ból elérhető minden q '∈Q ' állapot nyilván rendelkezik azzal a tulajdonsággal, hogy alkalmas pQ ', aT párra d(p, a)=q '. Így ha q 0 is elérhető önmagából, akkor A ' egy minimális, φ q 0 - t indukáló automata lesz. Ugyancsak az lesz, ha minden qQ '∖{q 0} esetén van olyan aT, melyre d(q 0, a)≠d(q, a). Ellenkező esetben valamely qQ '- re d(q, a)=d(q 0, a) minden aT- re fennáll, továbbá tetszőleges (az üresszótól különböző) wT + bemenő szó esetén d(q 0, w)≠z q 0 semmilyen zQ * esetén sem. Ha van olyan wT + (üresszótól különböző) bemenő szó, hogy d(q, w)=z q valamely zQ *- ra, akkor világos, hogy A ' ismét redukált automata lesz. Ellenkező esetben amellett, hogy az q, q 0Q párra d(q, a)=d(q 0, a), aT fennáll, {≫d(q 0, w)|wT +}∩{q 0, q}=∅ és {≫d(q, w)|wT +}∩{q 0, q}=∅ is teljesül. Világos hogy ebben az esetben a d ''(p, a)=d(p, a), pQ '∖{q 0}, aT átmeneti függvénnyel definiált B=(Q '∖{q 0}, T, q, d '') egy olyan minimális állapotszámú iniciális kimenőjel nélküli automata lesz, melynek qQ '∖{q 0} kezdőállapota pont φ q 0 - t indukálja.

Csak megemlítjük itt, hogy hasonló módszerrel minimalizálhatóak a Rabin-Scott (felismerő-) automaták is (részleteket lásd Véges determinisztikus elfogadó automaták minimalizálása fejezetben). Ezesetben, az Aufenkamp-Hohn algoritmus első osztályozó lépésében két csoportot képzünk, mégpedig a végállapotok, illetve a többi állapot halmazát.