Mașină de stat cu ieșire

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 aprilie 2021; verificările necesită 3 modificări .

Un automat finit de ieșire este o variație a unui automat finit determinist , completat cu un alfabet de ieșire și o funcție de ieșire.

Definiție

Există diferite moduri de a defini o mașină cu stări finite cu o ieșire. De exemplu, un automat finit cu o ieșire poate fi specificat ca șapte elemente ordonate ale unor mulțimi [1] : , unde $M=(V,W,Q,q_{0},F,\delta,\mu)$

$V$ este alfabetul de intrare (elementele sale sunt simboluri de intrare );
$W$ este alfabetul de ieșire (elementele sale sunt simboluri de ieșire );
$Q$ este un set de stări ale unui automat finit cu o ieșire;
$q_{0}$ este starea inițială a automatului finit cu ieșire;
$F$ — un set nevid de stări finale/finale , fiecare element fiind numit starea finală/finală a unui automat finit cu o ieșire;
$\delta$ este maparea funcției de tranziție , ; $\delta:Q\time V\rightarrow Q$
$\mu$ — funcția de afișare a ieșirilor , . $\mu:Q\time V\rightarrow W$

Funcția se numește funcție deterministă mărginită. $V^{*}\rightarrow W^{*}$

Problemă de sinteză structurală

Această sarcină este similară cu sarcina de a implementa o funcție booleană de către un circuit de elemente funcționale . Spre deosebire de un circuit de elemente funcționale pentru implementarea unei funcții booleene, acest circuit trebuie să conțină elemente de întârziere care să permită stocarea informațiilor despre starea curentă a automatului [2] . Pentru a rezolva problema sintezei structurale, se întocmește un tabel pentru funcțiile de tranziție și ieșirile unui automat finit cu o ieșire, apoi se construiește un tabel structural în care fiecare simbol de intrare și de ieșire și fiecare stare sunt înlocuite cu codul lor binar și care setează un operator boolean [3] .

Literatură

Belousov A. I., Tkachev S. B. Matematică discretă. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .
Kenneth R. Beesley și Lauri Karttunen . Morfologia stărilor finite . — Publicații CSLI , 2003.