4.3. Az automata, mint algebrai struktúra: részautomata, homomorfizmus, izomorfizmus, kompatibilis osztályozás

Az absztrakt automatákat vizsgálhatjuk algebrai struktúráként is. Mint ahogy beszélni szoktunk algebrai struktúrák rész-struktúráiról, homomorfizmusairól, izomorfizmusairól, ugyanígy szokás beszélni ezekről automaták esetén is. Először Mealy-féle automatákra fogjuk megadni a megfelelő részautomata-, homomorfizmus- és izomorfizmus-fogalmakat.

4.3.1. Mealy automata, mint algebrai struktúra

Egy A=(Q, T, V, d, f) Mealy-automata részautomatája alatt értjük azt az A '=(Q ', T ', V ', d ', f ') Mealy-automatát, melyre Q '⊆Q, T '⊆T, V '⊆V és d '=d| Q '×T ', illetve f '=f| Q '×T '. (Szavakban, d ' a d restrikciója, azaz megszorítása Q '×T '- re, f ' pedig az f restrikciója, azaz megszorítása Q '×T '- re.) Másként mondva, d ' és f ' úgy van definiálva, hogy alakjuk d ':Q '×T '  → Q ', illetve f ':Q '×T '  → V ', s teljesül minden qQ ', aT ' pár esetén a d '(q, a)=d(q, a), illetve az f '(q, a)=f(q, a) egyenlőség. Amint látjuk, a d és az f nem minden Q '×T '- re vett restrikciója alkalmas a részautomata átmeneti, illetve kimeneti függvényének. Kell még az is, hogy a tekintett d ' restrikció a Q '- be, illetve hogy a tekintett f ' restrikció a V '- be képezzen. Azt a tényt, hogy az A ' automata részautomatája az A automatának, időnként A '⊆A- val jelöljük.

Amennyiben az Q '⊆Q, T '⊆T, V '⊆V tartalmazások valamelyike valódi tartalmazás, azaz Q '⊊Q, T '⊊T, V '⊊V legalább egyike fennáll, úgy azt is mondjuk, hogy A ' valódi részautomatája A- nak, s ezt A '⊊A- val is jelöljük.

Ha Q '⊆Q és T=T ', V=V ', akkor az A '- t az A (valódi vagy nem valódi) állapot-, vagy Q- részautomatájának hívjuk (jelekben: A '⊆ Q A). Ha T '⊆T és Q=Q ', V '=V, akkor A ' bemenő jel részautomatája vagy T- részautomatája (jelekben: A '⊆ T A), ha pedig V '⊆V, továbbá Q '=Q, T '=T, akkor az A ' kimenőjel részautomatája, vagy V- részautomatája A- nak (jelekben: A '⊆ V A). Hasonló értelemben beszélünk (Q, T)-, (Q, V)-, (T, V)- részautomatákról.

További speciális automata-típus az iniciális részautomata, mely ugyancsak definiálható az említett részautomata-típusok bármelyikére. Akkor mondjuk, hogy egy A iniciális automatának egy A ' iniciális automata iniciális részautomatája, ha mindamellett, hogy A ' az A- nak részautomatája, az is teljesül, hogy az A ' kezdőállapota épp az A kezdőállapota lesz. Hasonló értelemben mint a korábbiakban, beszélünk iniciális Q- részautomatáról, iniciális T- részautomatáról, iniciális V- részautomatáról, illetve iniciális (Q, T)-, (Q, V)-, (T, V)- részautomatáról. Minden esetben tehát a megfelelő részautomata-tulajdonság mellett még azt is elvárjuk, hogy a megfelelő részautomata-típus kezdőállapota épp az őt tartalmazó automata kezdőállapota legyen.

Azt mondjuk, hogy az A '=(Q ', T ', V ', d ', f ') Mealy-automata homomorf képe az A=(Q, T, V, d, f) Mealy-automatának (jelekben AA '), ha megadható olyan szürjektív (azaz "ra" típusú, vagy más néven ráképező) ψ 1:Q  → Q ', ψ 2:T  → T ', ψ 3:V  → V ' leképezésekből álló ψ=(ψ 1, ψ 2, ψ 3) leképezés-hármas, hogy teljesülnek rá az úgynevezett művelettartó tulajdonságok. Más szóval, képletben kifejeve, tetszőleges qQ, aT pár esetén

ψ 1(d(q, a))=d '(ψ 1(q), ψ 2(a)),

illetve

ψ 3(f(q, a))=f '(ψ 1(q), ψ 2(a)).

Világos, hogy a homomorfia mint reláció reflexív ( AA) és tranzitív ( AA ', A '∼A ''⇒AA ''). Mint ahogy beszélünk speciális részautomatákról, ugyanúgy beszélünk speciális homomorfizmusokról. Azt mondjuk, hogy az A '=(Q ', T ', V ', d ', f ') Mealy-automata állapothomomorf képe vagy Q- homomorf képe az A=(Q, T, V, d, f) Mealy-automatának (jelekben A Q A '), ha az előbb definiált ψ 1, ψ 2, ψ 3 leképezés-hármasban a ψ 2 és a ψ 3 választható identikus leképezésnek. Ezen feltétel mellett tehát az előbbi egyenlőségeink tetszőleges qQ, aT pár esetén a következő alakúak lesznek: ψ 1(d(q, a))=d '(ψ 1(q), a), illetve f(q, a)=f '(ψ 1(q), a). Ebben az értelemben beszélünk tehát ψ 1:Q  → Q ' Q- homomorfizmusról. Ilyenkor nem egy leképezes-hármas, hanem egyetlen ψ 1 leképezés képviseli az állapothomomorfizmust (mert eltekintünk az identikus ψ 2:T  → T ' és ψ 3:V  → V ' leképezések szerepeltetésétől). Hasonló értelemben beszélünk ψ 2:T  → T ' bemenőjel-, vagy T- homomorfizmusról, ψ 3:Y  → Y ' kimenőjel-, vagy Y- homomorfizmusról, illetve ψ '={ψ 1, ψ 2} (Q, T)- homomorfizmusról (ahol ψ 1:Q  → Q ', ψ 2:T  → T '), ψ ''={ψ 1, ψ 3} (Q, V)- homomorfizmusról (ahol ψ 1:Q  → Q ', ψ 3:V  → V '), valamint ψ '''={ψ 2, ψ 3} (T, V)- homomorfizmusról (ahol ψ 2:T  → T ', ψ 3:V  → V ').

További speciális homomorfizmus típus az iniciális homomorfizmus, mely ugyancsak definiálható az említett speciális homomorfizmus-típusok (iniciális Q- homomorfizmus, iniciális T- homomorfizmus, stb.) bármelyikére is. Akkor mondjuk, hogy egy A iniciális automatának egy A ' iniciális automata iniciális homomorf képe (iniciális Q- homomorf képe, iniciális T- homomorf képe, stb.), ha mindamellett, hogy A ' a A- nak homomorf képe, az is teljesül, hogy az A ' kezdőállapota épp az A kezdőállapotának homomorf képe ( Q- homomorf képe, T- homomorf képe, stb.) lesz. Hasonló értelemben beszélünk tehát iniciális Q- homomorfizmusról, iniciális T- homomorfizmusról, iniciális V- homomorfizmusról, illetve iniciális (Q, T)-, (Q, V)-, (T, V)- homomorfizmusról. (Minden esetben a megfelelő homomorfia-tulajdonság mellett még azt is elvárjuk, hogy a homomorf kép kezdőállapota épp a ráképező automata kezdőállapota legyen.)

Amennyiben a homomorfizmus olyan, hogy az összes szereplő ráképezések bijekciók (azaz kölcsönösen egyértelmű ráképezések), akkor izomorfizmusról beszélünk. Így minden egyes speciális homomorfizmus-típusnak van egy megfelelő izomorfizmus-típusa ( Q- izomorfizmus, iniciális Q- izomorfizmus, stb.). Nyilvánvaló, hogy ha egy A Mealy-automatának egy A ' Mealy-automata izomorf képe (képletben AA '), s a φ=(φ 1, φ 2, φ 3) leképezés-hármas az A izomorfizmusa A '- re, akkor a φ -1=(φ 1 -1, φ 2 -1, φ 3 -1) leképezés-hármas az A ' izomorfizmusa lesz A- ra. Az izomorfizmus tehát mint reláció, szimmetrikus. Mindamellett mint a homomorfizmus általában (és az izomorfizmus a homomorfizmusnak speciális fajtája), az izomorfizmus mint reláció reflexív és tranzitív. Az izomorfizmus mint reláció tehát ekvivalencia reláció, hisz reflexív, szimmetrikus és tranzitív. (Ugyanez természetesen vonatkozik az összes speciális izomorfizmus-típusokra is.)

Az absztrakt algebrai vizsgálatoknál az egymással izomorf struktúrákat azonosnak szokták tekinteni. Ez az úgynevezett izomorfia elv. Ezt az elvet automataelméleti vizsgálatoknál sok esetben csak részlegesen szokásos elfogadni a vizsgálatok sajátosságai miatt.

Most részletesebben foglalkozunk még a Q- homomorfizmusokkal és a velük kapcsolatban álló kompatibilis osztályozásokkal. Legyen A=(Q, T, V, d, f) tetszőleges Mealy-automata és legyen ρ tetszőleges ekvivalencia reláció a Q állapothalmazon. Ismeretes, hogy minden ekvivalencia reláció egyértelműen indukál egy osztályozást azon a halmazon, amin a reláció értelmezve van. Nevezetesen, pontosan az egymással relációban lévő elemek fognak egy osztályba sorolódni. Így a ρ reláció is indukálja a Q halmaz egy C ρ osztályozását: a p és q állapotokat akkor és csak akkor soroljuk egy osztályba, ha egymással relációban vannak, azaz p ρ q fennáll. A q elem által reprezentált (vagyis a q elemet tartalmazó) osztályt C ρ [q]- val jelöljük. Jelölje az osztályok halmazát, azaz legyen ={C ρ [q]|qQ}. Egy ilyen C ρ osztályozást kompatibilis osztályozásnak nevezünk, ha a hozzá tartozó ρ reláció kongruencia reláció, vagyis ha ρ- ra teljesül az a követelmény, hogy minden p, qQ párra p ρ q- nek tetszőleges aT esetén következménye lesz d(p, a)ρ d(q, a) és f(p, a)=f(q, a).

Tegyük fel most, hogy a Q halmaz C ρ osztályozása pont egy kompatibilis osztályozás. Ekkor tehát minden p, qQ párra p ρ q- nek tetszőleges aT esetén következménye lesz d(p, a)ρ d(q, a) és f(p, a)=f(q, a). Másként fogalmazva, feltételezzük, hogy ha valamely p, qQ pár a C ρ osztályozás szerint egy és ugyanazon C ρ osztályba esik, akkor tetszöleges aT bemenő jel esetén d(p, a) és d(q, a) is egy osztályba fognak esni, továbbá f(p, a)=f(q, a) is fennáll. Ily módon definiálható a következő automata:

AC ρ =(, T, V, , ),

ahol minden qQ, aT párra

(C ρ ([q], a)=C ρ [d(q, a)], (C ρ ([q], a)=f(q, a).

Belátható, hogy ez az automata jól definiált és érvényes a következő:

A Q AC ρ ,

aholis a megfelelő Q- homomorfizmushoz úgy jutunk, hogy minden állapot állapothomomorf képeként az őt tartalmazó osztály adódik. Más szóval, egy automata faktorautomatái az automatának mindig Q- homomorf képei. A következő tétel azt mondja ki, hogy megfordítva, az A- homomorf képek mindig megszerkeszthetőek faktorautomataként. Ez a tétel az algebrában jól ismert Általános Homomorfia Tétel Mealy-automatákra vonatkozó speciális esete.

6. Tétel. (Általános Homomorfia Tétel Mealy-Automatákra Vonatkozó Speciális Esete) Tegyük fel, hogy az A=(Q, T, V, d, f) Mealy-automata az A '=(Q ', T ', V ', d ', f ') Mealy-automatára valamely állapothomomorfizmussal leképezhető, s tekinsük a Q állapothalmaznak azt a C osztályozását, amelynél bármely két p, qQ állapot akkor és csak akkor van egy osztályban, ha a tekintett állapothomomorfizmus szerinti képük ugyanaz. Ekkor a Q állapothalmaz ezen C osztályozása kompatibilis, s a hozzá tartozó AC faktorautomata Q- izomorf lesz az A ' automatával. Képletben,

A '∼ Q A(φ)⇒A/C Q A '(C[q]  → φ(q)).

4.3.2. Moore automata, mint algebrai struktúra

Most Moore-féle automatákra fogjuk megadni a megfelelő részautomata-, homomorfizmus-, és izomorfizmus-fogalmakat. Ekkor egy A=(Q, T, V, d, g) Moore-automata valamely részautomatája alatt értünk egy olyan A '=(Q ', T ', V ', d ', g ') Moore-automatát, melyre Q '⊆Q, T '⊆T, V '⊆V mellett d '=d| Q '×V ' és g '=g| Q ' teljesül. Más szóval tetszőleges qQ ', aT' pár esetén d '(q, a)=d(q, a) és g '(q)=g(q). Felmerül a kérdés, hogy ha egy Moore-automatát Mealy-féle automatának tekintünk, s vesszük ezen Mealy-automata egy (Mealy-automatáknál tárgyalt értelemben tekintett) részautomatáját, vajon ez a részautomata tekinthető lesz-e ugyancsak Moore-féle automatának, illetve részautomata lesz-e abban az értelemben is, ahogy azt a Moore-automaták esetén definiáltuk. A válaszunk az, hogy a két értelemben vett részautomata fogalom (Moore automatáknál) egybeesik. Legyen ugyanis f:Q×T  → V az a leképezés, melyre a tekintett Moore-automata, tetszőleges qQ ', aT ' pár esetén eleget tesz a f(q, a)=g(d(q, a)) összefüggésnek. Tegyük fel, hogy az ezen f függvénnyel definiált, A- ból nyert B=(Q, T, V, d, f) Mealy-automatának a B '=(Q ', T ', V ', d ', f ') Mealy-automata részautomatája. Ekkor d '=d| Q '×T ' és f '=f| Q '×T '. Ily módon tetszőleges qQ ', aT ' párra d '(q, a)=d(q, a) és f '(q, a)=f(q, a). Viszont f(q, a)=g(d(q, a)), f '(q, a)=f(q, a), valamint d '(q, a)=d(q, a) miatt ekkor f '(q, a)=g(d '(q, a)). Vagyis definiálhatjuk az A ''=(Q ', T ', V, d ', g) Moore-automatát, mely nyilvánvalóan (Q, T)- részautomatája lesz A- nak abban az értelemben, ahogy azt a Moore-automatáknál definiáltuk. Természetesen az is igaz, hogy V tetszőleges olyan V ''⊆V részhalmazára, melyre {g '(a)|qQ '}⊆V '', a g ''=g| Q '' feltételnek eleget tevő A '''=(Q ', T ', V '', d ', g '') Moore-automata a A automatának Moore-féle részautomatája lesz a Moore-automatáknál tekintett értelemben. Így valóban, ez a két részautomata-fogalom Moore-automatáknál egybeesik.

A Mealy-automatákra definiált speciális részautomata-fogalmak természetes módon definiálhatók Moore-féle automatákra, s az általános Moore-féle részautomata fogalomnál tárgyaltakhoz hasonló észrevételeket nyerünk, ha a Moore-automatákat speciális Mealy-automatáknak tekintve vesszük ezen Mealy-automaták megfelelő speciális ( Q-, T-, V-, (Q, T)-, (Q, V)-, (T, V)-) részautomatáit. Ugyanez érvényben marad az iniciális Moore-automaták iniciális részautomatáira is és azok további speciális (iniciális Q- részautomata, iniciális T- részautomata, stb.) eseteire is.

Egy A=(Q, T, V, d, g) Moore-automata valamely A '=(Q ', T ', V ', d ', g ') Moore-automatára történő (általános) Moore-homomorfizmusa alatt egy olyan ψ=(ψ 1, ψ 2, ψ 3) szürjektív leképezésekből álló leképezés-hármast értünk, melynek tagjai ψ 1:Q  → Q ', ψ 2:T  → T ', ψ 3:V  → V ' formájúak, s teljesülnek rájuk minden qQ, aT pár esetén a

ψ 1(d(q, a))=d '(ψ 1(q), ψ 2(a)),

illetve a

ψ 3(g(q))=g '(ψ 1(q))

összefüggés. Igazolható, hogy a Moore-féle homomorfizmus speciális esete a Mealy-féle automatákra értelmezett homomorfizmusnak abban az értelemben, hogy ha szereplő Moore-automatákat speciális Mealy-automatáknak tekintjük, akkor az előbb definiált Moore-féle homomorfizmus egy Mealy-féle automatákra definiált homomorfizmust fog szolgáltatni. De az is igaz, hogy lehetséges példát adni olyan Moore-automatára, melyet ha Mealy-automatának tekintünk, a Mealy-automatáknál vett értelemben homomorfan leképezhető lesz egy olyan Mealy-automatára, mely nem tekinthető Moore-automatának (lásd alábbi példában).

4.6. példa - Mealy és Moore automaták homomorfizmusa

Legyen adva egy A=({p, q}, {a, b}, {x, y}, d, g) Moore-automata, melyre d(p, a)=d(q, a)=p, d(p, b)=d(q, b)=q és g(p)=x, g(q)=y. Ezt a Moore-automatát Mealy-automatának tekintve nyerjük a B=({p, q}, {a, b}, {x, y}, d, g) Mealy-automatát, melyre f(p, a)=f(q, a)=x, f(p, b)=f(q, b)=y. Nyilvánvalóan fennáll minden q '∈{p, q}, a '∈{a, b} párra a f(q ', a ')=g(d(q ', a ')) összefüggés. Most vegyük a B '=({r}, {a, b}, {x, y}, d ', f ') Mealy-automatát, melyre d '(r, a)=d '(r, b)=r fennállása mellett f '(r, a)=x, f '(r, b)=y. Azonnal látszik, hogy a ψ(p)=ψ(q)=r összefüggéssel definiált ψ:{p, q} → {r} leképezés a B egy Q- homomorfizmusa lesz B '- re. De d '(r, a)=d '(r, b)=r és f '(r, a)≠f '(r, b) mellett az is látszik, hogy nincs olyan g ':{r} → {x, y} leképezés, melyre f '(r, a ')=g '(d '(r, a ')) fennállna minden a '∈{a, b} mellett. B ' tehát nem Moore-automata. ★


Ugyanúgy mint a Mealy-automatáknál, itt is tekinthetünk különféle speciális Moore-féle Q-, T-, V-, (Q, T)-, (Q, V)-, (T, V)- homomorfizmus típusokat, továbbá tekinthetjük mind az általános Moore-féle homomorfizmus-fogalom, mind pedig a speciális Moore-féle homomorfizmus-típusok iniciális változatait iniciális Moore-automatákra. Ugyanúgy, mint az általános esetben, ezekben az esetekben is lehet példát adni arra, hogy (Moore-automaták esetén) a Moore-féle speciális homomorfizmus-fogalmak (Moore-féle Q-, T-, V-, (Q, T)-, (Q, V)-, (T, V)- homomorfizmus és ezek iniciális változatai) is valódi speciális esetei a Mealy-féle változatoknak. Végül megjegyezzük, hogy ha a szereplő leképezések bijektívek (vagy ha egy ilyen leképezés van akkor ha a szereplő leképezés bijektív), akkor Moore-féle izomorfizmusról, illetve annak megfelelő speciális típusairól beszélünk. Izomorfizmusok esetén viszont a két féle (Mealy-féle, illetve Moore-féle) izomorfizmus-fogalmak egybeesnek.

Hasonlóan mint Mealy-automaták esetén, kimondható az algebrában jól ismert Általános Homomorfia Tétel Moore-automatákra vonatkozó speciális esete.

7. Tétel. (Általános Homomorfia Tétel Moore-Automatákra Vonatkozó Speciális Esete) Tegyük fel, hogy az A=(Q, T, V, d, g) Moore-automata az A '=(Q ', T ', V ', d ', g ') Moore-automatára valamely Moore-féle állapothomomorfizmussal leképezhető, s tekinsük a Q állapothalmaznak azt a C osztályozását, amelynél bármely két p, qQ állapot akkor és csak akkor van egy osztályban, ha a tekintett Moore-féle állapothomomorfizmus szerinti képük ugyanaz. Ekkor az Q állapothalmaz ezen C osztályozása kompatibilis, s a hozzá tartozó AC faktorautomata Q- izomorf lesz az A ' automatával. Képletben,

A '∼ Q A(φ)⇒A/C Q A '(C[q]  → φ(q)).

4.3.3. Kimenőjel nélküli automata, mint algebrai struktúra

Hátramaradt még a megfelelő részautomata-, homomorfizmus-, és izomorfizmus-fogalmak kimenőjel nélküli automatákra történő definiálása. Természetesen az is igaz, hogy némi megszorítással (a kimenő jelhalmazokra vonatkozó összefüggések figyelmen kívül hagyásával) a homomorfizmus, izomorfizmus és annak egyes speciális típusai definiálhatók kimenőjel nélküli automatákra is. Így például az A=(Q, T, d) kimenőjel nélküli automatának részautomatája az A '=(Q ', T ', d ') kimenőjel nélküli automata, ha Q '⊆Q, T '⊆T, valamint d '=d| Q '×T '. Továbbá az A=(Q, T, d) kimenőjel nélküli automatának homomorf képe az A '=(Q ', T ', d ') kimenőjel nélküli automata, ha alkalmas ψ 1:Q  → Q ', ψ 2:T  → T ' alakú, szürjektív leképezésekből álló ψ=(ψ 1, ψ 2) leképezés-párra minden qQ, aT esetén ψ 1(d(q, a))=d '(ψ 1(q), ψ 2(a)) fennáll. Az algebrában jól ismert Általános Homomorfia Tétel kimenőjel nélküli automatákra vonatkozó speciális esete formailag csaknem egybeesik a Mealy-féle automatákra vonatkozó speciális esettel.

8. Tétel. (Általános Homomorfia Tétel Kimenő Jel Nélküli Automatákra Vonatkozó Speciális Esete) Tegyük fel, hogy az A=(Q, T, d) kimenőjel nélküli automata az A '=(Q ', T ', d ') kimenőjel nélküli automatára valamely állapothomomorfizmussal leképezhető, s tekinsük a Q állapothalmaznak azt a C osztályozását, amelynél bármely két p, qQ állapot akkor és csak akkor van egy osztályban, ha a tekintett állapothomomorfizmus szerinti képük ugyanaz. Ekkor a Q állapothalmaz ezen C osztályozása kompatibilis, s a hozzá tartozó AC faktorautomata Q- izomorf lesz az A ' automatával. Képletben,

A '∼ Q A(φ)⇒A/C Q A '(C[q]  → φ(q)).

Az elmélet további kiépítésénél elsősorban Mealy-automatákra szorítkozunk. Így ha mást nem mondunk, a jegyzetnek ebben a részében automata alatt mindig Mealy-féle automatát fogunk érteni, azaz a Mealy-automaták esetén a "Mealy" jelzőt sok esetben elhagyjuk.