4.8. Egyéb véges automaták

Az automataelméleti fejezet zárásaként röviden bemutatunk néhány további véges automata fajtát.

4.8.1. Irányítható automaták

Vegyünk egy űrszondát, ami a Hold körül kering, ennek következtében időnként elveszítjük vele a kapcsolatot. A műholdat egy véges állapotú rendszernek tekintve, ha tudjuk milyen állapotban van, akkor megfelelő input jeleket küldve neki mi irányítjuk. Amikor viszont nincs kapcsolatunk vele, nincs ellenőrzésünk alatt, így nem tudjuk hogy milyen állapotba kerül. Az ilyen esetekre kínálnak megoldást az irányítható automaták.

6. Definíció. Az A=(Q, V, d) automatát irányíthatónak vagy szinkronizálhatónak neveztük, ha van olyan uV bemenő szó és qQ állapot, hogy minden pQ állapot esetén d(p, u)=z q, ahol zQ *. Az ilyen u szót az A automata irányító vagy szinkronizáló szavának, q- t pedig az A automata irányított vagy szinkronizált állapotának nevezzük. ★

Tehát, visszatérve az űrszondánkra, mindig amikor felvesszük vele kapcsolatot először egy irányító szót küldünk neki, és ezután tudjuk vele elvégeztetni a kívánt tevékenységeket. Természetesen az egyik kézenfekvő megoldás, ha pl. egy adott jelre (egybetűs irányítószóra) az automata irányított állapotba kerül, másrészt viszont, ha limitált ábécével kommunikálunk, nem biztos hogy érdemes egy betűt erre a célra fenntartani.

Jan Černý (ejtsd: csernyi) 1964-ben írt dolgozatában fogalmazta meg következő sejtését az irányítható automatákról.

1. Sejtés. Ha egy n állapotú automata irányítható, akkor a legrövidebb szinkronizáló szavának hossza nem több, mint (n-1)2.

A Černý sejtés az automaták algebrai elméletének egyik legrégebbi megoldatlan problémája.

4.8.2. Automata több kezdőállapottal

Az üresszavas átmeneteket is megengedve könnyen belátható, hogy az automata ugyanazt a nyelvosztályt fogadja el, akkor is ha több kezdőállapotot engedünk meg. A következő módszerrel egyszerűen konstruálhatunk egy kezdőállapottal rendelkező üresszavas átmenetes véges automatát, amely ugyanazt a nyelvet fogadja el, mint az eredeti több kezdőállapottal rendelkező automatánk.

Legyen (Q, I, T, d, F) adott, ahol Q az állapotok véges halmaza, IQ a kezdőállapotok halmaza, T az input ábécé, d az átmenetfüggvény, F pedig a végállapotok halmaza. Vegyünk fel egy új q 0 állapotot, amely nem eleme a Q- nak. Legyen Q '=Q∪{q 0} és legyen a d ' származtatva a d- ből oly módon, hogy a d átmenetein kívül legyen benne q 0- ból átmenet az üresszó hatására minden qI állapotba. Ekkor a (Q ', q 0, T, d ', F) automata megfelel az állításunknak: pontosan ugyanazt a nyelvet fogadja el, mint az eredeti és pontosan egy kezdőállapottal rendelkezik.

4.8.3. Átlátszóbetűs felismerő automata

A felismerő automatának az átlátszóbetűs változatát, melynek elfogadóereje jóval túlmutat a korábban ismertetett felismerő automatáén 2010-ben Friedrich Otto és Nagy Benedek vezették be. A hagyományos automatának ebben a kiterjesztésében minden állapotra megadhatunk a T bemenő ábécének egy olyan részhalmazát, amit az automata az adott állapotban nem lát. Az inputszalagon így az automata az első nem átlátszó betűt olvassa (törli), ami így nem biztos, hogy a legelső betű. Az olvasott betűnek megfelelő átmenet utáni állapotban más betűk lehetnek átlátszóak, így lehetőség van az előző állapotban nem látott - akár a törölt betűt megelőző - betűk elolvasására is. Az automata mindig az adott állapotban látszó legelső betűt tudja olvasni, ily módon nem feltétlenül a hagyományos balról jobbra sorrendben feldolgozva az inputot.

7. Definíció. Átlátszóbetűs (nemdeterminisztikus) felismerő automatának nevezzük az A=(Q, I, T, $, t, d, F) rendezett hetest, ahol Q az állapotok véges halmaza, IQ a kezdőállapotok halmaza, T az inputábécé, $∉T a szalagvége jel, t:Q → 2 T átlátszósági függvény, d:Q×T → 2 Q az állapotátmenet-függvény, FQ pedig a végállapotok halmaza. Minden qQ állapotra a t(q)- ban szereplő betűk átlátszóak, az automata ebben az állapotban ezeket a betűket nem látja. ★

Az automata működése a következő: először nemdeterminisztikusan választunk egy qI állapotot. A kezdőkonfiguráció: (q 0, w$). Legyen w=a 1 a 2a n ahol n ≥ 1, és a 1, a 2, …, a n T. Ekkor megkeressük az első olyan betűt balról amely nem átlátszó az adott állapotban, legyen w=u a v olyan, hogy at(q 0), u∈(t(q 0))*. Ekkor a d(q 0, a)- ból nemdeterminisztikusan választunk egy q ' állapotot és a következő konfiguráció (q ', u v$) lesz. Ha d(q 0, a)=∅, akkor az automata megáll anélkül hogy elfogadna. Ha w∈(t(q 0))*, akkor az automata a $ szimbólumot látja és megáll. Ha a gép a $ jelet látja, és az aktuális állapot végállapot, akkor elfogadja az inputot.

4.15. példa - Átlátszóbetűs elfogadó automata

Az {a, b, c} ábécé felett azokat a szavakat tartalmazó nyelv elfogadása, amelyekben az a- k, a b- k és a c- k száma megegyezik pl. a következő átlátszóbetűs felismerő automatával megy: ({q 0, q 1, q 2, q 3}, {q 0}, {a, b, c}, $, t, d, {q 3}), ahol t(q 0)={b, c}, t(q 1)={a, c}, t(q 2)={a, b}, t(q 3)=∅ és d(q 0, a)={q 1}, d(q 1, b)={q 2}, d(q 2, c)={q 0, q 3}, minden más esetben a d értéke az üres halmaz. ★


A jegyzetben a későbbiekben nemvéges (de végesen definiálható, illetve leírható) automatákról is lesz szó.