4.4. Az automaták által indukált leképezések

A korábban nem üres és véges halmazokra definiált néhány fogalmat a továbbiakban tetszőleges halmazokra is értelmezni fogjuk. Így valamely (véges vagy végtelen) V halmaz elemeiből alkotott véges láncot V- beli szónak, V elemeit pedig időnként betűknek hívjuk. Ha V az üres halmaz, technikai okokból (ahogy a Kleene itaráció definíciójából is kitűnik) V * egy olyan egy elemű halmazt jelöl, melynek egyetlen eleme az üresszó: tehát ∅*={λ}. Nemcsak véges, hanem végtelen V halmazokra is (és az üres halmazra is) érvényes lesz, hogy a V *- beli összes szavak a konkatenációra (egymás mellé írásra) nézve - mint műveletre - monoidot, azaz egységelemes szabad félcsoportot fognak alkotni. Ugyancsak igaz, nemcsak véges hanem végtelen V halmazokra is, hogy a V +- beli összes szavak a konkatenációra (egymás mellé írásra) nézve - mint műveletre - szabad félcsoportot fognak alkotni. (Ha V az üres halmaz, akkor a V feletti összes nem üres szavak V + halmaza is nyilván üres halmaz. Márpedig egy félcsoportról fel szokás tételezni, hogy legalább egy eleme van, azaz az üres halmazt nem szokás félcsoportnak tekinteni. Így V +- t nem tekintjük félcsoportnak ha V üres halmaz.) Egy pV * szó hosszát - akkor is ha V nem véges - |p|- el jelöljük, s mint korábban, a szót alkotó betűk számát értjük alatta (multiplicitásokkal együtt). A V halmaz számosságát is (akár véges, akár nem, akár üres akár nem) |V|- el jelöljük. Végül, ha p nem üres, mint korábban, ≫p jelöli a p utolsó betűjét.

Legyen A=(Q, T, V, d, f) tetszőleges Mealy-automata. A d:Q×TQ és a f:Q×TV függvények értelmezését kiterjesztjük Q×T *- ra a következő definícióval:

Legyenek d:Q×T *  → Q +, f:Q×T *  → V * úgy definiálva, hogy tetszőleges qQ és a 1, …, a n T esetén álljanak fenn a

d(q, a 1⋅⋅⋅a n )=q 1⋅⋅⋅q n

és a

f(q, a 1⋅⋅⋅a n )=b 1⋅⋅⋅b n

összefüggések, ahol q 1=d(q, a 1), …, q n =d(q n-1, a n ), illetve b 1=f(q, a 1), …, b n =f(q n-1, a n ). Emellett legyen d(q, λ)=q, f(q, λ)=λ. Ez a formális definíció annak az interpretációnak felel meg, hogy bármely qQ állapotból indulva az A automata egy bemenő jelsorozatnak egy kimenő jelsorozatot feleltet meg (az automata "szekvenciális gép"). Nevezetesen, az automata az üres bemenő szóra üres kimenő szóval reagál.

Valamely T halmaz feletti T * szabad monoidot egy V halmaz feletti V * szabad monoidba leképező α:T *  → V * leképezést alfabetikus leképezésnek hívunk. A bemenő szavak a bemenő információ, a kimenő szavak pedig a kimenő információ hordozói. Az automata az információ átalakítást alfabetikus leképezések segítségével realizálja. Így a fenti a 1 a 2⋅⋅⋅a n szóhoz az automata a fenti b 1 b 2⋅⋅⋅b n szót rendeli hozzá. Speciálisan, az üresszónak minden állapot az üresszót felelteti meg, hisz definícióink értelmében tetszőleges qQ állapotra f(q, λ)=λ. A továbbiakban egy A=(Q, T, V, d, f) Mealy-automata minden egyes qQ állapotához hozzárendeljük a φ q, A (w)=f(q, w), wT * összefüggéssel definiált φ q, A :T *  → V * leképezést, melyet a qQ állapot által indukált leképezésnek is fogunk hívni. Ha nem áll fenn a félreértés veszélye, φ q, A helyett a legtöbbször csak φ q - t írunk. Iniciális A=(Q, T, V, q 0, d, f) Mealy-automata esetén a q 0 kezdőállapottal indukált φ q 0 leképezést az A iniciális automata által indukált leképezésnek, vagy röviden az A automata leképezésének is mondjuk és időnként φ A - val jelöljük. A következő tétel George N. Raneytől (ejtsd: réni) származik.

9. Tétel. (Raney tétele) Egy φ:T *  → V * alfabetikus leképezés akkor és csak akkor automata leképezés, ha eleget tesz a következő két feltételnek:

(i) hossztartó, azaz tetszőleges wT *- ra |w|=|φ(w)|,

(ii) kezdőszelet tartó (kezdőszeletet kezdőszeletbe visz át), azaz minden w, vT *- hoz létezik olyan uV *, hogy φ(w v)=φ(w)u.

Bizonyítás. A szükségesség nyilvánvaló a kiterjesztett átmeneti és kimeneti függvények tulajdonságai miatt. Valóban, legyen A=(Q, T, V, d, f) tetszőleges Mealy-automata, s legyen qQ tetszőleges állapota. Legyen wT * tetszőleges. Ha w=λ, azaz w az üresszó, akkor f(q, λ)=λ a definíciónk szerint, azaz a φ q (λ)=f(q, λ) és a f(q, λ)=λ összefüggések miatt ekkor φ q (λ)=λ, amiből |φ q (λ)|=|λ| nyilvánvalóan következik. φ q tehát az üresszóra teljesíti a hossztartó tulajdonságot. Most legyen wT * nem üresszó, azaz legyen valamely a 1, …, a n T bemenő jelekre w=a 1a n . Ekkor, amint a d és f függvények kiterjesztésénél láttuk, alkalmas q 1, …, q n Q állapotokra q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n =d(q n-1, a n ) teljesülése mellett f(q, a 1⋅⋅⋅a n )=f(q, a 1)f(q 1, a 2)⋅⋅⋅f(q n-1, a n ). Vagyis, bevezetve a b 1=f(q, a 1), b 2=f(q 1, a 2), …, b n =f(q n-1, a n ) jelöléseket, φ q (a 1⋅⋅⋅a n )=f(q, a 1⋅⋅⋅a n )=b 1⋅⋅⋅b n . Ebből nyilvánvaló, hogy |a 1⋅⋅⋅a n |=|b 1⋅⋅⋅b n |=n, vagyis |w|=|φ q (w)|, azaz φ w minden T *- beli (üres vagy nem üres) szóra hossztartó.

Az üresszó T *- nak és V *- nak egységeleme, azaz tetszőleges vT *, wV * esetén λ v=v λ=v, illetve λ w=w λ=w. Legyen most vT * tetszőleges szó. Ekkor azt kapjuk, hogy φ q (λ v)=φ q (v)=λ φ q (v). Vagyis a kezdőszelet tartó tulajdonság teljesülni fog ha az üresszó a kezdőszelet, a végszelet pedig maga a tekintett szó. (Írjunk u- t a φ q (v) helyébe a φ q (λ v)=λ φ q (v) egyenlőség jobboldalán.) Hasonlóan kapjuk tetszőleges wT *- ra a φ q (w λ)=φ q (w)=φ q (w)λ levezetést. Tehát a kezdőszelet tartó tulajdonság akkor is teljesülni fog, ha a szó kezdőszeletének magát a szót tekintjük, végszeletének pedig az üresszót. (Írjunk u- t a λ helyébe a φ q (w λ)=φ q (w)λ egyenlőség jobboldalán.) Most válasszuk meg a w, vT * párt úgy, hogy egyikük se legyen üres. Ekkor valamely a 1, …, a k , a k+1, …, a n T bemenő jelekre w=a 1⋅⋅⋅a k , v=a k+1⋅⋅⋅a n . Vezessük be rendre a q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n =d(q n-1, a n ) és a b 1=f(q, a 1), b 2=f(q 1, a 2), …, b n =f(q n-1, a n ) jelöléseket. Ekkor φ q (w v)=f(q, w v)=f(q, a 1⋅⋅⋅a n )=f(q, a 1)f(q 1, a 2)⋅⋅⋅f(q k-1, a k )f(q k+1, a k+1)⋅⋅⋅f(q n-1, a n )=b 1⋅⋅⋅b k b k+1⋅⋅⋅b n és φ q (w)=f(q, w)=f(q, a 1⋅⋅⋅a k )=f(q, a 1)f(q 1, a 2)⋅⋅⋅f(q k-1, a k )=b 1⋅⋅⋅b k fennállnak. Ebből viszont φ q (w v)=φ q (w)b k+1⋅⋅⋅b n , vagyis az u=b k+1⋅⋅⋅b n választással kapjuk, hogy alkalmas uV *- ra φ q (w v)=φ q (w)u ebben az esetben is fennáll. φ q tehát valóban kezdőszelet tartó.

Az elegendőséghez legyen φ:T *  → V * tetszőleges hossz- és kezdőszelet-tartó alfabetikus leképezés. Ekkor minden w, vT * párhoz lesz olyan uV *, hogy φ(w v)=φ(w)u.

Rögzített wT * esetén jelölje φ w azt a φ w :T *  → V * alfabetikus leképezést, melyre tetszőleges vT * esetén a φ(w v)=φ(w)φ w (v) egyenlőség fog teljesülni. Először mutassuk meg, hogy a tetszőlegesen választott wT *- hoz tekintett φ w alfabetikus leképezés is automata leképezés. Valóban, φ hossztartó volta miatt |w v|=|φ(w v)| és |w|=|φ(w)|. Másrészt φ(w v)=φ(w)φ w (v) miatt |φ(w)φ w (v)|=|φ(w v)|, azaz |w|+|v|=(|w v|=|φ(w)φ w (v)|=)|φ(w)|+|φ w (v)|. Ebből |w|=|φ(w)| értelmében |v|=|φ w (v)|, azaz φ w hossztartó. Mutassuk meg, hogy kezdőszelet tartó is. Legyen v, zT * tetszőleges. Ekkor φ(w v z)=φ(w)φ w (v z) és φ(w v z)=φ(w v)φ w v (z)=φ(w)φ w (v)φ w v (z) is teljesülni fognak a φ kezdőszelet tartó volta miatt. Így φ(w)φ w (v z)=φ(w)φ w (v)φ w v (z) is teljesül. Ám szabad monoidban a szavak egyenlősége betűről-betűre való egyenlőséget jelent, azaz a legutóbb kapott egyenlőségünkből φ w (v z)=φ w (v)φ w v (z) is következik. Más szóval, tetszőleges v, zT *- hoz létezik olyan u(=φ w v (z))∈V *, hogy φ w (v z)=φ w (v)u teljesül. Tehát φ w is kezdőszelet tartó. Azt kaptuk tehát, hogy tetszőleges wT * esetén φ w is automata leképezés. Tetszőleges wT * esetén a φ w automata leképezést a továbbiakban a φ leképezés állapotának fogjuk hívni. Legyen Q φ ={φ w |wT *} és definiáljuk az A φ =(Q φ , T, V, φ λ , d φ , f φ ) Mealy-automatát úgy, hogy minden φ w Q φ , aT esetén d φ (φ w , a)=φ w a , f φ (φ w , a)=φ w (a). A tételhez azt kell még megmutatni, hogy A φ automata a φ leképezést indukálja.

Mivel az üresszó az egyetlen olyan szó, melynek hossza nulla, a φ hossztartó volta miatt φ(λ)=λ. Így tekintettel arra, hogy az üresszó mint bemenő szó hatására egy Mealy-automata kimenő szóként definíció szerint az üresszót adja ki, f φ (φ λ , λ)=φ(λ)(=λ) teljesülni fog. Most legyen w=a 1⋅⋅⋅a n egy nem üres bemenő szó, ahol a 1, …, a n T tetszőleges bemenő jelek. Az A φ automata definíciója értelmében, valamint amiatt, hogy tetszőleges uT * szóra λ u=u fennáll, d(φ λ , w)=d(φ λ , a 1⋅⋅⋅a n )=φ λ a 1 φ λ a 1 a 2 ⋅⋅⋅φ λ a 1⋅⋅⋅a n =φ a 1 φ a 1 a 2 ⋅⋅⋅φ a 1⋅⋅⋅a n . Ekkor azonban, ugyancsak az A φ automata definíciója alapján φ A φ =f φ (φ λ ,w)=f φ (φ λ ,a 1⋅⋅⋅a n )=f φ (φ λ ,a 1)f φ (φ a 1 ,a 2)⋅⋅⋅f φ (φ a 1⋅⋅⋅a n-1,a n )=φ λ (a 1)φ a 1 (a 2)⋅⋅⋅φ a 1⋅⋅⋅a n-1 (a n )= =λ φ λ (a 1)φ a 1 (a 2)⋅⋅⋅φ a 1⋅⋅⋅a n-1 (a n )=φ(λ)φ λ (a 1)φ a 1 (a 2)⋅⋅⋅φ a 1⋅⋅⋅a n-1 (a n )=φ(λ a 1)φ a 1 (a 2)⋅⋅⋅φ a 1⋅⋅⋅a n-1 (a n )= =φ(λ a 1 a 2)φ a 1 a 2 (a 3)⋅⋅⋅φ a 1⋅⋅⋅a n-1 (a n )=⋅⋅⋅=φ(λ a 1⋅⋅⋅a n )=φ(a 1⋅⋅⋅a n )=φ(w).

Viszont épp ezt kellett bizonyítani. ∎

Nyilvánvaló, hogy ha egy automata leképezés egy véges iniciális automatával indukálható, akkor ennek az automata leképezésnek legfeljebb annyi állapota lehet mint az őt indukáló véges automatának. Másrészt az is világos, hogy a Raney tételének bizonyításában szereplő A φ automata véges, ha a bemenő és kimenő jelhalmazok végessége mellett a tekintett φ automata leképezés véges állapotú. Így a következő állításhoz jutunk.

1. Következmény. Egy véges halmaz feletti monoidot egy véges halmaz feletti monoidba képező automata leképezés akkor és csakis akkor indukálható véges automatában, ha állapotainak száma véges.

2. Megjegyzés. Egy φ:T *  → V * automata leképezés indukálható a következő Mealy-automatával is: A φ =(T *, T, V, λ, d φ , f φ ), ahol tetszőleges wT *, aT párra d φ (w, a)=w a, f φ (w, a)=≫φ(w a) (ahol ≫φ(w a) a φ(w a) utolsó betűjét jelöli).

Az A φ automatát a φ automata leképezéshez tartozó alsó automatának, az A φ automatát pedig a φ automata leképezéshez tartozó felső automatának hívjuk. Világos, hogy a felső automata mindig végtelen állapotú.

Egy iniciális automatát iniciálisan összefüggőnek hívunk, ha a kezdőállapotából minden állapotba visz át bemenő szó. Képletben, az A=(Q, T, V, q 0, d, f) iniciális Mealy automata iniciálisan összefüggő, ha minden qQ állapothoz létezik olyan wT * bemenő szó, hogy d(q 0, w)=q, azaz a q 0 állapotból indulva a w szót feldolgozva az automata a q állapotba jut. (Megjegyezzük, hogy w=λ választással ez a kezdőállapotra mindig fennáll.) Nyilvánvaló, hogy egy automata leképezéshez tartozó alsó és felső automaták iniciálisan összefüggőek. Bizonyítás nélkül megemlítjük a következő tételt.

10. Tétel. Ha A tetszőleges olyan iniciálisan összefüggő automata, amely a φ leképezést indukálja, akkor az A automata az A φ felső automatának állapothomomorf képe, s ugyanekkor az A φ alsó automata pedig A- nak állapothomomorf képe.

3. Megjegyzés. Egy φ automata leképezés előállításánál felhasznált automaták közül a hozzá tartozó alsó automata a lehető leggazdaságosabb, a hozzá tartozó felső automata pedig a lehető leggazdaságtalanabb. Így az optimális előállításnál a φ automata leképezéshez tartozó alsó automatát kell előállítani. Ez így azonban csupán elméleti eredmény, mivel adott w, vT * párra általában nehéz ellenőrizni, hogy fennáll-e a φ w =φ v egyenlőség.

11. Tétel. Tetszőleges T halmazra T * összes önmagába történő automata leképezéseinek K T halmaza a leképezések szokásos szorzására nézve monoidot, azaz egységelemes félcsoportot alkot.

4. Megjegyzés. Egy A=(Q, T, V, q 0, d, f) által indukált leképezésnek a B=(Q ', T ', V ', q' 0, d ', f ') automata által indukált leképezéssel való szorzása értelmezhető, ha VT '. Ezt a szorzat-leképezést a B automata indukálja, ha B '=(Q×Q ', T, V ', (q 0, q' 0), d '', f '') alakú, ahol tetszőleges (q, q ')∈Q×Q ', aT párra d ''((q, q '), a)=(d(q, a), d '(q ', f(q, a)) és f ''((q, q '), a)=f '(q ', f(q, a)). A B ' automatát az A automata B automatával történő soros kapcsolásának vagy szuperpozíciójának hívjuk.

12. Tétel. Egy T halmaz feletti T * monoid összes önmagába történő, véges automaták által indukálható leképezéseinek L T halmaza a leképezések szokásos szorzására nézve részfélcsoportot alkot a K T félcsoportban.

13. Tétel. Tetszőleges T halmazra az T * összes önmagába történő bijektív automata leképezéseinek A T halmaza a leképezések szokásos szorzására nézve részcsoportot alkot a K T félcsoportban.

14. Tétel. Egy T halmaz feletti T * monoid összes önmagába történő, véges automaták által indukálható bijektív leképezéseinek G T halmaza a leképezések szokásos szorzására nézve részcsoportot alkot a K T félcsoportban és az A T csoportban.

Egy S félcsoport generátorrendszerén értjük S- beli elemek egy H részhalmazát, ha S minden eleme előáll H- beli elemek szorzataként. H minimális generátorrendszere, vagy más néven bázisa S- nek, ha amellett hogy S- nek generátorrendszere, tetszőleges hH mellett H∖{h} már nem generátorrendszere S- nek. Hasonlóan, egy G csoport generátorrendszerén értjük G- beli elemek egy H részhalmazát, ha G minden eleme előáll olyan szorzatként, melynek minden tényezője vagy egy H- beli elem, vagy pedig egy H- beli elem inverze. Ugyanúgy mint félcsoportok esetén, H minimális generátorrendszere, vagy más néven bázisa G- nek, ha amellett hogy G- nek generátorrendszere, tetszőleges hH mellett H∖{h} már nem generátorrendszere G- nek. (Az itt szereplő S és G betűk az angol group (=csoport), illetve semi-group szavak kezdőbetűi, a generatív nyelvtanoknál szereplő S, illetve G- vel való azonosságuk csak a véletlen műve!)

Nem nehéz belátni, hogy ha T egy egyelemű halmaz vagy T az üres halmaz, akkor K T , L T , A T , G T mindegyike egy elemű. Így ebben az esetben mindegyiknek önmaga a bázisa. Ha T legalább két elemű, akkor érvényes a következő állítás.

15. Tétel. Egy legalább két elemű T halmaz esetén K T - nek és L T - nek nincs bázisa.

Nyitott kérdés, hogy van-e bázisa A T - nek, illetve G T - nek egy legalább két elemű T halmaz esetén.

Végül megjegyezzük, hogy Moore-automata esetén az átmeneti és jelfüggvények kiterjesztése hasonlóképp történik mint Mealy-automata esetén. Legyen A=(Q, T, V, d, g) tetszőleges Moore-automata. A d:Q×TQ és a g:Q → V függvények értelmezését kiterjesztjük Q×T *- ra, illetve Q +- ra a következő definícióval:

Legyenek d:Q×T *  → Q +, g:Q *  → V * úgy definiálva, hogy tetszőleges qQ és a 1, …, a n T esetén álljanak fenn a

d(q, a 1⋅⋅⋅a n )=q 1⋅⋅⋅q n

és a

g(q 1⋅⋅⋅q n )=b 1⋅⋅⋅b n

összefüggések, ahol q 1=d(q, a 1), …, q n =d(q n-1, a n ), illetve b 1=g(q 1), …, b n =g(q n ). Emellett legyen d(q, λ)=q, g(λ)=λ. Ekkor a q állapot által indukált φ q leképezésre φ q (λ)=g(λ)=λ, illetve tetszőleges a 1, …, a n T- re φ q (a 1⋅⋅⋅a n )=g(q 1⋅⋅⋅q n ), aholis q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n =d(q n-1, a n ). Később látni fogjuk, hogy minden iniciális Mealy-automatával indukálható automata leképezés indukálható iniciális Moore-automatával is. Sőt az is igaz, hogy ha egy automata leképezés véges iniciális Mealy automatával indukálható, akkor indukálható véges iniciális Moore-automatával is. Így a fejezetben tárgyaltak Moore-automatákra ugyanígy érvényben maradnak. Az átmeneti függvény természetesen kiterjeszthető kimenőjel nélküli automata esetén is. Nevezetesen, ugyanúgy mint Moore-automata esetén, egy A=(Q, T, d) tetszőleges kimenőjel nélküli automatára a d:Q×TQ függvény értelmezését úgy terjesztjük ki Q×T *- ra, hogy d:Q×T *  → Q +- t a következőképp definiáljuk: Legyen d:Q×T *  → Q + úgy definiálva, hogy tetszőleges qQ és a 1, …, a n T esetén álljanak fenn a

d(q, a 1⋅⋅⋅a n )=q 1⋅⋅⋅q n

összefüggések, ahol q 1=d(q, a 1), …, q n =d(q n-1, a n ). Emellett legyen d(q, λ)=q. Ekkor a q állapot által indukált φ q leképezésre φ q (λ)=λ, illetve tetszőleges a 1, …, a n T- re φ q (a 1⋅⋅⋅a n )=q 1⋅⋅⋅q n , aholis q 1=d(q, a 1), q 2=d(q 1, a 2), …, q n =d(q n-1, a n ).

Mint korábban megjegyeztük, egy A=(Q, T, d) kimenőjel nélküli automatát szokás olyan A=(Q, T, V, d, f) Mealy-automatának tekinteni, ahol V=Q és f=d. Ez a kiterjesztett átmeneti és kimeneti függvényekre csak korlátozottan érvényes. Nevezetesen, ha wT * nem üres, akkor a kiterjesztett kimeneti függvényt is úgy értelmezzük, hogy f(q, w)=d(q, w), qQ. Az üresszó esetén viszont a kiterjesztett átmeneti és kimeneti függvényeket ebben az esetben (tehát egy A=(Q, T, Q, d, f) Mealy automatának tekintett A=(Q, T, d) kimenőjel nélküli automaták esetén) úgy definiáljuk, hogy d(q, λ)=q és f(q, λ)=λ minden qQ- ra. Ekkor egy A=(Q, T, d) kimenőjel nélküli automata esetén egy qQ állapot által indukált φ q leképezés alatt értjük azt a φ q :Q *  → Q * leképezést, melyre tetszőleges wT * esetén

φ q (w)=d(q, w), ha wλ,

φ q (w)=λ, ha w=λ.

A kimenőjel nélküli automaták által indukált automata leképezések speciális automata leképezések, s nem minden (Mealy- vagy Moore-féle automatával indukálható) automata leképezés indukálható véges automatával.

4.7. példa - Automataleképezések

Legyen A=({q 0, q}, {a, b}, {a, b}, q 0, d, f) egy iniciális Mealy-automata, ahol d(q 0, a)=d(q, a)=q 0, d(q 0, b)=d(q, b)=q, f(q 0, a)=f(q, a)=f(q 0, b)=a, f(q, b)=b. Ekkor φ q 0 (a a b a b b)=a a a a a b, amihez akárhogy is szerkesztünk meg egy iniciális kimenőjel nélküli B=(Q ', T, p 0, d ') automatát, φ p 0 (a a b a b b)≠a a a a a b fog teljesülni. Tehát valóban, nem minden automata leképezés indukálható kimenőjel nélküli automatával. ★