Absztrakt automaták osztályozása

Az alábbi szövegben a következő jelöléseket használjuk:

S

az automata állapotok halmaza

x

- beviteli ábécé

Y

- kimeneti ábécé

\delta

- átmeneti funkció

\lambda

- kimeneti funkció

$S$ , , véges, nem üres halmazok $x$ $Y$

Az automaták osztályozása az átmeneti és kimeneti függvények logikai tulajdonságai szerint

A kimeneti függvények kialakításának módja szerint megkülönböztetjük a Mealy és Moore automatákat .

Machine Miles

A Mealy gépben a kimeneti függvény egy absztrakt automata klasszikus sémájának megfelelően határozza meg a kimeneti szimbólum értékét . A Mealy automata matematikai modellje és az ismétlődési relációk sémája nem különbözik egy absztrakt automata matematikai modelljétől és ismétlődési relációinak sémájától . Így a következő definíció adható: $\lambda$

Egy véges determinisztikus Mealy-típusú automata öt objektum halmaza

${\boldsymbol {A=(S,X,Y,\delta ,\lambda )))$ ,

ahol , és véges, nem üres halmazok, és a és a forma leképezései: $S$ $x$ $Y$ $\delta$ $\lambda$

$\delta :S\times X\rightarrow S$ és $\lambda :S\szor X\jobbra Y$

halmazok elemeinek összekapcsolásával , és absztrakt időben = 0, 1, 2, … az egyenletekkel: $S$ $x$ $Y$ $T$

${\boldsymbol {s(t+1)=\delta (s(t),x(t)),}}$

${\boldsymbol {y(t)=\lambda (s(t),x(t)),t\in T))$

(A és a leképezéseket az A automata átmeneti függvényeinek, illetve kimeneti függvényeinek nevezték el). $\delta$ $\lambda$

A Mealy automata jellemzője, hogy a kimeneti függvény kétargumentumos, és a kimeneti csatornában lévő szimbólumot csak akkor észleli a rendszer, ha a bemeneti csatornában van szimbólum . A funkcionális séma nem különbözik egy absztrakt automata sémájától . $y(t)$ $x(t)$

Moore géppuska

A kimenő jelnek csak az állapottól való függését a Moore - gépek ábrázolják . A Moore automatában a kimeneti függvény csak egy argumentumból – az automata állapotából – határozza meg a kimeneti szimbólum értékét. Ezt a függvényt címkefüggvénynek is nevezik, mivel a kimeneten az automata minden állapotához címkét rendel.

Egy véges determinisztikus Moore-típusú automata öt objektum halmaza: ${\boldsymbol {A=(S,X,Y,\delta ,\mu ),}}$

ahol , , és — egy Mealy-típusú automata definíciójának felel meg , és a következő alakú leképezés: μ : S → Y , $S$ $x$ $Y$ $\delta$ $\mu$

az állapotok és a kimenő jelek időbeli függésével az egyenlet szerint:

${\boldsymbol {y(t)=\mu (s(t)),t\in T))$ .

A Moore-automata jellemzője, hogy a kimeneti csatornában lévő szimbólum mindaddig létezik, amíg az automata állapotban van . $y(t)$ $utca)$

Minden Moore géphez létezik egy Mealy gép, amely ugyanazt a funkciót valósítja meg . És fordítva: minden Mealy automatához van egy megfelelő Moore automata (esetleg időeltolásos, azaz ) $\mu (s(t+1))=\lambda (s(t),x(t)),t\in T$ .

Egyéb automata osztályok

Érdekes kiemelni az automaták speciális osztályait, amelyek matematikai modelljei az algebra mindössze két hordozóján alapulnak.

Legyen |X| = 1 . Ekkor a matematikai modell és az ismétlődési összefüggésrendszer a következőképpen alakul:

${\boldsymbol {B=(S,Y,\gamma ,\mu )))$ ,

$\gamma :S\rightarrow S$

$\lambda :S\rightarrow Y$

${\boldsymbol {s(t+1)=\gamma (s(t)),}}$

${\boldsymbol {y(t)=\mu (s(t)),t\in T))$

ahol és az állapotok és kimeneti jelek véges, nem üres halmazai , és a és a fenti típusú leképezések. $S$ $Y$ ${\boldsymbol {\gamma ))$ ${\bold symbol {\mu ))$

Egy ilyen automata működésének sajátossága, hogy a kimeneti szó szimbólumsorozatát csak az automata állapotsorától függően állítják elő.

Az ilyen automatát autonóm véges determinisztikus automatának nevezzük .

A B automata minden kezdeti állapothoz és természetes számhoz két sorozatot határoz meg: ${\displaystyle {\boldsymbol {s(0)={s_{i))))_{0))$ $t$

${\boldsymbol {s_{i}}}_{0},{\boldsymbol {s_{i}}}_{1}{\boldsymbol {=\gamma ({s_{i}}}}_{ 0}{\boldsymbol {),{s_{i}}}}_{2}{\boldsymbol {=\gamma ({s_{i}}}}_{1}{\boldsymbol {),..., {s_{i))))_{t}{\boldsymbol {=\gamma ({s_{i))))_{t-1}{\boldsymbol {),}}$

${\boldsymbol {\mu ({s_{i))))_{0}{\boldsymbol {),\mu ({s_{i))))_{1}{\boldsymbol {),\ mu ({s_{i)))_{2}{\boldsymbol {),...,\mu ({s_{i))))_{t-1}{\boldsymbol {).}}$

Egy véges automata úgy ábrázolható, mint a bemeneti szekvenciák konvertálója kimeneti sorozatokká. Ebben az esetben a kimeneti sorozatokat generáltnak, a bemeneti szekvenciákat pedig reprezentáltnak tekinthetjük. Egy automata kimeneti sorozatai határozzák meg az automata által generált szavak halmazát. Egy autonóm CDA-t generálásnak nevezünk, ha az általa generált szót kimeneti sorozatként ábrázoljuk, és az ilyen sorozatot ez az automata generáltnak nevezzük.

Hadd . Ekkor a matematikai modell és az ismétlődési összefüggésrendszer a következőképpen alakul: ${\boldsymbol {Y=\emptyset ))$

${\boldsymbol {C=(X,S,\delta );}}$

${\boldsymbol {\delta :S\times X\rightarrow S))$

Az automaták osztályozása a diszkrét idő visszaszámlálásának jellege szerint

A diszkrét időszámlálás természete szerint az automatákat szinkronra és aszinkronra osztják.

A szinkron állapotú gépekben a bemeneti jelek beolvasásának időpontját kényszerített időzítő jelek határozzák meg. A következő szinkronizáló jel után, figyelembe véve a "beolvasást" és az automata működési összefüggéseinek megfelelően, átmenet történik egy új állapotba, és a kimeneten egy jelet adnak ki, amely után az automata érzékeli a következőt. a bemeneti jel értéke.

Egy aszinkron véges állapotú gép folyamatosan olvassa a bemeneti jelet, ezért egy kellően hosszú, állandó x értékű bemeneti jelre reagálva a gép működésére vonatkozó összefüggésekből következően többször is állapotot tud változtatni, kiadva a megfelelő számú kimeneti jelet, amíg stabil állapotba nem kerül, amelyet ezzel a bemeneti jellel már nem lehet megváltoztatni.

Lásd még

Linkek

Moore és Mealy automata archiválva 2019. augusztus 24-én a Wayback Machine -nél // ITMO Egyetem Wikiösszefoglalók
Kétirányú determinisztikus véges állapotú gép archiválva 2019. október 25-én a Wayback Machine -nél // ITMO Egyetem Wikiösszefoglalók