Statsmaskin med utgång

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 april 2021; kontroller kräver 3 redigeringar .

En ändlig utgångsautomat är en variant av en deterministisk ändlig automat , kompletterad med ett utgångsalfabet och en utgångsfunktion.

Definition

Det finns olika sätt att definiera en finita tillståndsmaskin med en utgång. Till exempel kan en finit automat med en utgång specificeras som ett ordnat sju element av vissa uppsättningar [1] : , där $M=(V,W,Q,q_{0},F,\delta ,\mu )$

$V$ är inmatningsalfabetet (dess element är inmatningssymboler );
$W$ är utgångsalfabetet (dess element är utgångssymboler );
$F$ är en uppsättning tillstånd för en finit automat med en utgång;
$q_{0}$ är initialtillståndet för den finita automaten med utgång;
$F$ — en icke-tom uppsättning slut-/sluttillstånd , vars varje element kallas slut-/sluttillståndet för en finit automat med utgång;
$\delta$ är kartläggningen av övergångsfunktionen , ; $\delta :Q\times V\rightarrow Q$
$\mu$ — visningsfunktion för utgångar , . $\mu :Q\times V\rightarrow W$

Funktionen kallas en gränsligt deterministisk funktion. $V^{*}\rightarrow W^{*}$

Strukturell syntesproblem

Denna uppgift liknar uppgiften att implementera en boolesk funktion genom en krets av funktionella element . Till skillnad från en krets av funktionella element för implementering av en boolesk funktion, måste denna krets innehålla fördröjningselement som tillåter lagring av information om automatens nuvarande tillstånd [2] . För att lösa problemet med struktursyntes sammanställs en tabell för övergångsfunktionerna och utgångarna från en finit automat med en utgång, sedan byggs en strukturell tabell i vilken varje ingångs- och utmatningssymbol och varje tillstånd ersätts med sin binära kod och som ställer in en boolesk operator [3] .

Anteckningar

↑ Diskret matematik, 2006 , sid. 552.
↑ Diskret matematik, 2006 , sid. 556.
↑ Diskret matematik, 2006 , sid. 560.

Litteratur

Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 sid. — ISBN 5-7038-2886-4 .
Kenneth R. Beesley och Lauri Karttunen . Finita tillståndsmorfologi . — CSLI Publications , 2003.