Minimiziranje stanj končnega avtomata

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Problem: zapisati končni avtomat z minimalnim številom stanj (in povezav med njimi)


Vsebina

Metode:

1.)Implikacijska tabela

2.)Moore-ov redukcijski postopek

3.)KA minimalizacijski algoritem


Implikacijska tabela


Koncept implikacijske tabeli sloni na začetnih predpostavkah, da je vsako stanje povezano z vsakim drugim stanj, nakar sledi eliminacija za dani problem neustreznih povezav. Ko nam v tem postopku ostanejo samo še stanja, ki ustrezajo problemu, se le ta povežejo v optimalni končni avtomat.

Postopek:

1. Zapis vseh moznih kombinacij v implikacijsko tabelo

2. Eliminacija neustreznih stanj, ki niso v skladu z konkretnim problem oziroma dajo napačen izhod

3. Eliminacija vseh možnosti, ki se pojavijo kot kombinacija stanj slonečih na ekvivalenci prejšnih eliminiranih možnosti

4. Ponovitev zgornjega postopka dokler ne moremo odstraniti nobene neustrezne možnosti več


Moore-ov redukcijski postopek

Koncept je podoben kot pri eliminacijski tabeli. V začetku predpostaviš, da obstajajo povezave med vsemi možnimi stanji, nato pa jih ločiš v razlikujoča se stanja imenovana ekvivalenčni razredi. Ko noben ekvivalenčni razred ne vsebuje več razlikujočih si stanj, se lahko stanja v istem ekvivalenčnem razredu povežejo. Ekvivalenčni razredi so označeni s številom korakov potrebnih, da pridemo do zaželjenega stanja. 0-ti razred vsebuje vsa stanja v eni skupini, prva particija pa vsa stanja povezana v skupino samo na podlagi njihovih izhodov. Vsak nadalnji razred je osnovan na podlagi dejstva v katero skupino se povezujejo stanja iz prejšnjega razreda. Postopek je končan ko je n-ti razred enak n+1 - em razredu.

Stanja, ki se razlikujejo v k-tem razredu imenujemo k-različna stanja. Stanja, ki so v isti skupini v k-tem razredu se imenujejo k-ekvivalentna stanja. Velja, da stanja, ki so k-ekvivalentna v nekem koraku ne predstvljajo nujno ekvivalentnih stanj, saj je moćno, da jih lahko ločimo v različne skupine v kasnejšem razredu.

Postopek:

1. Ločitev stanj v skupine, ki dajo isti izhodni podatek za isti vhodni podatek

2. Razlikovanje stanj, katerih naslednji izhodni podatki ležijo v raličnih skupinah

3. Ponovna ločitev stanj in ponovitev zgornjega postopka dokler ni nič več razlikujočih si stanj


KA algoritmi

1.) KA dno-vrh algoritem

2.) KA vrh-dno algoritem


KA dno-vrh algoritem za aciklične končne avtomate

Postopek:

1.) Najdemo vsa stanja brez izhodnih povezav ( ker velja, da gre za aciklični končni avtomat, taka stanja vedno obstajajo)

2.) Ločimo slednjo skupino v eno ali dve skupini, sloneč na podlagi kočnega statusa ( če so v skupini samo končna stanja ali če nobeno od stanj ni končno, dobimo samo eno skupino). Združimo obe (ali samo eno) skupino v dve (eno) novi stanji, vse ustrezne povezave ustrezno ponovno povežemo. Slednji skupini rečemo (eno ali dvoelementna množica) procesirana.

Glavna zanka (nadaljuj dokler ni doseženo ustrezno končno stanje):

1.) Najdemo vse prednike procesiranih stanj, vse povezave, katerih povezave vodijo samo do stanj, ki so že bila procesirana (brez pomembnosti "kako daleč nazaj"). Dobljeno skupino imenujemo kandidati.

2.) Če je kandidatska skupina prazna, izpišemo dobljeni KA in se ustavimo. Postopek je končan.

3.) Če pa ni prazna, združimo skupaj podskupine kandidatskih stanj, ki imajo isti končni status (vsa so bodisi končna ali ne-končna) in ki imajo hkrati skupne vse izhodne povezave ( npr., njihova stanja kažejo na ista stanja in z istimi povezavami). [ Nekatere podskupine so lahko velikosti 1, t.j. nekatera stanja ne morejo biti povezana z nobenimi drugimi stanji iz kandidatske skupine razen "sami s sabo".]

4.) Povežemo stanja v vseh zgornjih podskupinah, ponovno ustrezno povežemo povezave. [ Za podskupine velikosti 1 očitno to ni potrebno, vendar gledamo nanje kot na združene tudi.]

5.) Dobljeno skupino združenih procesiranih stanj ( vključno s tistimi katerih velikost podskupin je 1 ali trivialnih združitev pri katerih ni bil potreben noben postopek) in ponovimo glavno zanko.

Primer (dno-vrh algoritem)

Vhodni KA

Slika:Fsa1.jpg

Končna stanja so zelene barve (2,3,5,8,9). Vhodna simbola sta le a in b. Vse besede, ki jih dani KA prepozna: a,b,bb,bbba,bbbb,baaa,baab,ab,abba,abbb,aaaa,aaab.

Začetni korak

Stanja brez izhodnih povezav, povezana glede na končni status: Končna: {8,9} Ne-Končna: {10} Pokličemo dve novi stanji "9"(za {8,9}) in "10"(za {10}). Procesirana skupina vsebuje {9,10}. Končni avtomat po združitvi:

Slika:Fsa2.jpg

Glavna zanka

Prva ponovitev

Procesirani: {9,10} Kandidati: {6,7}( vendar ne 5, saj ni nobene povezave od 5 do 7 in stanje številka 7 še ni bilo procesirano)

Zdaj je kandidatska skupina združena v eno samo stanje (recimo mu "6"), saj je vzorec izhodnih povezav iz 6 in 7 isti. KA po združitvi ( stanja, ki niso bila procesirana v preteklosti, imajo odebeljen rob):

Slika:Fsa3.jpg

Druga ponovitev:

Procesirani: {6} (samo stanje 6 -- stanje združeno v prejšnji ponovitvi--; 9 in 10 nosita oznako "procesirana v preteklosti", vendar je nepotrebno ponovno jih vključiti v procesirano skupino) Kandidati: {4,5} (zdaj je tud 5 kandidat, ker sta bila tako 10 kot 6 procesirana v preteklosti)

Stanji 4 in 5 (kandidata) ne moreta biti združena ( ne samo da 4 nima nobenega izhodnega loka označenega z b, temveč je tudi 5 končno, kjer 4 to ni). Morata ostati ločeni (ohranimo njuna imena, "4" in "5"). KA po združitvi:

Slika:Fsa4.jpg

Tretja ponovitev:

Procesirani: {4,5} Kandidati: {2,3}

Stanji 2 in 3 sta lahko združeni ( npr. v "2"): obe povezavi označeni z a gresta v stanje 4, obe povezavi označeni z b gresta v stanje 5. KA po združitvi:

Slika:Fsa5.jpg

Četrta ponovitev:

Procesirani: {2} Kandidati: {1}

Nobena združitev ni možna, vendar kljub temu jemljemo "1" kot združeno stanje. KA po združitvi:

Slika:Fsa6.jpg

Peta ponovitev:

Procesirani: {1} Kandidati: {} \Rightarrow Postopek je končan!


KA vrh-dno algoritem za (splošne) KA

Ta algoritem deluje za splošne KA (to je, z zankami). Če je vhod zagotovo acikličen, potem mora biti vzeto v obzir: vrh-dno verzija algoritma potrebuje [linerno] manj spomina kot dno-vrh algoritem, vendar je možno, da je proces mnogo daljši, razen če "delitev izhodnih povezav" testirano na razdelitvah ni implementirano na pameten način.

Postopek:

1.) Ločimo vsa stanja vhodnega KA v dve skupini glede na njihov končni status: ena skupina vsebuje vsa končna stanja in druga vse ostala (ne glede na to, če obstajajo kakšne izhodne povezave iz njih). Če je kakšna skupina prazna, jo lahko zavržemo. [ Če je zavržena skupina, skupina končnh stanj, potem minimaliziran KA sestoji samo iz ne-končnih začetnih stanj. Ne preveč zanimiv KA!]

2.) Imenujemo dobljeno zbirko stanj EQUISET ( le ta definira ekvivalenčno relacijo na skupini vseh stanj KA). Imenujemo element EQUISET-a (t.j., (pod)skupino stanj) CLASS (razred stanj).

Glavna zanka (jo izvajamo dokler terminacijski status znotraj zanke ni dosežen):

1.) Za vsak CLASS ( iz EQUISET-a), ločimo CLASS (t.j., skupino stanj) naprej v eno ali več podskupin stanj, takih da stanja v isti podskupini delijo vse izhodne povezave (t.j., njihove povezave kažejo na isti CLASS (ne stanja) uporabljeno z istim simbolom na povezavi).[ To je lahko zelo počasen del algoritma, če implementacija ni opremljena z "pospešujočimi" tehnikami.]

2.) Če noben CLASS ne more biti razdeljen v nadalnje, izpišemo dobljeni KA ( ohranjajoč samo predstavnika vsakega CLASS in ustrezno odstranimo povezave) ter se ustavimo. Postopek je končan.

3.) V nasprotnem primeru ( vsaj en CLASS je bil razdeljen v dve ali več podskupini) ustvarimo nov EQUISET, ki vsebuje vse nove CLASS, kot rezultat razdelitev. [Tako se število CLASS v EQUISET-u stalno povečuje.]

4.)Glavno zanko ponovimo.

Primer (vrh-dno algoritem)

Vhodni KA

Slika:Fsa1.jpg

Končna stanja so zelene barve (2,3,5,8,9). Vhodna simbola sta le a in b. Vse besede, ki jih dani KA prepozna: a,b,bb,bbba,bbbb,baaa,baab,ab,abba,abbb,aaaa,aaab.

Začetni korak

Začetna ločitev:{2,3,5,8,9}(končna stanja, C1), {1,4,6,7,10} (ne-končna, C2).

Glavna zanka

Prva ponovitev

Tranzicijska tabela: (orig.stanj)x(simbol) \rightarrow CLASS (za C1):

orig.stanje: 2 3 5 8 9
a C1 C2 C2 - -
b C1 C2 C2 - -


Ločitev C1 v:{2,3} (novo ime za naslednjo ponovitev: c1), {5} (C2) in {8,9}(C3). Tranzicijska tabela: (orig.stanje)x(simbol) -> CLASS (za C2):

orig.stanje: 1 4 6 7 10
a C1 C2 C1 C1 -
b C1 - C1 C1 -


Razdelitev C2 v: {1,6,7} (novo ime za naslednjo ponovitev: C4), {4}(C5) in {10}(C6).

Druga ponovitev

Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C1):

orig.stanje: 2 3
a C5 C5
b C2 C2

Nobena nadalnja razdelitev ni mogoča (zaželjeno stanje). Dobi ime C1 (ponovno). [Čeprav nobena ločitev ni mogoča se lahko CLASS razdeli v prihodnosti, če se kateri od CLASS na drugem koncu izhodnih povezav razdeli.]

Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C2):

orig.stanje: 5
a C6
b C4


Očitno, katerikoli CLASS, ki vsebuje samo eno stanje, lahko pustimo pri miru do nalnjega, samo ime se mu spremeni: C2 ({5}; ne povsem "nov" v tem primeru, vendar ...)

Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C3):

orig.stanje: 8 9
a - -
b - -


Nobena nadaljnja razdelitev ni mogoča. Ime za naslednjo ponovitev: C3 ({8,9}).

Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C4):

orig.stanje: 1 6 7
a C1 C3 C3
b C1 C3 C3


Razdelitev C4 v: {1} (novo ime za naslednjo ponovitev: C4), {6,7}(C5). Ker C5 in C6 že vsebujeta samo eno stanje ({4}in {10}), jima priredimo samo novo ime za naslednjo ponovitev: C5 -> C6 ({4}), C6 ->C7 ({10}).

Tretja ponovitev

Prikazane so tabele z vsaj dvema stolpcema: Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C1):

orig.stanje: 2 3
a C6 C6
b C2 C2

Nobena nadalnja razdelitev ni mogoča. Ime za naslednjo ponovitev: C1.

Tranzicijska tabela za C2 ni prikazana (samo eno stanje:{5}). Novo ime: C2. Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C3):

orig.stanje: 8 9
a - -
b - -

Nobena nadaljnja razdelitev ni mogoča. Ime za naslednjo ponovitev: C3. Tranzicijska tabela za C4 ni prikazana (samo eno stanje:{1}). Novo ime: C4. Tranzicijska tabela: (orig.stanje) x (simbol) \rightarrow CLASS (za C5):

orig.stanje: 6 7
a C3 C3
b C3 C3

Nobena nadaljnja razdelitev ni mogoča. Tranzicijska tabela za C6 ni prikazana (samo eno stanje:{4}). Novo ime: C6. Tranzicijska tabela za C7 ni prikazana (samo eno stanje:{10}). Novo ime: C7.

Noben CLASS se ni razdelitev med to ponovitvijo - končni status je dosežen. Izpišemo dobljeni KA, izberemo eno od stanj v skupinah {2,3},{6,7} in {8,9} kot reprezentativno stanje CLASS. Izpustimo povezave, ki ne kažejo nikamor (potem ko so bila stanja izbrisana).

Ali alternativno; razumemo CLASS kot stanja, jih oštevilčimo in izpišemo dobljeni KA: Dobljeni optimitizirani KA (z CLASS kot stanji):

Slika:Fsa7.jpg

Osebna orodja