Klassificering av abstrakta automater

Följande notationer används i texten nedan:

S

är uppsättningen av automattillstånd

X

- mata in alfabetet

Y

- utgående alfabet

\delta

- övergångsfunktion

\lambda

- utgångsfunktion

$S$ , , är ändliga icke-tomma uppsättningar $X$ $Y$

Klassificering av automater enligt de logiska egenskaperna hos övergångs- och utdatafunktioner

Beroende på hur utgångsfunktionerna bildas, särskiljs Mealy- och Moore -automaterna .

Machine Miles

I Mealy-maskinen bestämmer utgångsfunktionen värdet på utgångssymbolen enligt det klassiska schemat för en abstrakt automat . Den matematiska modellen för Mealy-automaten och schemat för återkommande relationer skiljer sig inte från den matematiska modellen och schemat för återkommande relationer för en abstrakt automat . Således kan följande definition ges: $\lambda$

En ändlig deterministisk automat av Mealy-typ är en uppsättning av fem objekt

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

där , och är ändliga icke-tomma uppsättningar, och och är mappningar av formen: $S$ $X$ $Y$ $\delta$ $\lambda$

$\delta :S\ gånger X\högerpil S$ och $\lambda :S\ gånger X\högerpil Y$

med kopplingen av elementen i mängderna , och i abstrakt tid = 0, 1, 2, … genom ekvationerna: $S$ $X$ $Y$ $T$

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

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

(Mappningarna och har benämnts, respektive övergångsfunktionerna och utgångsfunktionerna för automaten A). $\delta$ $\lambda$

En egenskap hos Mealy-automaten är att utgångsfunktionen är tvåargumenterad och symbolen i utgångskanalen detekteras endast om det finns en symbol i ingångskanalen . Det funktionella schemat skiljer sig inte från schemat för en abstrakt automat . $y(t)$ $x(t)$

Moore maskingevär

Beroendet av utsignalen endast av tillståndet är representerat i Moore -maskiner . I Moore-automaten bestämmer utdatafunktionen värdet på utdatasymbolen från endast ett argument - automatens tillstånd. Denna funktion kallas även etikettfunktionen, eftersom den tilldelar en etikett till varje tillstånd av automaten vid utgången.

En finit deterministisk automat av Moore-typ är en uppsättning av fem objekt: ${\boldsymbol {A=(S,X,Y,\delta ,\mu ),}}$

där , , och — motsvarar definitionen av en automat av Mealy-typ , och är en avbildning av formen: μ : S → Y , $S$ $X$ $Y$ $\delta$ $\mu$

med beroendet av tillstånd och utsignaler i tid genom ekvationen:

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

En egenskap hos Moore-automaten är att symbolen i utgångskanalen existerar hela tiden medan automaten är i tillståndet . $y(t)$ $s(t)$

För alla Moore-maskiner finns det en Mealy-maskin som implementerar samma funktion . Och vice versa: för alla Mealy-automater finns det en motsvarande Moore-automat (möjligen med en tidsförskjutning, dvs. ) $\mu (s(t+1))=\lambda (s(t),x(t)),t\in T$ .

Andra klasser av automater

Det är intressant att peka ut speciella klasser av automater vars matematiska modeller är baserade på endast två bärare av algebra.

Låt |X| = 1 . Då har den matematiska modellen och systemet med återfallsrelationer 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))$

där och är ändliga icke-tomma uppsättningar av tillstånd och utsignaler , och och är avbildningar av ovanstående typ. $S$ $Y$ ${\boldsymbol {\gamma ))$ ${\bold symbol {\mu ))$

Ett särdrag för funktionen hos en sådan automat är genereringen av en sekvens av symboler för utgående ord endast beroende på sekvensen av tillstånden hos automaten.

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

För varje initialtillstånd och naturligt tal definierar automaten B två 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 finit automat kan representeras som en omvandlare av ingångssekvenser till utdata. I detta fall kan utmatningssekvenserna betraktas som genererade och ingångssekvenserna som representerade. Utmatningssekvenserna för en automat bestämmer uppsättningen av ord som genereras av denna automat. En autonom CDA kallas generering om ordet som genereras av den representeras som en utdatasekvens, och en sådan sekvens kallas genererad av denna automat.

Låt . Då har den matematiska modellen och systemet med återfallsrelationer formen: ${\boldsymbol {Y=\emptyset ))$

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

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

Klassificering av automater enligt arten av nedräkningen av diskret tid

Beroende på karaktären av diskret tidsräkning delas automater in i synkrona och asynkrona.

I synkrona tillståndsmaskiner bestäms tidpunkterna vid vilka maskinen läser insignaler av påtvingade tidsstyrningssignaler. Efter nästa synkroniseringssignal, med hänsyn till "avläsningen" och i enlighet med relationerna för automatens funktion, sker en övergång till ett nytt tillstånd och en signal avges vid utgången, varefter automaten kan uppfatta nästa värdet på ingångssignalen.

En asynkron maskin med ändligt tillstånd läser insignalen kontinuerligt, och därför, som svar på en tillräckligt lång insignal med ett konstant värde x, kan den, som följer av förhållandena för maskinens drift, ändra tillstånd flera gånger och utfärda lämpligt antal utsignaler, tills den går in i ett stabilt tillstånd, vilket inte längre kan ändras av denna insignal.

Se även

Länkar

Moore och Mealy automata Arkiverad 24 augusti 2019 på Wayback Machine // ITMO University Wikisummaries
Two-Way Deterministic Finite State Machine Arkiverad 25 oktober 2019 på Wayback Machine // ITMO University Wikisummaries