5.8. Véges automaták által indukálható leképezések

Ebben a részben a véges automaták által indukálható leképezéseket (lásd Az automaták által indukált leképezések fejezet) a reguláris nyelvekkel kapcsolatosan vizsgáljuk.

Érvényes a következő állítás.

3. Segédtétel. Tetszőleges φ:T *  → V * automata leképezés esetén egy bV akkor és csak akkor lesz valamely wT *- ra a φ(w) képszó valamely betűje, ha van olyan w '∈T *, hogy b a φ(w ') képszó utolsó betűje.

Bizonyítás. Legyen φ:T *  → V * tetszőleges automata leképezés, s tételezzük fel, hogy valamely wT * esetén a bY betű előfordul a φ(w) képszóban. Ekkor φ(w) előáll φ(w)=p b r alakban, ahol p, rV *. Mivel φ hossztartó, |w|=|φ(w)|. Így w előáll w=u a v alakban, ahol |u|=|p|, aT és |v|=|r|. Ráadásul a hossztartó tulajdonság miatt φ(u a) és p b hossza is szükségképp megegyezik. Másrészt φ kezdőszelet tartó, azaz φ(u a)=p b. Ha tehát bV előfordul egy képszóban, akkor előfordul egy (esetleg másik) képszó utolsó betűjeként is. ∎

A továbbiakban olyan φ:T *  → V * automata leképezésekre szorítkozunk, ahol minden bV előfordul legalább egy wT * szó képszavában. Fenti segédtételünk értelmében ekkor minden bV elő fog fordulni legalább egy wT * szó képszavának utolsó betűjeként.

Legyenek T és V véges halmazok és legyen φ:T *  → V * tetszőleges (nem feltétlen véges állapotú) automata leképezés. Megmutatjuk, hogy φ jellemezhető nyelvek egy alkalmas rendszerével. Tetszőleges bV- re legyen L b ={wT *|≫φ(w)=b}. Más szóval, az L b legyen azoknak a T *- beli w szavaknak a halmaza, amelyek a φ leképezésnél a b- re végződő szóba esnek át. Tekintsük az ilyen L b nyelvek halmazát: H φ ={L b |bV}. H φ eleget tesz a következő feltételeknek:

(a) H φ véges sok elemből áll.

(b) ∀b, b '∈V:bb '⇒L b L b '=∅.

(c) Minden nem üres wT *- hoz van olyan bV, hogy wL b .

(d) A λ üresszó nincs benne egyik L b - ben sem.

Az (a)-(d) feltételek jelentése az, hogy az L b (bV) nyelvek a T *∖{λ} halmaz egy véges indexű osztályozását alkotják. Az (a)-(d) feltételeknek eleget tevő nyelvrendszereket automata nyelvrendszereknek nevezzük.

28. Tétel. Ha a T és V véges halmazok, akkor minden φ:T *  → V * automata leképezéshez hozzárendelhető a T feletti nyelvalgebra egy H φ automata nyelvrendszere. Megfordítva, a véges T ábécé feletti nyelvalgebra bármely H automata nyelvrendszere a véges V halmaz elemeinek jelölésétől eltekintve egyértelműen meghatározza azt a φ:T *  → V * automata leképezést, melyre H φ =H.

Bizonyítás. A tétel első felét már beláttuk. Második felének bizonyításához legyen H az L A Y nyelvalgebra egy tetszőleges automata nyelvrendszere és legyen H={H 1, …, H n }. Legyen továbbá V={1, …, n} és határozzuk meg azt a φ:T *  → V * automata leképezést, melyre tetszőleges w=a 1⋅⋅⋅a k T *, a 1, …, a k T szó esetén φ(w)=i 1⋅⋅⋅i k , ahol a 1H i 1 , a 1 a 2H i 2 , …, a 1⋅⋅⋅a k H i k . Ez a φ leképezés nyilván automata leképezés és rá H φ =H teljesül. ∎

A tétel azt fejezi ki, hogy a véges T és V halmazokhoz tartozó φ:T *  → V * alakú automata leképezések a V elemeinek jelölésétől eltekintve egy-egy értelmű módon jellemezhetők nyelvek bizonyos rendszerével. Így valóban eljutottunk az automata leképezések olyan megadási módjához, mely a korábban kirótt feltételeinket teljesíti.

Egy A automatához tartozó K A kanonikus nyelvrendszeren az A automata által indukált leképezéshez tartozó automata nyelvrendszert értjük. Képletben: K A =H φ A . (Itt feltesszük, hogy A iniciális automata, melynek bemenő és kimenő jelhalmaza véges.) A definícióból közvetlenül adódik:

29. Tétel. Egy véges T és V halmazokkal rendelkező A=(Q, T, V, q 0, d, f) Mealy automata akkor és csak akkor indukálja a φ:T *  → V * automata leképezést, ha a φ- hez tartozó automata nyelvrendszer egybeesik az A- hoz tartozó kanonikus nyelvrendszerrel. ∎

Ebben a fejezetben eddig végig feltételeztük, hogy az T és V halmazok végesek. Most tovább szűkítjük vizsgálataink körét és az állapothalmaz végességét is kikötjük. Más szóval, a továbbiakban csupán véges automatákkal foglalkozunk. Arra vonatkozóan, hogy milyen leképezések indukálhatóak véges automatákkal, érvényes a következő tétel.

30. Tétel. (Véges Automaták Alaptétele) A véges T és V halmazok esetén egy φ:T *  → V * automata leképezés akkor és csak akkor indukálható véges automatában, ha a φ- hez tartozó H φ automata nyelvrendszer minden eleme reguláris nyelv.

Bizonyítás. A szükségesség igazolásához tegyük fel, hogy T és V véges halmazok, s a φ:T *  → V * automata leképezés indukálható a véges A=(Q, T, V, q 0, d, f) automatával. Akkor Gill tétele szerint van olyan véges A '=(Q ', T, V, q 0, d ', g) Moore-automata is, mely ugyancsak indukálja a φ leképezést. Minden bV- re legyen Q' b ={q '∈Q '|g(q ')=b}, azaz legyen Q' b az A ' automata b állapotjelű állapotainak halmaza és jelölje L' b azt a nyelvet, mely az A ''=(Q ', T, q 0, d ') kimenő jel nélküli automatában a Q' b halmazzal előállítható (vagyis a (Q ', T, q 0, d ', Q' b ) által elfogadott nyelv), azaz legyen L' b =L A '' Q' b . Mivel az A véges, az analízisre vonatkozó tétel alkalmazásával kapjuk, hogy L' b minden bV- re reguláris nyelv. Ezért a szükségességhez azt kell csupán megmutatni, hogy ha H φ ={L b |bV}, akkor minden bV- ra L b =L' b . Ez pedig a következő számolással adódik: wL b ⇔≫φ(w)=b⇔≫φ A (w)=bφ A '(w)=b⇔≫g(d(q 0, w))=b⇔≫d(q 0, w)∈Q' b wL' b . Ezzel a szükségesség igazolását befejeztük.

Az elegendőség kimutatásához tegyük fel, hogy a véges T és V halmazokra megadott φ:T *  → V * automata leképezés H φ ={L b 1 , …, L b m } automata nyelvrendszeréhez létezik olyan A ''=(Q, T, q 0, d) iniciális kimenő jel nélküli automata, amelyben az L b 1 , …, L b m nyelvek rendre előállíthatók a Q állapothalmaz Q 1, …, Q m részhalmazaival. Bővítsük ki az A ''=(Q, T, q 0, d) automatát az A=(Q, T, V, q 0, d, g) kimenő jellel bíró Moore-automatává a g jelfüggvény következő definíciójával: Legyen g(q 0) egy tetszőlegesen rögzített V- beli elem, továbbá legyen minden qQ i , i∈{1, …, m} mellett g(q)=b i . Minthogy H φ automata nyelvrendszer, azért a Q 1, …, Q m páronként diszjunkt halmazok. Így g definíciója egyértelmű. Megmutatjuk, hogy az A Moore-automata indukálja a φ leképezést. Ehhez az előzőek alapján elegendő kimutatni, hogy a K A ={R b i |b i V} kanonikus nyelvrendszer egybeesik a H φ automata nyelvrendszerrel. Ez pedig a következő számolással adódik: wR b i ⇔≫φ A (w)=b i ⇔≫g(d(q 0, w))=b i ⇔≫d(q 0, w)∈Q i wL b i .

Ezzel az elegendőség igazolását is befejeztük. ∎

Az analízisre és a szintézisre vonatkozó tétel a most bebizonyított tétellel együtt - konstruktív bizonyításukat konkrét esetre alkalmazva - algoritmust szolgáltat az analízis és a szintézis eredeti értelemben vett megoldására.

5.47. példa - Automata nyelvrendszer

Legyen T={a, b} és az T *∖{λ} félcsoportot bontsuk fel a következő módon:


L 1 legyen az összes, csupa a jelből álló szavak halmaza,

L 2 legyen az összes, csupa b jelből álló szavak halmaza,

L 3 legyen az összes többi szavak halmaza.

Ez a nyelvrendszer automata nyelvrendszer, mégpedig minden eleme reguláris nyelv, hiszen nyilván L 1=a a *, L 2=b b *, L 3=(a a * b+b b * a)(a+b)*. Vegyük észre, hogy a véges automaták szintézisénél tárgyalt Gluskov módszert épp erre a három nyelvre alkalmaztuk, így az ott kapott 9 állapotú A automata játszhatja az alaptétel elegendősége bizonyítása során A ''- vel jelölt kimenő jel nélküli automata szerepét. Ha most ezt az automatát kimenő jellel bíró automatává egészítjük ki úgy hogy az L 1, L 2, L 3 nyelvekhez rendre hozzárendeljük az u, v, w szimbólumokat, s a jelfüggvényt az alaptétel elegendősége bizonyításánál látott módon definiáljuk, akkor az alábbi Moore-automatához jutunk, mely az L 1, L 2, L 3 nyelvrendszerrel megadott leképezést indukálja. Az Aufenkamp-Hohn algoritmussal meghatározható az ezen leképezést indukáló minimális (négy állapotú) automata. Ennek ismertetését mellőzzük.

A tetsz. u v u w w v w w
  q 0 q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8
a q 1 q 3 q 5 q 3 q 7 q 7 q 5 q 7 q 7
b q 2 q 4 q 6 q 4 q 8 q 8 q 6 q 8 q 8

Eredményeink alapján algoritmust tudunk konstruálni annak eldöntésére is, hogy két reguláris kifejezés ekvivalens-e, azaz egy és ugyanazon reguláris nyelv reguláris kifejezéseiről van-e szó. Gluskov módszerével ugyanis mindkettőhöz meg tudunk szerkeszteni egy-egy iniciális kimenő jel nélküli automatát, melyek állapotaik alkalmas részhalmazával ezeket a nyelveket felismerik. Vehetjük a véges determinisztikus felismerő automatákat és minimalizálhatjuk őket. Ezután már csak azt kell eldöntenünk, hogy a kapott két automata állapot-izomorf-e egymással úgy, hogy egy alkalmas izomorfizmus a kezdőállapotokat egymáshoz rendeli. Véges automatákra ez nyilván eldönthető. Ha igen a válasz, akkor a két reguláris kifejezés ekvivalens, különben nem.

A fentiek alapján algoritmus adható egy reguláris kifejezéssel megadott reguláris nyelvhez a legrövidebb vele ekvivalens reguláris kifejezés meghatározásához is: Végig kell vizsgálni az összes, a mi reguláris kifejezésünknél nem hosszabb olyan reguláris kifejezéseket, melyek összes változói legalább egyszer előfordulnak az adott reguláris kifejezésben. A vizsgálat során ki kell választani azokat a reguláris kifejezéseket, melyek ekvivalensek az adott reguláris kifejezéssel, s a legrövidebbet (vagy ha több ilyen van akkor az egyik legrövidebbet) meg kell tartanunk.

Cél lehet egy adott reguláris kifejezéshez megtalálni egy vele ekvivalens olyan reguláris kifejezést, melyben terminálisok a lehető legkevesebbszer fordulnak elő. Nyilván csak azok a reguláris kifejezések jöhetnek számításba, melyekben a terminálisok előfordulási száma nem nagyobb, mint az adott reguláris kifejezésben. Ha ez a szám és a zárójel-párok száma ismert, akkor felső korlátot tudunk adni a vizsgálandó reguláris kifejezések hosszára. Nevezetesen, legfeljebb annyi iterációs jelet tartalmazhat, mint a zárójel-párok száma plusz a terminálisok előfordulási száma. Az összeadásjelek és a szorzások számának összege ennél az értéknél kisebb, mert a legelső előfordulás elé (ami vagy egy kezdő zárójel, vagy egy terminális) nem teszünk műveleti jelet. Belátható, hogy a nem elhagyható zárójelpárok száma kisebb mint a terminálisok előfordulási száma. Vagyis ha csupán nem elhagyható zárójeleket tételezünk fel, a minimális terminális előfordulási számú reguláris kifejezés (vagy ha több van akkor ezek egyike) meghatározható.