Klassificering af abstrakte automater

Følgende notationer er brugt i teksten nedenfor:

S

er sættet af automattilstande

x

- indtast alfabet

Y

- output alfabet

\delta

- overgangsfunktion

\lambda

- output funktion

$S$ , , er endelige ikke-tomme sæt $x$ $Y$

Klassificering af automater i henhold til de logiske egenskaber ved overgangs- og outputfunktioner

Afhængigt af den måde, outputfunktionerne dannes på, skelnes Mealy- og Moore -automaterne .

Machine Miles

I Mealy-maskinen bestemmer output -funktionen værdien af outputsymbolet i henhold til det klassiske skema for en abstrakt automat . Den matematiske model for Mealy-automaten og skemaet for gentagelsesrelationer adskiller sig ikke fra den matematiske model og skemaet for gentagelsesrelationer for en abstrakt automat . Således kan følgende definition gives: $\lambda$

En endelig deterministisk Mealy-type automat er et sæt af fem objekter

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

hvor , og er endelige ikke-tomme sæt, og og er afbildninger af formen: $S$ $x$ $Y$ $\delta$ $\lambda$

$\delta :S\ gange X\højrepil S$ og $\lambda :S\ gange X\højrepil Y$

med forbindelsen af elementerne i mængderne , og i abstrakt tid = 0, 1, 2, … ved ligningerne: $S$ $x$ $Y$ $T$

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

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

(Kortlægningerne og er blevet navngivet henholdsvis overgangsfunktionerne og udgangsfunktionerne for automaten A). $\delta$ $\lambda$

Et træk ved Mealy-automaten er, at udgangsfunktionen er to-argument, og symbolet i udgangskanalen detekteres kun, hvis der er et symbol i indgangskanalen . Det funktionelle skema adskiller sig ikke fra skemaet for en abstrakt automat . $y(t)$ $x(t)$

Moore maskingevær

Udgangssignalets afhængighed kun af tilstanden er repræsenteret i Moore - maskiner . I Moore-automaten bestemmer output-funktionen værdien af outputsymbolet ud fra kun ét argument - automatens tilstand. Denne funktion kaldes også etiketfunktionen, da den tildeler en etiket til hver tilstand af automaten ved udgangen.

En endelig deterministisk Moore-type automat er et sæt af fem objekter: ${\boldsymbol {A=(S,X,Y,\delta ,\mu ),}}$

hvor , , og — svarer til definitionen af en Mealy-type automat , og er en kortlægning af formen: μ : S → Y , $S$ $x$ $Y$ $\delta$ $\mu$

med afhængigheden af tilstande og udgangssignaler i tid ved ligningen:

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

Et træk ved Moore-automaten er, at symbolet i udgangskanalen eksisterer hele tiden, mens automaten er i tilstanden . $y(t)$ $s(t)$

For enhver Moore-maskine er der en Mealy-maskine, der implementerer samme funktion . Og omvendt: for enhver Mealy-automat er der en tilsvarende Moore-automat (muligvis med et tidsskift, dvs. ) $\mu (s(t+1))=\lambda (s(t),x(t)),t\in T$ .

Andre klasser af automater

Det er interessant at udskille specielle klasser af automater , hvis matematiske modeller er baseret på kun to bærere af algebra.

Lad |X| = 1 . Så har den matematiske model og systemet med gentagelsesrelationer formen:

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

hvor og er endelige ikke-tomme sæt af tilstande og udgangssignaler , og og er afbildninger af ovennævnte type. $S$ $Y$ ${\boldsymbol {\gamma ))$ ${\fed symbol {\mu ))$

Et træk ved funktionen af en sådan automat er genereringen af en sekvens af symboler af outputordet, kun afhængigt af sekvensen af tilstande af automaten.

En sådan automat kaldes en autonom finit deterministisk automat .

For hver begyndelsestilstand og naturligt tal definerer automaten B to sekvenser: ${\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 {).}}$

En endelig automat kan repræsenteres som en konverter af inputsekvenser til output. I dette tilfælde kan outputsekvenserne betragtes som genererede, og inputsekvenserne som repræsenteret. Udgangssekvenserne for en automat bestemmer det sæt af ord, der genereres af denne automat. En autonom CDA kaldes generering , hvis ordet genereret af den er repræsenteret som en outputsekvens, og en sådan sekvens kaldes genereret af denne automat.

Lad . Så har den matematiske model og systemet med gentagelsesrelationer formen: ${\boldsymbol {Y=\emptyset ))$

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

${\boldsymbol {\delta :S\ gange X\højrepil S))$

Klassificering af automater i henhold til arten af nedtællingen af diskret tid

I henhold til arten af diskret tidstælling er automater opdelt i synkrone og asynkrone.

I synkrone tilstandsmaskiner bestemmes tidspunkterne, hvorpå maskinen læser inputsignaler, af tvungne timingsignaler. Efter det næste synkroniseringssignal, under hensyntagen til "læsningen" og i overensstemmelse med relationerne til automatens funktion, sker der en overgang til en ny tilstand, og der udsendes et signal ved udgangen, hvorefter automaten kan opfatte den næste værdien af indgangssignalet.

En asynkron finite state-maskine læser indgangssignalet kontinuerligt, og derfor kan den, som svar på et tilstrækkeligt langt indgangssignal med en konstant værdi x,, som følger af relationerne for maskinens drift, skifte tilstand flere gange, og udstede passende antal udgangssignaler, indtil den kommer i en stabil tilstand, som ikke længere kan ændres af dette indgangssignal.

Klassificering af abstrakte automater