Clasificarea automatelor abstracte

Următoarele notații sunt utilizate în textul de mai jos:

S

este ansamblul stărilor automatelor

X

- introducerea alfabetului

Y

- alfabet de ieșire

\delta

- functie de tranzitie

\lambda

- functie de iesire

$S$ , , sunt mulțimi finite nevide $X$ $Y$

Clasificarea automatelor în funcție de proprietățile logice ale funcțiilor de tranziție și de ieșire

După modul în care sunt formate funcțiile de ieșire , se disting automatele Mealy și Moore .

Machine Miles

În mașina Mealy , funcția de ieșire determină valoarea simbolului de ieșire conform schemei clasice a unui automat abstract . Modelul matematic al automatului Mealy și schema relațiilor de recurență nu diferă de modelul matematic și schema relațiilor de recurență a unui automat abstract . Astfel, se poate da următoarea definiție: $\lambda$

Un automat determinist finit de tip Mealy este un set de cinci obiecte

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

unde , și sunt mulțimi finite nevide și și sunt mapări de forma: $S$ $X$ $Y$ $\delta$ $\lambda$

$\delta :S\time X\rightarrow S$ și $\lambda :S\time X\rightarrow Y$

cu legătura elementelor mulțimilor , iar în timp abstract = 0, 1, 2, … prin ecuațiile: $S$ $X$ $Y$ $T$

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

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

(Mapările și au fost denumite, respectiv, funcțiile de tranziție și funcțiile de ieșire ale automatului A). $\delta$ $\lambda$

O caracteristică a automatului Mealy este că funcția de ieșire are două argumente, iar simbolul din canalul de ieșire este detectat numai dacă există un simbol în canalul de intrare . Schema funcțională nu diferă de schema unui automat abstract . $YT)$ $x(t)$

Mitralieră Moore

Dependenţa semnalului de ieşire numai de stare este reprezentată în maşinile Moore . În automatul Moore, funcția de ieșire determină valoarea simbolului de ieșire dintr-un singur argument - starea automatului. Această funcție este numită și funcție de etichetă, deoarece atribuie o etichetă fiecărei stări a automatului la ieșire.

Un automat determinist finit de tip Moore este un set de cinci obiecte: ${\boldsymbol {A=(S,X,Y,\delta,\mu),}}$

unde , , și — corespund definiției unui automat de tip Mealy și este o mapare de forma: μ : S → Y , $S$ $X$ $Y$ $\delta$ $\mu$

cu dependența stărilor și a semnalelor de ieșire în timp prin ecuația:

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

O caracteristică a automatului Moore este că simbolul din canalul de ieșire există tot timpul în timp ce automatul este în stare . $YT)$ $Sf)$

Pentru orice mașină Moore, există o mașină Mealy care implementează aceeași funcție . Și invers: pentru orice automat Mealy, există un automat Moore corespunzător (eventual cu o schimbare în timp, adică ) $\mu (s(t+1))=\lambda (s(t),x(t)),t\in T$ .

Alte clase de automate

Este interesant să evidențiem clase speciale de automate ale căror modele matematice se bazează pe doar doi purtători de algebră.

Fie |X| = 1 . Atunci modelul matematic și sistemul de relații de recurență au forma:

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

unde și sunt seturi finite nevide de stări și semnale de ieșire și și sunt mapări de tipul de mai sus. $S$ $Y$ ${\boldsymbol {\gamma })$ ${\bold symbol {\mu ))$

O caracteristică a funcționării unui astfel de automat este generarea unei secvențe de simboluri ale cuvântului de ieșire numai în funcție de succesiunea stărilor automatului.

Un astfel de automat se numește automat determinist finit autonom .

Pentru fiecare stare inițială și număr natural, automatul B definește două secvențe: ${\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 {).}}$

Un automat finit poate fi reprezentat ca un convertor de secvențe de intrare în cele de ieșire. În acest caz, secvențele de ieșire pot fi considerate ca generate, iar secvențele de intrare ca fiind reprezentate. Secvențele de ieșire ale unui automat determină setul de cuvinte generate de acest automat. Un CDA autonom se numește generator dacă cuvântul generat de acesta este reprezentat ca o secvență de ieșire, iar o astfel de secvență se numește generat de acest automat.

Lasă . Atunci modelul matematic și sistemul de relații de recurență au forma: ${\boldsymbol {Y=\emptyset ))$

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

${\boldsymbol {\delta:S\time X\rightarrow S})$

Clasificarea automatelor în funcție de natura numărătoarei inverse a timpului discret

În funcție de natura numărării în timp discret, automatele sunt împărțite în sincrone și asincrone.

În mașinile cu stare sincronă, momentele la care mașina citește semnalele de intrare sunt determinate de semnale de sincronizare forțate. După următorul semnal de sincronizare, ținând cont de „citire” și în conformitate cu relațiile de funcționare a automatului, are loc o tranziție la o nouă stare și este emis un semnal la ieșire, după care automatul poate percepe următorul valoarea semnalului de intrare.

O mașină asincronă cu stări finite citește continuu semnalul de intrare și, prin urmare, ca răspuns la un semnal de intrare suficient de lung cu o valoare constantă x, poate, după cum rezultă din relațiile de funcționare a mașinii, să schimbe starea de mai multe ori, emitând numărul adecvat de semnale de ieșire, până când acesta intră într-o stare stabilă, care nu mai poate fi schimbată de acest semnal de intrare.

Vezi și

Link -uri

Automate Moore și Mealy Arhivate 24 august 2019 la Wayback Machine // Wikisumaries ale Universității ITMO
Mașină de stări finite deterministă bidirecțională Arhivată pe 25 octombrie 2019 la Wayback Machine // ITMO University Wikisummaries