Klasifikace abstraktních automatů

V níže uvedeném textu jsou použity následující zápisy:

S

je množina stavů automatu

X

- vstupní abeceda

Y

- výstupní abeceda

\delta

- přechodová funkce

\lambda

- výstupní funkce

$S$ , , jsou konečné neprázdné množiny $X$ $Y$

Klasifikace automatů podle logických vlastností přechodových a výstupních funkcí

Podle způsobu tvorby výstupních funkcí se rozlišují automaty Mealy a Moore .

Machine Miles

Ve stroji Mealy určuje výstupní funkce hodnotu výstupního symbolu podle klasického schématu abstraktního automatu . Matematický model Mealyho automatu a schéma rekurentních vztahů se neliší od matematického modelu a schématu rekurentních relací abstraktního automatu . Lze tedy uvést následující definici: $\lambda$

Konečný deterministický automat typu Mealy je sada pěti objektů

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

kde , a jsou konečné neprázdné množiny a a jsou zobrazení tvaru: $S$ $X$ $Y$ $\delta$ $\lambda$

$\delta :S\krát X\šipka doprava S$ a $\lambda :S\krát X\šipka doprava Y$

se spojením prvků množin a v abstraktním čase = 0, 1, 2, … rovnicemi: $S$ $X$ $Y$ $T$

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

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

(Zobrazení a byly pojmenovány jako přechodové funkce a výstupní funkce automatu A). $\delta$ $\lambda$

Vlastností automatu Mealy je, že výstupní funkce je dvouargumentová a symbol ve výstupním kanálu je detekován pouze tehdy, je-li ve vstupním kanálu symbol . Funkční schéma se neliší od schématu abstraktního automatu . $y(t)$ $x(t)$

Kulomet Moore

Závislost výstupního signálu pouze na stavu je reprezentována v Mooreových strojích . V Moorově automatu určuje výstupní funkce hodnotu výstupního symbolu pouze z jednoho argumentu – stavu automatu. Tato funkce se také nazývá funkce návěští, protože přiřazuje návěští každému stavu automatu na výstupu.

Konečný deterministický automat Mooreova typu je sada pěti objektů: ${\boldsymbol {A=(S,X,Y,\delta ,\mu ),}}$

kde , , a — odpovídají definici automatu typu Mealy a je zobrazením tvaru: μ : S → Y , $S$ $X$ $Y$ $\delta$ $\mu$

se závislostí stavů a výstupních signálů v čase podle rovnice:

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

Charakteristickým rysem automatu Moore je, že symbol ve výstupním kanálu existuje po celou dobu, kdy je automat ve stavu . $y(t)$ $Svatý)$

Pro jakýkoli stroj Moore existuje stroj Mealy, který implementuje stejnou funkci . A naopak: pro každý automat Mealy existuje odpovídající automat Moore (možná s časovým posunem, tj. ) $\mu (s(t+1))=\lambda (s(t),x(t)),t\in T$ .

Jiné třídy automatů

Je zajímavé vyčlenit speciální třídy automatů, jejichž matematické modely jsou založeny pouze na dvou nositelích algebry.

Nechť |X| = 1 . Potom má matematický model a systém rekurentních vztahů tvar:

${\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))$

kde a jsou konečné neprázdné množiny stavů a výstupních signálů a a jsou zobrazení výše uvedeného typu. $S$ $Y$ ${\boldsymbol {\gamma ))$ ${\bold symbol {\mu ))$

Znakem fungování takového automatu je generování sekvence symbolů výstupního slova pouze v závislosti na sekvenci stavů automatu.

Takový automat se nazývá autonomní konečný deterministický automat .

Pro každý počáteční stav a přirozené číslo definuje automat B dvě sekvence: ${\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 {).}}$

Konečný automat lze reprezentovat jako převodník vstupních sekvencí na výstupní. V tomto případě lze výstupní sekvence považovat za generované a vstupní sekvence za reprezentované. Výstupní sekvence automatu určují množinu slov generovaných tímto automatem. Autonomní CDA se nazývá generování , pokud je jím generované slovo reprezentováno jako výstupní sekvence a taková sekvence se nazývá generovaná tímto automatem.

Nechte _ Potom má matematický model a systém rekurentních vztahů tvar: ${\boldsymbol {Y=\emptyset ))$

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

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

Klasifikace automatů podle charakteru odpočítávání diskrétního času

Podle povahy diskrétního počítání času se automaty dělí na synchronní a asynchronní.

V synchronních automatech jsou časy, ve kterých stroj čte vstupní signály, určeny vynucenými časovacími signály. Po dalším synchronizačním signálu, s přihlédnutím ke „čtenému“ a v souladu se vztahy pro fungování automatu, dojde k přechodu do nového stavu a na výstupu je vydán signál, po kterém může automat vnímat další hodnotu vstupního signálu.

Asynchronní konečný automat čte vstupní signál nepřetržitě, a proto může v reakci na dostatečně dlouhý vstupní signál o konstantní hodnotě x, jak vyplývá ze vztahů pro činnost stroje, několikrát změnit stav a vydat odpovídající počet výstupních signálů, dokud se nedostane do stabilního stavu, který již nelze tímto vstupním signálem měnit.

Viz také

Odkazy

Automaty Moore a Mealy Archivovány 24. srpna 2019 na Wayback Machine // Wikisummaries ITMO University
Dvoucestný deterministický konečný stavový stroj archivován 25. října 2019 na Wayback Machine // Wikisummaries ITMO University