Mať jeden vstup, jeden výstup a byť v každom okamihu v jednom stave z mnohých možných. Toto zariadenie prijíma symboly jednej abecedy na vstupe a na výstupe vytvára symboly (vo všeobecnom prípade) inej abecedy.

Formálne je abstraktný automat definovaný ako päťka

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

Obmedzenie počtu parametrov abstraktného automatu definovalo taký pojem ako konečný automat.

Fungovanie automatu spočíva v generovaní dvoch sekvencií: sekvencie po sebe nasledujúcich stavov automatu $\backslash boldsymbol(s\_1s\_2s\_3...)$ a sekvencie výstupných symbolov $\backslash boldsymbol(y\_1y\_2y\_3...)$, čo pre postupnosť znakov $\backslash boldsymbol(x\_1x\_2x\_3...)$ odvíjajú sa v momentoch diskrétneho času t = 1, 2, 3, … Momenty diskrétneho času sa nazývajú cykly.

Fungovanie automatu v diskrétnych časoch t možno opísať systémom rekurentných vzťahov: $\backslash boldsymbol(s(t+1)=\backslash delta(s(t),x(t));)$

$\backslash boldsymbol(y(t)=\backslash lambda(s(t),x(t)).)$

Na objasnenie vlastností abstraktných automatov bola zavedená klasifikácia.

Abstraktné automaty tvoria základnú triedu diskrétnych modelov ako model sám o sebe, tak aj ako základná súčasť Turingových strojov, zásobníkových automatov, konečných automatov a iných konvertorov informácií.

Napíšte recenziu na článok "Abstraktný automat"

Úryvok charakterizujúci abstraktný automat

Panovník sa s úsmevom otočil k jednému zo svojho sprievodu, ukázal na kolegov Absheronov a niečo mu povedal.

Kutuzov v sprievode svojich pobočníkov jazdil tempom za karabinierom.
Keď prešiel pol verst na konci kolóny, zastavil sa pri opustenom dome (pravdepodobne bývalej krčme) blízko rázcestia dvoch ciest. Obe cesty klesali z kopca a po oboch pochodovali jednotky.
Hmla sa začala rozchádzať a na neurčito, vo vzdialenosti dvoch verst už bolo vidieť nepriateľské jednotky na protiľahlých kopcoch. Vľavo dole sa streľba stala počuteľnejšou. Kutuzov sa prestal rozprávať s rakúskym generálom. Princ Andrei, ktorý stál trochu vzadu, sa na nich zahľadel a chcel požiadať pobočníka o ďalekohľad a obrátil sa k nemu.
"Pozri, pozri," povedal tento pobočník a nepozeral sa na vzdialenú armádu, ale dolu z hory pred sebou. - Sú Francúzi!
Dvaja generáli a adjutanti začali fajku chytať a ťahať ju jeden z druhého. Všetky tváre sa zrazu zmenili a na všetkých bolo vidieť zdesenie. Francúzi mali byť dve míle od nás, no objavili sa zrazu, nečakane pred nami.
- Je to nepriateľ?... Nie!... Áno, pozri, on... pravdepodobne... Čo je toto? bolo počuť hlasy.
Princ Andrej jednoduchým okom Videl som dole vpravo hustý stĺp Francúzov, ktorý stúpal smerom k Apšerončanom, nie ďalej ako päťsto krokov od miesta, kde stál Kutuzov.
„Je to tu, prišiel rozhodujúci moment! Prišlo to ku mne, “pomyslel si princ Andrei, narazil na koňa a išiel do Kutuzova. "Musíme zastaviť Apsheroňanov," kričal, "Vaša Excelencia!" Ale v tom istom momente bolo všetko zahalené dymom, bolo počuť streľbu z blízka a naivne vystrašený hlas, dva kroky od princa Andreja, zakričal: "No, bratia, sabat!" A ako keby bol tento hlas príkazom. Pri tomto hlase sa všetko rozbehlo.
Zmiešané, stále sa zväčšujúce davy utekali späť na miesto, kde pred piatimi minútami prechádzali vojská okolo cisárov. Bolo nielen ťažké zastaviť tento dav, ale nebolo možné nepohnúť sa späť spolu s davom.
Bolkonskij sa s ňou len snažil držať krok a obzeral sa okolo seba, zmätený a neschopný pochopiť, čo sa pred ním deje. Nesvitskij s nahnevaným pohľadom, červený a nepodobný sebe, kričal Kutuzovovi, že ak teraz neodíde, pravdepodobne ho vezmú do zajatia. Kutuzov stál na tom istom mieste a bez odpovede si vytiahol vreckovku. Z líca mu tiekla krv. Princ Andrei sa k nemu pretlačil.
- Si zranený? spýtal sa, sotva ovládol chvenie spodnej čeľuste.
- Rany tu nie sú, ale kde! - povedal Kutuzov, pritlačil si vreckovku na zranené líce a ukázal na utečencov. - Zastavte ich! skríkol a zároveň, pravdepodobne presvedčený, že ich nemožno zastaviť, narazil do koňa a išiel doprava.

26. apríla 2010 o 19:06 hod

Samoštúdium obvodov. Abstraktný automat. Časť 2

• Elektronika pre začiatočníkov

Článok je napísaný, zozbieraný a vysádzaný. Ďakujem mu veľmi pekne.
V predchádzajúcom článku som sa snažil rozložiť všetky základné definície a princípy, aby bol tento článok čo najprehľadnejší. Všetko nesedí, preto vám dôrazne odporúčam, aby ste sa oboznámili s týmito súbormi:
Základ, Základ2, Minimalizácia. Neskôr v tomto článku som nechal niekoľko vysvetliviek napísaných kurzívou.

V tomto článku sa pokúsim vysvetliť v jednoduchom jazykučo je abstraktný automat, spôsoby jeho reprezentácie. Keďže teória automatov je plná matematiky a komplexná, skúsim napísať ľudský jazyk aby nepripravený čitateľ pochopil, čo je v stávke.

Elektronické digitálne obvody možno formálne rozdeliť do 2 tried:

• Kombinované schémy (CS) - nemajú pamäť. Výstupný signál sa vytvára v závislosti od kombinácie vstupné dáta v pevnom časovom bode (s prihliadnutím na oneskorenie pri konverzii signálu) Kombinované obvody, ich typy a konštrukčné princípy môžu byť témou na samostatný článok a príklady zahŕňajú: Riadené zbernice, multiplexory a demultiplexory, dekodéry a kódovače , prevodníky kódov, kombinačné počítadlá a sčítačky atď.
• Pamäťové obvody - algoritmus ich práce závisí od stavu vstupov a Pamäť(čo bolo v predchádzajúcich chvíľach času). Tieto schémy sú popísané pomocou teórie konečných automatov. Budeme o nich hovoriť ďalej.

Inými slovami, prvá trieda sú logické zariadenia, ktoré spracovávajú vstupný signál. Druhé prvky majú pamäť a reagujú na signál v závislosti od údajov do nich zadaných.

Abstraktný automat

Stroj bude musieť implementovať niektoré funkcie, ktoré sú nastavené vývojárom. Môže to byť jednoduchá sčítačka, môže implementovať akúkoľvek mikroinštrukciu procesora, môže vyberať slová z Náhodný vstup do pamäťe alebo analyzovať výraz.
AT všeobecný pohľad Bez toho, aby sme zachádzali do podrobností, možno abstraktný automat znázorniť takto:

Alebo, ak prejdeme od ilustrácie k matematickému popisu:
A=

Označenia:

1. Sada (A) je množina hodnôt na fyzických vstupoch automatu. Na vstupe v našom prípade bude nejaká postupnosť vysokých a nízke úrovne napätia, ktoré budú kódovať logické nuly a jednotky.
2. Sada (B) je množina hodnôt na fyzických výstupoch automatu.
3. Sada (C) - sada, ktorá predstavuje vnútorný stav automatu - pamäte. Pre budúcnosť sa bude označovať C0 počiatočný stav stroj.
4. δ = X × Z → Z sú prechodové funkcie automatu, jednoznačne určujú stav ai, do ktorého automat prechádza zo stavu aj.
5. λ = X × Z → Y sú výstupné funkcie, určujú, čo je na výstupe automatu v závislosti od vstupov a vnútorného stavu.

δ a λ nie sú v diagrame zobrazené pre vizuálne zjednodušenie.

Takýto automat funguje diskrétne v čase, to znamená, že hodnoty vstupov, výstupov a vnútorný stav automatu sa menia v diskrétnych časoch.
Vo všeobecnosti sme teda opísali, čo je abstraktný automat. Príkladom takéhoto automatu môže byť spúšť, počítačový register alebo sčítačka.

Existujú 2 typy strojov:

1. Múčne stroje. Popísané sústavou rovníc:
   c(t) = 5(a(t), c(t-1));
   b(t) = λ(a(t), c(t-1)).
2. Mooreove automaty. Popísané rovnicami:
   c(t) = 5(a(t), c(t-1));
   b(t) = λ(a(t), c(t)).

Ako je vidieť stav automatu c(t) v aktuálnom čase je funkciou jeho stavu v predchádzajúcom čase a vstupného signálu.
Automaty sa líšia typom výstupnej funkcie. V stroji Mealy je výstupný signál určený vstupným signálom a(t) a stavom stroja v predchádzajúcom čase c(t-1). Výstupný signál Moorovho stroja je určený dvojicou vstupného signálu a(t) a stavom in tento moment c(t).
Možno tiež poznamenať, že z jedného typu sa dá prejsť na druhý a naopak a pri prechode z automatu Mealy na automat Moore sa počet vnútorné stavy automat zostane rovnaký a pri spätnom prechode sa môže zvýšiť počet vnútorných stavov. Nebudeme sa tým podrobne zaoberať, vzhľadom na to, že sme syntetizovali (nakreslili graf) automat takého typu, aký je potrebný.
Takže toto je koniec materiálu. Skúsme popísať automaty.

Tie. Automat typu Mealy generuje výstupný signál, keď sa jeho vstup zmení v závislosti od jeho predchádzajúceho stavu. V tomto prípade trvanie výstupného signálu nezávisí od trvania vstupu, ale iba od jeho prítomnosti. V automatoch typu Moore je výstupný signál závislý od stavu automatu v aktuálnom čase, t.j. automat bude produkovať určitý výstupný signál, kým nezmení svoj stav.

Metódy nastavenia automatov

Ako sme zistili v prvej časti, automat je množina vstupných a výstupných abeced, množina vnútorných stavov a funkcií, ktoré určujú prechody a výstupy. Zvyčajne však funkcie δ a λ nie sú dané a správanie automatu je potrebné opísať inak.

Existujú dva hlavné spôsoby, ako definovať automat:

1. S pomocou grafov.
2. Pomocou skokových tabuliek a výstupov.

počíta

Graf automatu je orientovaný súvislý graf, ktorého vrcholy symbolizujú vnútorné stavy automatu a oblúky symbolizujú prechody z jedného stavu do druhého.

V prípade grafu Mealy sú na oblúkoch uvedené podobné a výstupné písmená. Výstupné písmená sú napísané nad oblúkmi, čo symbolizuje, že výstupný stav závisí od stavu automatu v predchádzajúcom časovom okamihu.

V prípade grafu Moorovho automatu sú na oblúkoch napísané iba vstupné písmená, zatiaľ čo výstupné písmená sú uvedené v blízkosti vrcholov.

Dôležitý bod: Ak z každého vrcholu vychádza toľko oblúkov, koľko je vstupných písmen, potom sa automat nazýva kompletný. Inými slovami, ak sú prechody definované z každého vrcholu pre každé vstupné písmeno. V našich príkladoch stroj Miles je plný a automat Mura - čiastočná.
A ešte niečo: Ak je z jedného vrcholu viac oblúkov ako vstupných písmen (čiže 2 a viac oblúkov s rovnakými vstupnými písmenami), tak sa takýto automat tzv. nedeterministický. To sa môže stať pri vytváraní formalizovaného popisu a potom bude potrebné vykonať prechod na deterministický stroj, ale to nie je vždy možné. Chýba mi aj popis tohto procesu, keďže som okamžite nakreslil deterministický automat.
To je všetko o grafoch.

Skokové a výstupné tabuľky.

Grafy sú pre človeka vizuálnejšie a tabuľky sú pre stroj. Každý automat môže byť reprezentovaný ako prechodová a výstupná tabuľka (TOT). V TPV sú riadky internými stavmi automatu a stĺpce sú vstupné písmená.
Zostrojme TPV pre naše Mealyho a Mooreove grafy. Ak nie je definované žiadne vstupné alebo výstupné písmeno, namiesto neho sa vloží pomlčka. Ak štát nie je definovaný, potom platí rovnaké jednoduché pravidlo.

Gróf Miley TPV

V Mileovom TPV sú prechody a výstupy zaznamenané v každej bunke. Ak je napríklad automat v stave C0 a na vstup príde písmeno a1, tak prejde do stavu C1 a na výstupe sa objaví písmeno b3.

Gróf Moore TPV

Pre Mooreov graf je vytvorená tabuľka označených prechodov. Pre výstupné písmená je priradený ďalší stĺpec.
V bunke pod vstupným písmenom je napísané, do akého stavu sa automat dostane, v bunke úplne vpravo - aké výstupné písmeno vráti.

Príklad syntézy automatov

Pomocou abstraktných automatov môžete opísať takmer čokoľvek. Môžete opísať činnosť digitálneho obvodu alebo môžete opísať analyzátor alebo lexikálny analyzátor. Skúsme popísať spúšťač – prečo nie automat?
Na nastavenie grafu potrebujete slovný popis algoritmu spúšťača. Čítanie:

Kódujeme vstupnú a výstupnú abecedu:
A = (a0, a1), kde a0 je logická 1 na vstupe R, a1 je logická 1 na vstupe S.
B = (b0, b1), kde b0 je logická 0 na výstupe Q, b1 je logická 1 na výstupe Q.
Zostavíme graf Mealyho automatu:


Tu je taká vtipná cheburaška :-). Teraz môžeme zostaviť prechodovú a výstupnú tabuľku:

Ak túto tabuľku zapíšeme transformáciou dohovorov do skutočných, dostaneme tabuľku, ktorá je tabuľkou spúšťacích prechodov. Potom sa to dá zjednodušiť:

Výslednú funkciu aplikujeme na Veitchovu mapu a minimalizujeme ju:

Napíšeme, čo sa stalo:

Zostavíme schému podľa funkcie (Urobili ste si domácu úlohu?).

Digitálny (diskrétny) automat možno interpretovať ako zariadenie, ktoré prijíma, ukladá a konvertuje diskrétne informácie podľa nejakého algoritmu. Z určitého pohľadu môžu automaty zahŕňať tak reálne zariadenia (počítače, živé organizmy a pod.), ako aj abstraktné systémy (matematické stroje, axiomatické teórie

všeobecná teória Automaty sa delia na abstraktné a štrukturálne. Rozdiel medzi nimi spočíva v tom, že abstraktná teória, abstrahujúca od štruktúry automatu (t. j. nezaujímajúca sa o spôsob jeho konštrukcie), študuje iba správanie automatu vzhľadom na vonkajšie prostredie. Abstraktná teória automatov je teda blízka teórii algoritmov, v podstate ide o jej ďalšie detaily. Na rozdiel od abstraktnej teórie sa štrukturálna teória zaujíma tak o štruktúru samotného automatu, ako aj o štruktúru vstupných akcií a reakcií automatu na ne. Štrukturálna teória študuje metódy konštrukcie automatov, metódy kódovania vstupných akcií a reakcií automatu. Štrukturálna teória automatov je teda pokračovaním a ďalší vývoj abstraktná teória. Na základe aparátu booleovských funkcií a na abstraktnej teórii automatov uvádza štrukturálna teória účinné odporúčania o vývoji skutočných výpočtových zariadení.

Abstraktný digitálny automat A je definovaný množinou piatich objektov, kde je množina vstupných signálov automatu A (vstupná abeceda automatu A); - množina stavov automatu A (abeceda stavov automatu - množina výstupných signálov automatu A (výstupná abeceda automatu A); - prechodová funkcia

automat A, ktorý špecifikuje zobrazenie, t.j. priradenie ľubovoľnej dvojici prvkov karteziánskeho súčinu množín, prvok množiny je výstupná funkcia automatu A, ktorá špecifikuje buď zobrazenie alebo zobrazenie.

Inými slovami, prechodová funkcia ukazuje, že automat A, ktorý je v určitom stave, keď sa objaví vstupný signál, prejde do určitého stavu. Ten možno zapísať aj ako výraz. Výstupná funkcia, ktorá špecifikuje mapovanie, ukazuje, že automat L, ktorý je v určitom stave, keď sa objaví vstupný signál, vytvára výstupný signál, ktorý možno zapísať ako

Podľa spôsobu generovania výstupnej funkcie sa rozlišujú tri typy abstraktných automatov: Mealyho automat, Mooreov automat, C-automat. V abstraktnom Mealyho automate výstupná funkcia X definuje mapovanie . V abstraktnom Mooreovom automate výstupná funkcia definuje mapovanie, v abstraktnom C-autome sú zavedené dve výstupné funkcie X, respektíve definujúce mapovanie. V tomto prípade je výstupná abeceda C-automatu buď

Ľubovoľný abstraktný automat Milan alebo Moore má jeden vstupný a jeden výstupný kanál (obr. 10.1). Ľubovoľný abstraktný C-automat má jeden vstupný a dva výstupné kanály (obrázok 10.2).

Existujú plne definované a čiastočné automaty.

Plne definovaný je abstraktný digitálny automat, ktorého prechodová funkcia a výstupná funkcia sú definované pre všetky dvojice

Abstraktný digitálny automat sa nazýva čiastočný, ak prechodová funkcia alebo výstupná funkcia alebo obe tieto funkcie nie sú definované pre všetky páry.

Abstraktný digitálny automat sa nazýva počiatočný, ak je množine jeho stavov 5 pridelený špeciálny počiatočný stav, t. j. počiatočný abstraktný automat je určený množinou šiestich objektov. Výber na množine počiatočného stavu je vysvetlený čisto praktickými úvahami súvisiace s často vznikajúcou potrebou fixovať podmienky pre štart automatu.

O abstraktnom automate sa hovorí, že pracuje v diskrétnom čase automatu a prechody zo stavu do stavu sú okamžité. V každom okamihu diskrétneho času je automat v nejakom stave z množiny stavov, ak je automat počiatočný, tak v počiatočnom okamihu je vždy v počiatočnom stave . Automat je momentálne v stave akceptovať na vstupe písmeno vstupnej abecedy v súlade s výstupnou funkciou X, zároveň vydá písmeno výstupnej abecedy a v súlade s prechodová funkcia prejde na

stav Podľa definície abstraktného automatu je Mealyho automat v tomto prípade charakterizovaný systémom rovníc:

Moorov automat – sústavou rovníc;

a C-automat - systémom rovníc:

Inými slovami, ak sa počiatočný abstraktný automat Mealy alebo Moore, nastavený na počiatočný stav, privádza písmeno po písmene do určitej sekvencie písmen vstupnej abecedy vstupného slova, potom sa na výstupe automatu postupne objavia písmená výstupná abeceda výstupného slova. V prípade C-automatu sa na jeho výstupoch objavia dve sekvencie: v abstraktnom C-automate sú všetky bonusy vydávané výstupným signálom, keď je stroj v stave

Na úrovni abstraktnej teórie sa teda fungovanie digitálneho automatu chápe ako transformácia vstupných slov na výstupné slová.

Pojem stav v definícii abstraktného automatu bol zavedený z dôvodu, že väčšina reálnych procesov, ktoré sú riadené skutočne vybudovanými digitálnymi automatmi, si pre svoj správny priebeh vyžaduje včasnú znalosť prehistórie vývoja procesov. Inými slovami, výstupný signál vydaný automatom v danom časovom okamihu je určený nielen vstupnou činnosťou na automate, ale aj stavom, v ktorom sa automat v danom časovom okamihu nachádzal. signál semaforu“, potom v každom okamihu, aby sa organizovala správna prevádzka stroja, je okrem vstupného signálu „prepnite semafor“ potrebné mať informácie o polohe semafora v predchádzajúcom okamihu času. Tieto informácie poskytuje prítomnosť rôznych stavov abstraktného automatu. Abstraktné digitálne automaty zodpovedajúce zavedenej definícii abstraktného automatu sa nazývajú aj abstraktné automaty s pamäťou, keďže existencia množiny rôznych stavov v automate je možná len vtedy, ak má automat pamäť.

Množstvo procesov riadených skutočnými automatmi si pre svoj správny priebeh nevyžaduje včasnú znalosť praveku vývoja procesu. V automatických strojoch, ktoré riadia takéto procesy,

Tabuľka 10.1

výstupný signál je určený len vstupnou činnosťou na automate. Tieto automaty sú definované na abstraktnej úrovni reprezentácie pomocou triple , kde výstupná funkcia definuje mapovanie a nazývajú sa abstraktné automaty s triviálnou pamäťou alebo kombinačné automaty. Najjednoduchší analóg kombinovaného automatu možno čítať ako obyčajnú elektrickú lampu za predpokladu, že vstupná akcia je stlačenie tlačidla "Zapnuté" a výstupný signál je zapálenie žiarovky.

Abecedy vstupov, stavov a výstupov automatov sú špecifikované ako obyčajné množiny, napríklad výpisom ich prvkov. Prechodové a výstupné funkcie je možné špecifikovať maticovo, graficky a analyticky. Preto môže byť akýkoľvek abstraktný automat definovaný tromi spôsobmi! matice, graficky a analyticky

Pri maticovej metóde je automat reprezentovaný buď dvomi tabuľkami: prechodovou tabuľkou a výstupnou tabuľkou, alebo spojovacou maticou.Prechodová tabuľka špecifikuje mapovanie, t.j. určuje prechodovú funkciu automatu, výstupná funkcia stroja.

Tabuľka prechodov ľubovoľného plne definovaného abstraktného automatu je skonštruovaná nasledovne. Stĺpce tabuľky sú označené písmenami vstupnej abecedy automatu a riadky tabuľky sú označené písmenami abecedy stavov automatu. V bunke prechodovej tabuľky umiestnenej na priesečníku stĺpca označeného vstupným signálom a riadku označeného stavom sa nastavuje stav, ktorý je výsledkom prechodu automatu zo stavu pod vplyvom vstupu signál, ktorý je určený výrazom Príklad, tabuľku prechodov nejakého abstraktného plne definovaného automatu so vstupnou abecedou a abecedou stavov uvádza tab. 10.1. Ak je abstraktný automat čiastočný, potom sa do bunky jeho tabuľky prechodov umiestnenej na priesečníku stĺpca označeného vstupným signálom a riadku označeného stavom umiestni pomlčka (za predpokladu, že prechod zo stavu pod vplyvom vstupný signál nie je definovaný) a akékoľvek vstupné slovo vedúce k špecifikovanému prechodu je zakázané. Vyplnenie zvyšku buniek je podobné ako v prípade plne definovaného automatu. Príklad tabuľky prechodov pre nejaký abstraktný čiastočný automat so vstupnou abecedou a abecedou stavov je uvedený v tabuľke. 10.2. Forma tabuľky prechodov nezávisí od typu daného automatu (Mooreov automat, Mealyho automat, C-automat). Výstupné tabuľky Moore, Mealy, C-automatu majú rozdiely. Výstupná tabuľka plne definovaného stroja Mealy je zostavená nasledovne. Identifikácia stĺpcov a riadkov a formát tabuľky zodpovedajú skokovej tabuľke plne definovaného automatu. V bunke výstupnej tabuľky

Tabuľka 10.2

Tabuľka 10.3

Tabuľka 10.4

nachádza sa na priesečníku stĺpca označeného vstupným signálom a riadku označeného stavom, nastavuje sa výstupný signál, ktorý produkuje stroj Mealy, pričom je v stave prítomnosti vstupného signálu, ktorý je určený výrazom tab. 10.3.

Výstupná tabuľka plne definovaného Moorovho automatu je konštruovaná jednoduchšie: každému stavu automatu je priradený vlastný výstupný signál. Príklad výstupnej tabuľky Moorovho stroja s abecedou stavov a výstupnou abecedou je uvedený v tabuľke 10.4.

Je zrejmé, že abstraktný plne definovaný C-automat je daný dvoma výstupnými tabuľkami, z ktorých prvá je výstupná tabuľka automatu Mealy a druhá je výstupná tabuľka Mooreovho automatu.

Ak je automat Mealy čiastočný, potom v niektorých bunkách jeho tabuľky výstupov môže byť pomlčka, ktorá označuje absenciu výstupného signálu. V tomto prípade je potrebné umiestniť pomlčku do tých buniek výstupnej tabuľky, ktoré zodpovedajú rovnakým bunkám s pomlčkou v tabuľke prechodov automatu Mealy. Ten je spôsobený tým, že ak je v parciálnom Mealyho automate dvojica ) a taká, že prechod zo stavu pod vplyvom vstupného signálu je nedefinovaný, tak, prirodzene, hodnota výstupného signálu pri takom (neexistujúci) prechod je tiež nedefinovaný. Príklad tabuľky výstupov parciálneho Mealyho automatu, daný prechodovou tabuľkou (tabuľka 10.2) s výstupnou abecedou, je uvedený v tabuľke. 10.5

Čiarky v niektorých bunkách výstupnej tabuľky čiastočného Moorovho automatu nesúvisia s čiarkami v bunkách jeho tabuľky prechodov. Je to dané tým, že výstupný signál Moorovho stroja závisí len od stavu, v ktorom sa stroj nachádza. Napríklad výstupná tabuľka čiastočného Mooreovho stroja daná tabuľkou prechodov (tabuľka 10.2),

Tabuľka 10.5

Tabuľka 10.6.

Tabuľka 10.7

môže byť prezentovaná aj ako tabuľka. 10.4, ak v každom zo svojich stavov stroj produkuje nejaký druh výstupného signálu a ako v tabuľke. 10.6, ak je hodnota výstupného signálu automatu pre niektoré stavy nedefinovaná.

V praxi sa prechodové a výstupné tabuľky automatu často spájajú do jednej tabuľky, ktorá sa nazýva označená tabuľka prechodov automatu. Označená tabuľka prechodov plne definovaného automatu Mealy, reprezentovaná tabuľkou prechodov (tabuľka 10.1) a výstupnou tabuľkou (tabuľka 10.3), je zhrnutá v tabuľke. 10.7. Označená tabuľka prechodov parciálneho Moorovho automatu (tab. 10.2) a výstupná tabuľka (tab. 10.4) sú zhrnuté v tabuľke. 10.8.

Okrem vyššie uvedených prechodových a výstupných tabuliek môže byť ľubovoľný abstraktný automat opísaný spojovacou maticou. Takýto popis je jednou z metód maticovej definície abstraktných automatov. Matica spojenia ľubovoľného abstraktného automatu je štvorcová a obsahuje toľko stĺpcov (riadkov), koľko je rôznych stavov uvažovaného automatu. Každý stĺpec (riadok) matice spojov je označený písmenom stavu automatu. Ak je automat počiatočný, potom prvý stĺpec vľavo a prvý riadok v hornej časti matice jeho spojení sú označené písmenom počiatočného stavu automatu , pod vplyvom ktorého je prechod automatu z Ak je abstraktný automat Milne špecifikovaný spojovacou maticou, potom je vedľa písmena vstupného signálu v zátvorkách uvedené písmeno výstupného signálu, ktorý stroj Mealy vytvára prechodom. 10.7 ) je znázornená na obr. 10.3.

Ak je spojovacia matica abstraktný Mooreov automat, výstupné signály označujú stavy automatu, ktoré identifikujú riadky spojovacej matice.

Tabuľka 10.8

o grafickým spôsobom abstraktné automaty pracovných miest sú reprezentované orientovanými grafmi; stavy automatu sú znázornené vrcholmi grafu a prechody medzi stavmi sú znázornené oblúkmi medzi príslušnými vrcholmi. V tomto prípade je každému oblúku grafu priradené určité písmeno vstupnej abecedy automatu, čo naznačuje, že tento prechod automatu sa uskutoční iba vtedy, keď sa objaví vstupný signál a každému vrcholu grafu je priradené písmeno zodpovedajúci stav automatu. Ak graf predstavuje automat Mila, výstupné signály automatu sú uvedené na oblúkoch grafu (podľa tabuľky výstupov automatu) vedľa písmena vstupného signálu. Príklad grafu Mealyho automatu definovaného tabuľkou prechodov (tabuľka 10.1) a výstupnou tabuľkou (tabuľka 10.3) je na obr. 10.4. Ak graf predstavuje Moorov automat, potom výstupné signály automatu sú umiestnené blízko vrcholov grafu (v súlade s tabuľkou výstupov automatu). Príklad grafu Moorovho automatu definovaného tabuľkou prechodov (tabuľka 10.2) a výstupnou tabuľkou (tabuľka 10.4) je na obrázku. 10.5.

Pri analytickej metóde nastavenia sú abstraktné automaty reprezentované štyrmi objektmi, kde špecifikuje mapovanie pre každý stav automatu. Inými slovami, v analytickom spôsobe špecifikácie pre každý stav automatu je uvedené mapovanie, ktoré je množinou všetkých trojíc a také, že pod vplyvom vstupného signálu automat vykoná prechod zo stavu do stavu, pri vydávaní výstupného signálu. spoločná definícia abstraktný automat, druhý je ekvivalentný popisu funkcií a X v súlade s výrazmi: Mapovanie je napísané takto:

Analytická úloha automatu Mealy, reprezentovaná vyznačenou tabuľkou prechodov (tabuľka 10.7), má nasledovnú podobu.

Zvážte ekvivalentnú transformáciu automatov. Ekvivalentné automaty sú tie, ktoré vyvolávajú rovnaké mapovanie z množiny slov vo vstupnej abecede do množiny slov vo výstupnej abecede. Uvažujme len o transformácii Moorovho automatu na jeho ekvivalentný Mealyho automat. Transformácia Mealyho automatu na ekvivalentný Mooreov automat je o niečo komplikovanejšia.

Prechod z Moorovho automatu na ekvivalentný Mealyho automat sa pohodlne vykonáva grafickou metódou špecifikácie automatov. V tomto prípade sa redukuje na prenos výstupného signálu daného Moorovým automatom v stave do oblúkov zahrnutých vo vrchole označenom písmenom V maticovej metóde sa prechodová tabuľka automatu Mealy zhoduje s prechodovou tabuľkou Moorovho automatu, a tabuľka výstupov automatu Mealy sa získa z jeho prechodovej tabuľky nahradením písmena stavu umiestneného na priesečníku stĺpca označeného vstupným signálom a riadkom za výstupný signál vydaný automatom Moore v r. štát

rozvoj skutočné stroje(zastúpené aspoň na úrovni základnej elektrické obvody) vyžaduje ich nastavenie najskôr na abstraktnej úrovni, po ktorej nasleduje prechod na štrukturálnu úroveň, ktorá zohľadňuje logické prvky použité v obvode automatu a prepojenia medzi nimi. V tejto súvislosti vyvstáva úloha syntetizovať abstraktný automat na základe nejakého počiatočného, ​​napríklad verbálneho opisu jeho činnosti. Existujúce algoritmy na syntézu abstraktných automatov sa pre zložitosť a ťažkopádnosť výpočtov v praxi zvyčajne nepoužívajú, a preto nie sú zahrnuté v učebnicovom materiáli. Pre lepšie pochopenie pojmu abstraktný automat a jeho definície tu však budeme uvažovať o príklade syntézy abstraktného automatu, založenej na čisto špekulatívnych úvahách.

Príklad. Zostavte abstraktný digitálny automat na ovládanie prepínania semafora za predpokladu, že na vstup automatu bude prijatý iba signál „prepnite semafor“. Tento signál označujeme písmenom a jeho absenciu písmenom.

Je zrejmé, že vstupná abeceda X takéhoto automatu bude pozostávať z dvoch písmen: zelená farba, potom zavedieme tri zodpovedajúce výstupné riadiace signály Tiež predpokladáme, že v momente spustenia činnosti je automat v stave Algoritmus činnosti je triviálny; Možné riešenie stroja Mealy je znázornené na obr. 10.6 a pre stroj Moore - na obr. 10.7. Pre (pre zjednodušenie predpokladáme, že v počiatočnom momente dáva Mooreov automat výstupný signál „zapni zelenú farbu“. Upozorňujeme, že na zostavenie grafu automatu je potrebné zadať štyri rôzne stavy. Počet stavov môže byť znížiť napríklad zvýšením počtu vstupných signálov automatu alebo rozšírením možností automatu v zmysle zapamätania si histórie vývoja riadiaceho procesu v čase (v uvažovanom príklade len moment vydania posledného výstupného signálu sa zapamätá).

Na záver poznamenávame, že uvažujeme len deterministické automaty, pre ktoré je splnená podmienka jednoznačnosti prechodov: automat, ktorý je v určitom stave, nemôže prejsť do viac ako jedného stavu pôsobením akéhokoľvek vstupného signálu. Automat špecifikovaný tabuľkou prechodov je vždy deterministický, pretože na priesečníku stĺpca a riadku tabuľky prechodov sa zaznamená iba jeden stav, ak je prechod definovaný, a ak prechod definovaný nie je, vloží sa pomlčka. Pokiaľ ide o grafickú metódu definovania automatu, podmienka jedinečnosti znamená, že dva alebo viac oblúkov označených rovnakým vstupným signálom nemôže vzniknúť zo žiadneho vrcholu v grafe automatu.

• 1.1 Základné pojmy
• Výkon
• Bibliografia

Úvod

Téma kontrolná práca v disciplíne „Aplikovaná teória digitálnych automatov“ – „Abstraktné digitálne automaty“.

Účelom práce je zoznámiť sa so základnými pojmami abstraktných digitálnych automatov; typy abstraktných automatov; spôsoby špecifikácie abstraktných automatov; prepojenie medzi modelmi Mealy a Moore; ekvivalentné automaty a ekvivalentné transformácie automatov; minimalizácia počtu vnútorných stavov automatu a Aufenkamp-Hohnov algoritmus.

1. Abstraktné digitálne automaty

1.1 Základné pojmy

Digitálny automat možno interpretovať ako zariadenie, ktoré prijíma, ukladá a konvertuje diskrétne informácie podľa nejakého algoritmu. K automatom možno z určitého pohľadu priradiť tak reálne zariadenia (počítače), ako aj abstraktné systémy (matematické modely).

Automat je diskrétny konvertor informácií schopný prijímať rôzne stavy, presúvať sa z jedného stavu do druhého pod vplyvom vstupných signálov a vytvárať výstupné signály.

Všeobecná teória automatov sa delí na abstraktné a štrukturálne.

Abstraktná teória automatov, odhliadnuc od štruktúry automatu (teda bez toho, aby sa zaujímala o spôsob jeho konštrukcie), študuje iba správanie automatu vo vzťahu k vonkajšiemu prostrediu. Abstraktná teória automatov je blízka teórii algoritmov, ktorá je v podstate jej ďalšou realizáciou.

Na rozdiel od abstraktnej teórie automatov sa štrukturálna teória automatov zaujíma ako o štruktúru samotného automatu, tak aj o štruktúru vstupných akcií a reakcií automatu na ne. Štrukturálna teória študuje metódy konštrukcie automatov, metódy kódovania vstupných akcií a reakcií automatov na ne. Štrukturálna teória automatov je pokračovaním a rozvojom abstraktnej teórie. Opierajúc sa o aparát booleovských funkcií a o abstraktnú teóriu automatov, štrukturálna teória dáva efektívne odporúčania pre vývoj skutočných výpočtových zariadení.

Abstraktný digitálny automat (DA) je matematický model diskrétneho riadiaceho zariadenia.

Abstraktné cieľové publikum je definované súborom pozostávajúcim zo šiestich prvkov:

S=(X,A,Y,ao),

kde:

X=(x1, x2,. xn) - množina vstupných signálov (vstupná abeceda);

Y=(y1, y2, ym) - množina výstupných signálov (výstupná abeceda);

А=( a0, a1, a2,. aN) - množina stavov (abeceda stavov);

ao - počiatočný stav (aoA);

- prechodová funkcia automatu, ktorá špecifikuje mapovanie (XxA) A, t.j. priradenie ľubovolnej dvojice prvkov karteziánskeho súčinu (XxA) prvku množiny A;

- výstupná funkcia automatu špecifikujúca buď mapovanie (XxA) Y alebo mapovanie AY.

Inými slovami, prechodová funkcia ukazuje, že automat S, ktorý je v určitom stave ajA, keď sa objaví vstupný signál xjX, prechádza do určitého stavu apA. Toto sa dá napísať:

ap= (ai,Xj).

Výstupná funkcia ukazuje, že automat S, ktorý je v určitom stave ajA, keď sa objaví vstupný signál xjX, vytvára výstupný signál ykY. Dá sa to napísať: уk = (ai , Xj).

Pojem stav bol do definície automatu zavedený z dôvodu, že sa často stáva nevyhnutnosťou popísať správanie systémov, ktorých výstupy závisia nielen od stavu vstupov v danom čase, ale aj od nejakého praveku, t.j. zo signálov, ktoré prišli na vstupy systému skôr. Stav len zodpovedá nejakej pamäti minulosti, čo umožňuje elimináciu času ako explicitnej premennej a vyjadrenie výstupných signálov ako funkcie stavov a vstupov v danom čase.

Abstraktný automat funguje v diskrétnom čase t=0,1,2,. a prechody zo stavu do stavu sú okamžité. V každom okamihu t diskrétneho času je automat v určitom stave a (t) z množiny A stavov automatu a v počiatočnom čase t=0 je vždy v počiatočnom stave ao. V čase t, ktorý je v stave a (t), je automat schopný vnímať signál x (t) X na vstupnom kanáli a vydávať signál y (t) = (a (t), x (t) )) na výstupnom kanáli, prechádza do stavu a (t+1) = = (a (t),x (t)). Závislosť výstupného signálu od vstupu a od stavu znamená, že obsahuje pamäť.

1.2 Typy abstraktných automatov

Podľa spôsobu generovania výstupnej funkcie sa rozlišujú tri typy abstraktných automatov: Mealyho automat, Mooreov automat, C-automat. Automat Mealy je charakterizovaný systémom rovníc:

y(t) = (a(t), x(t));

a(t+1) = q(a(t), x(t)). (1-1)

Mooreov automat - systém rovníc:

y(t) = (a(t));

a(t+1) = q(a(t), x(t)). (1-2)

C-stroj - sústava rovníc:

y=y1y2

y1(t) = (a(t),x(t));

Y2(t) = 2(a(t));

a (t+1) = q (a (t), x (t)).

Ľubovoľný abstraktný automat Mealy alebo Moore (obr. 1.1.) má jeden vstupný a jeden výstupný kanál. Ľubovoľný abstraktný C-automat má jeden vstupný a dva výstupné kanály (obr. 1.2.).

Obrázok 1.1 - Abstraktný automat

Obrázok 1.2 Abstraktný C-automat

Ak vstup abstraktného automatu Mealy alebo Moore, nastavený na počiatočný stav ao, dostane písmeno po písmene sekvenciu písmen vstupnej abecedy x(0), x(1),. je vstupné slovo, potom sa na výstupe automatu postupne objavia písmená výstupnej abecedy y (0), y (1). - výstupné slovo. V prípade C-automatu sa na jeho výstupoch objavia dve sekvencie: y1 (0), y1 (1),. a y2(0), y2(1), . V abstraktnom C-automate je výstupný signál y2 (t) = (a (t)) vysielaný po celú dobu, kým je automat v stave a (t). Výstupný signál y1 (t) = 11 (a (t), x (t)) je vydaný pri pôsobení vstupného signálu x (t), keď je C-automat v stave a (t).

Na úrovni abstraktnej teórie sa teda fungovanie digitálneho automatu chápe ako transformácia vstupných slov na výstupné slová.

Existujú plne definované a čiastočné automaty.

Abstraktný digitálny automat sa nazýva úplne definovaný, ak jeho prechodová funkcia alebo výstupná funkcia alebo obe tieto funkcie sú definované pre všetky dvojice prechodov (xi,aj).

Abstraktný digitálny automat sa nazýva čiastočný, ak jeho prechodová funkcia alebo výstupná funkcia alebo obe tieto funkcie nie sú definované pre všetky dvojice prechodov (xi,aj).

Abstraktný digitálny automat sa nazýva počiatočný, ak je na množine jeho stavov A priradený počiatočný stav ao.

1.3 Spôsoby definovania abstraktných automatov

Na nastavenie konečného automatu S je potrebné popísať všetky prvky množiny: S=( X,A,Y,ao). Existuje niekoľko spôsobov, ako nastaviť činnosť stroja, ale najčastejšie používané sú tabuľkové (maticové), grafické a analytické.

Pri tabuľkovej metóde je automat špecifikovaný dvomi tabuľkami: prechodovou tabuľkou a výstupnou tabuľkou alebo spojovacou maticou. Prechodová tabuľka ľubovoľného plne definovaného automatu je konštruovaná nasledovne: riadky tabuľky sú označené písmenami vstupnej abecedy automatu a stĺpce tabuľky sú označené písmenami stavovej abecedy automatu; V bunke tabuľky skokov umiestnenej na v priesečníku riadku označeného vstupným signálom xi a stĺpca označeného stavom aj sa nastaví stav ak, ktorý je výsledkom prechodu automatu zo stavu aj vplyvom vstupného signálu xi, ktorý je určený výrazom ak= (aj, xj).

Tabuľka 1.1 Prechodová tabuľka automatu

Príklad vyplnenia tabuľky prechodov nejakého abstraktného plne definovaného automatu so vstupnou abecedou X=(x1, x2) - a stavovou abecedou A=(a1, a2, a3) je uvedený v tabuľke 1.2.

Tabuľka 1.2

Ak je abstraktný automat čiastočný, potom sa do bunky jeho tabuľky prechodov umiestni pomlčka, ktorá sa nachádza na priesečníku riadku označeného vstupným signálom a stĺpca označeného zodpovedajúcim stavom (za predpokladu, že prechod do tohto stavu v rámci akcie tohto vstupného signálu nie je definovaný) a akékoľvek vstupné slovo vedúce k špecifikovanému prechodu je zakázané.

Vyplnenie zvyšku buniek je podobné ako v prípade plne definovaného automatu. Forma tabuľky prechodov nezávisí od typu daného automatu (Mealy, Moore, C-automat). Výstupné tabuľky automatov Mealy, Moore, C majú rozdiely.

Výstupná tabuľka plne definovaného automatu Mealy je zostavená nasledovne: identifikácia stĺpcov a riadkov a formát tabuľky zodpovedajú tabuľke prechodov plne definovaného automatu. V bunke výstupnej tabuľky umiestnenej na priesečníku riadku označeného vstupným signálom Xj a stĺpca označeného stavom ak je umiestnený výstupný signál Um, ktorý automat vydáva, keď je v stave ak v prítomnosti. vstupného signálu Xj, ktorý je určený výrazom Ym= (ak, xj ).

Tabuľka 1.3 Tabuľka výstupov abstraktného automatu Mealy.

Uvádza sa príklad vyplnenia výstupnej tabuľky nejakého abstraktného plne definovaného automatu vstupnou abecedou X=(x1, x2), stavovou abecedou A=(a1, a2, a3) a výstupnou abecedou Y=(y1, y2, y3). v tabuľke 1.4.

Tabuľka 1.4

Je zrejmé, že abstraktný plne definovaný C-automat je daný dvoma výstupnými tabuľkami, z ktorých prvá je výstupná tabuľka automatu Mealy a druhá je výstupná tabuľka Moore. Ak je automat čiastočný, potom v niektorých bunkách jeho tabuľky môže byť pomlčka, čo znamená, že neexistuje žiadny výstupný signál.

V praxi sa prechodové a výstupné tabuľky často kombinujú do jednej tabuľky, ktorá sa nazýva označená prechodová tabuľka automatu. Príklady označených tabuliek prechodov sú uvedené v tabuľke 1.6. - 1.8 (Celkový pohľad na označenú tabuľku prechodov - tabuľka 1.6., Tabuľka označených prechodov stroja Mealy - tabuľka 1.7., Tabuľka označených prechodov stroja Moore - tabuľka 1.8.).

Okrem vyššie uvedených prechodových a výstupných tabuliek môže byť ľubovoľný abstraktný automat definovaný spojovacou maticou.

Matica spojenia je štvorcová a obsahuje toľko stĺpcov (riadkov), koľko je rôznych stavov v abecede stavov daného automatu. Každý stĺpec (riadok) matice spojov je označený písmenom stavu automatu. V bunke umiestnenej na priesečníku stĺpca označeného písmenom aj a riadku označeného písmenom as automatu je umiestnený vstupný signál (alebo disjunkcia vstupných signálov), pod vplyvom ktorého sa tento prechod prenáša. von.

Pre abstraktný Mealyho automat obsahuje bunka vedľa stavu aj výstupný signál, ktorý automat vydáva v dôsledku tohto prechodu (tabuľka 1.9.) Pre Mooreov automat je výstupný signál umiestnený v riadku vedľa stavu ( tieto stavy zodpovedajú počiatočným stavom automatu).

Tabuľka 1.6

Tabuľka 1.8

V grafickom spôsobe nastavenia sú abstraktné automaty reprezentované orientovanými grafmi. Automatový graf je orientovaný súvislý graf, ktorého vrcholy zodpovedajú stavom automatu a oblúky medzi nimi zodpovedajú prechodom medzi stavmi. Dva vrcholy ak a as sú spojené oblúkom, ak má automat prechod zo stavu ak do stavu as. Pre stroj Mealy sú vstupné a výstupné signály umiestnené na oblúku zodpovedajúcemu tento prechod(obr. 1.3.), pre automat Moore je vstupný signál umiestnený na oblúku a výstupný signál je umiestnený v blízkosti vrcholu zodpovedajúceho stavu (obr. 1.4.).

Tu sa berú do úvahy iba deterministické automaty, pre ktoré je splnená podmienka jednoznačnosti prechodov: automat, ktorý je v určitom stave, pôsobením akéhokoľvek vstupného signálu nemôže prejsť do viac ako jedného stavu. Vzhľadom na grafický spôsob špecifikácie automatu to znamená, že zo žiadneho vrcholu v grafe automatu nemôžu vzniknúť dva alebo viac oblúkov označených rovnakým vstupným signálom.

Obrázok 1.3 - Graf stroja Mealy Obrázok 1.4 - Graf stroja Moore

V analytickom spôsobe nastavenia sú abstraktné automaty dané štyrmi objektmi:

S=(X,A,Y,F), kde F definuje pre každý stav aj automatu mapovanie (ХхА) - > (AxY). Inými slovami, pri analytickom spôsobe zadávania pre každý stav automatu aj sa uvádza zobrazenie Fai, čo je množina všetkých trojíc ap, xm, yk a taká, že pod vplyvom vstupného signálu xm automat prechádza od štátu aj v stav ap, vytvárajúci výstupný signál yk.

Pokiaľ ide o všeobecnú definíciu abstraktného automatu, táto je ekvivalentná popisu funkcií q a l v súlade s výrazom: ap= q (ai, xm), yk= l (ai, xm).

Mapovanie Fai je napísané takto:

Fai(ap (Xm/yk),ai (Xf/yz) …).

Pre abstraktný automat Mealy (tabuľka 1.7.) má analytická úloha nasledujúcu formu:

S=(X,A,Y,F), X=(x1,x2), A=(a1, a2, a3), Y=(y1, y2, y3),

Fa1=(a2 (x1/y2), a1 (x2/y3) ),

Fa2=(а3 (x1/y3), a1 (x2/y1) ),

Fa3 = (al (xl/y3), a2 (x2/y2)).

Treba poznamenať, že funkcia Fai je vždy napísaná pre počiatočný stav.

Definujeme synchrónne a asynchrónne automaty. Stav ako u automatu S sa nazýva stabilný stav, ak pre ľubovoľný vstupný signál xjX platí, že ako = q (ai Xm) máme ako = q (as, xm).

Automat S sa nazýva asynchrónny, ak každý z jeho stavov ako A je stabilný. Automat S sa nazýva synchrónny, ak nie je asynchrónny.

Treba si uvedomiť, že v praxi postavené automaty sú vždy asynchrónne a stabilita ich stavov je vždy zabezpečená tak či onak, napríklad zavedením synchronizačných signálov. Na úrovni teórie abstraktných automatov, keď je automat len ​​matematickým modelom, ktorý neodráža mnohé špecifické črty jeho implementácie, sa však často ukazuje ako pohodlnejšie pracovať so synchrónnymi automatmi.

1.4 Vzťah medzi modelmi Mealy a Moore

Ako už bolo uvedené, abstraktný automat funguje ako konvertor slov vo vstupnej abecede na slová vo výstupnej abecede.

Mealyho abstraktný automat nech je daný grafom na obr. 1.5.

Vstup tohto automatu, nastavený do počiatočného stavu, dostane vstupné slovo X=x1, x1, x2, x1, x2, x2.

Obrázok 1.5 - Graf automatu Mealy

Pretože? (a1, x1) = a3, a? (a1, x1) = y1, potom pôsobením prvého písmena slova X vstupného signálu x1 automat prejde do stavu a3 a na jeho výstupe sa objaví signál y1. Ďalej, ? (a3, x1) = a1, čo? (a3, x1) = y2, teda pri príchode druhého signálu x1 bude automat v stave a1 a na jeho výstupe sa objaví signál y2. Priamo na graf alebo tabuľky prechodov a výstupov nasleduje ďalšie správanie sa automatu, popíšeme ho v troch riadkoch, z ktorých prvý zodpovedá vstupnému slovu X, druhý - postupnosť stavov, ktorými automat prechádza pod pôsobenie písmen slova X, tretieho - na výstupné slovo Y, ktoré sa objaví na výstupnom stroji:

x1x1x2x1x2x2

a1a3 a1a1 a3 a2 a3

y1 y2 y1 y1 y1 y2

zavolajme ti = ? (a1, X) reakciou Mealyho automatu v stave a1 na vstupné slovo X. Ako je zrejmé z príkladu, Mealyho automat ako odpoveď na vstupné slovo dĺžky k vygeneruje sekvenciu stavov dĺžky k. k + 1 a výstupné slovo dĺžky k. Vo všeobecnosti možno správanie automatu Mealy nastaveného do stavu am opísať takto:

Rovnakým spôsobom sa dá opísať správanie Moorovho automatu, ktorý je v stave am, keď príde vstupné slovo xi1, xi2,., хik . Pripomeňme, že v súlade s (1-2) výstupný signál v Mooreovom automate v čase t (Y (t)) závisí iba od stavu, v ktorom sa automat nachádza v čase t (a (t)):

Je zrejmé, že výstupný signál yi1=l(am) v čase i1 nezávisí od vstupného signálu xi1, ale je určený iba stavom am.

Tento signál yi1 teda nie je žiadnym spôsobom spojený so vstupným slovom prichádzajúcim na vstup automatu, počnúc okamihom i1. V tejto súvislosti pri reakcii Moorovho stroja nastaveného do stavu am na vstupné slovo X=xi1, хi2 , . , хik budeme rozumieť výstupnému slovu rovnakej dĺžky y= л(am,х)=уi2, уi3,., yik+1.

Ako príklad uvažujme Mooreov stroj S5, ktorého graf je na Obr. 1-6, a nájdite jeho odozvu v počiatočnom stave na rovnaké vstupné slovo, aké sme použili pri analýze správania Mealyho stroja S1:

Obrázok 1-6 - Graf Mooreovho automatu

Ako vidno z tohto a predchádzajúcich príkladov, reakcie automatov S5 a S1 v počiatočnom stave na vstupné slovo X sa zhodujú až do posunu o 1 cyklus (reakcia automatu Moore je zakrúžkovaná). Teraz uvádzame rigoróznu definíciu ekvivalencie plne definovaných automatov.

Dva automaty SA a SB s rovnakou vstupnou a výstupnou abecedou sa nazývajú ekvivalentné, ak sa po nastavení do počiatočných stavov ich reakcie na ľubovoľné vstupné slovo zhodujú.

1.5 Ekvivalentné automaty. Ekvivalentné transformácie automatov

Dá sa ukázať, že pre každý Mealyho automat existuje ekvivalentný Mooreov automat a naopak, pre každý Moorov automat existuje ekvivalentný Mealyho automat.

Pri popise algoritmov vzájomnej transformácie automatov Mealy a Moore v súlade s vyššie uvedeným budeme zanedbať výstupný signál v automatoch Moore spojený s počiatočným stavom (? (a1)).

Najprv zvážte transformáciu Moorovho stroja na Mealyho stroj.

Nech je daný Mooreov automat: SA=(XA, AA, UA,?A,?A, aoA), kde:

XA = (xl, x2, xn); Y = (y1, y2, ym); A = (a0, a1, a2, aN); a0A = a0 - počiatočný stav (a0AA); ?A - funkcia prechodu automatu, ktorá definuje mapovanie (ХАхАА) - >АА; ?A - funkcia výstupov automatu, ktorá nastavuje mapovanie AA->UA.

Postavme Mealyho automat: SB=( XB, AB, YB,??B, ?B , a0B), kde AB=AA; XB=XA; YB=UA; AB=A; a0B=a0A. Výstupná funkcia?B je definovaná nasledovne. Ak v stroji Moore? A (am, x1) = as a? A (as) = ​​​​yg, potom v stroji Mealy? B (am, x1) = yg

Obrázok 1.7 - Ilustrácia prechodu z Moorovho modelu na Mealyho model

Prechod z automatu Moore na automat Mealy s grafickým spôsobom nastavenia je znázornený na obr. 1-7: výstupný signál yg zapísaný v blízkosti vrcholu (as) sa prenáša do všetkých oblúkov zahrnutých v tomto vrchole.

Pri tabuľkovom spôsobe špecifikácie automatu sa tabuľka prechodov automatu Mealy zhoduje s tabuľkou prechodov pôvodného Moorovho automatu a výstupná tabuľka sa získa z tabuľky prechodov nahradením symbolu ako na priesečníku riadku xf a stĺpec am so symbolom výstupného signálu yg označujúci stĺpec ako v tabuľke prechodov automatu SA.

Zo spôsobu konštrukcie Mealyho automatu SB je zrejmé, že je ekvivalentný Moorovmu automatu SA. Indukciou je ľahké ukázať, že akékoľvek vstupné slovo konečnej dĺžky, dané na vstupy automatov SA a SB, nastavené na stavy am, spôsobí výskyt rovnakých výstupných slov, a teda automaty SA a SB sú ekvivalentné.

Pred uvažovaním o premene stroja Mealy na stroj Moore, kladieme na automat Mealy nasledujúce obmedzenie: automat nesmie mať prechodné stavy. Prechodným javom rozumieme stav, v ktorom, keď je automat znázornený ako graf, nevstupuje žiadny oblúk, ale ktorý má aspoň jeden vychádzajúci oblúk. Nech je teda daný Mealyov automat:

SA=( XA, AA, YA, ?A, ?A, a0A),

kde:

XA=(x1, x2,.xn); Y=(y1,y2,.ym); A=(a0,a1,a2,.aN); a0A = a0 - počiatočný stav (a0AA); ?A - funkcia prechodu automatu, ktorá definuje mapovanie (XAxAA) - >AA; ?A - výstupná funkcia automatu, ktorá definuje mapovanie (XAxAA) - >YA.

Zostavme si Mooreov automat: SB=(XB, AB, YB, ?B, ?B, a0B), ktorý má XB=XA; YB=YA.

Na určenie AB je každý stav asA spojený s množinou As všetkých možných párov tvaru (as, yg)

Výstupná funkcia?B je definovaná nasledovne. Každému stavu Moorovho automatu SB, ktorý je dvojicou tvaru (as, yg), bude priradený výstupný signál yg.

Ak by Mealyho automat SA mal prechod?A (am, xf) = as a zároveň vyprodukoval výstupný signál?A (am,xf) =yg, tak v SB dôjde k prechodu z množiny stavov Am. generované am do stavu (as, yg) pôsobením vstupného signálu xf.

Ako počiatočný stav a0B možno vziať ktorýkoľvek zo stavov množiny A0, ktorý je generovaný počiatočným stavom a0 automatu SA. V tomto prípade by sa výstupný signál v čase t=0 nemal brať do úvahy.

Zvážte príklad. Nech je daný Mealyho automat (tabuľka 1.10.)

Každému páru ai/xk priraďme stav bik (i-číslo stavu, k-číslo vstupného signálu), berúc do úvahy b0.

Urobme tabuľku prechodov automatu Moore podľa nasledujúcich pravidiel:

1) Vypíšme stavy Mealyho automatu a množiny stavov Moorovho automatu (bik) zodpovedajúce každému z nich z tabuľky 1.11:

a0= (b0, b02, b11, b21); a1= (b22); a2= (b01, bl2);

2) Ak je stav biku Mooreovho stroja zahrnutý v množine zodpovedajúcej stavu ap Mealyho stroja, tak do riadku tabuľky prechodov Moorovho stroja pre stavový bik treba napísať riadok z tabuľky prechodov. stroja Mealy zodpovedajúcemu stavu ap (od 1.10.).

3) Výstupná funkcia Moorovho automatu je definovaná nasledovne: ?B (bik) =?A (ai, xk). Pre počiatočný stav b0 môže byť hodnota výstupného signálu zvolená ľubovoľne, ale generovaná počiatočným stavom a0 (s prihliadnutím na koncept stavovej ekvivalencie). Výsledná tabuľka prechodov a výstupov Moorovho automatu ekvivalentného Mealyho automatu uvedená v tabuľke 1.10 je uvedená v tabuľke 1.12.

4) Nájdite ekvivalentné stavy v tabuľke 1.12 a odstráňte ich (nahraďte ich zástupcom triedy ekvivalencie).

Ak je výstupný signál blízko b0 rozšírený o y1, potom sa ukáže, že v tejto tabuľke prechodov sú 3 ekvivalentné stavy (b0,b11,b02). Nahradením triedy ekvivalencie jedným zástupcom (b0) získame konečnú tabuľku prechodov (tabuľka 1.13).

Tabuľka 1.12

Prezentované metódy vzájomnej transformácie automatov Mealy a Moore ukazujú, že pri prechode z Moorovho automatu na Mealyho automat sa počet stavov automatu nemení, pričom pri spätnom prechode sa počet stavov v Moorovom automate nemení. sa spravidla zvyšuje.

Vzájomne ekvivalentné automaty teda môžu mať rôzny počet stavov, čím vzniká problém nájsť minimálny (s minimálnym počtom stavov) automat v triede navzájom ekvivalentných automatov. Existenciu pre akýkoľvek abstraktný automat ekvivalentného abstraktného automatu s minimálnym počtom vnútorných stavov prvýkrát dokázal Moore.

1.6 Minimalizácia počtu vnútorných stavov automatu

Aufenkamp-Hohnov algoritmus.

Metóda minimalizácie stavov automatu je založená na myšlienke rozdelenia všetkých stavov pôvodného, ​​abstraktného automatu do párovo disjunktných tried ekvivalentných stavov a nahradenia každej triedy ekvivalencie jedným stavom (reprezentatívnym túto triedu). Minimálny automat, ktorý je výsledkom týchto transformácií, má toľko stavov, koľko je tried ekvivalencie, do ktorých sú počiatočné stavy rozdelené.

Dva stavy automatu am a as sa nazývajú ekvivalentné (am =as), ak? (am, X) = ? (as,X) pre všetky možné vstupné slová dĺžky X.

Ak am a as nie sú ekvivalentné, sú odlišné. Slabšia ekvivalencia je K-ekvivalencia. Stavy am a as sú K-ekvivalentné, ak? (am, Xk) = ? (as, Xk) pre všetky možné vstupné slová dĺžky K. Pri minimalizácii počtu vnútorných stavov Mealyho automatu S=(X, Y, A, ? , ?, a0) používa sa Aufenkamp-Hohnov algoritmus:

1. Nájdite po sebe nasledujúce oddiely?1,?2,…,?k,?k+1, množiny A do tried jedno-, dvoj-,., K-, (K+1) - ekvivalentné stavy až do určitého (K +1) krok nedopadne ze?k=?k+1. V tomto prípade sú K-ekvivalentné stavy ekvivalentné. Počet krokov K, pri ktorých?k=?k+1 nepresiahne N-1, kde N je počet vnútorných stavov automatu.

2. V každej triede ekvivalencie? vyberte si po jednom prvku (zástupca triedy), ktorý tvorí množiny A "stavov minimálneho automatu S".

3. Funkcia prechodov?" a výstupov?" automat S" je definovaný na množine A"xX.

Na tento účel sa v tabuľke prechodov a výstupov prečiarknu stĺpce zodpovedajúce stavom, ktoré nie sú zahrnuté v množine A, a vo zvyšných stĺpcoch tabuľky prechodov sa všetky stavy nahradia ekvivalentnými stavmi z množiny A. , (zástupcovia).

4. Jeden zo stavov ekvivalentných stavu a0 sa zvolí ako a"0. Najmä je vhodné vziať samotný stav a0.

Pri minimalizácii Moorovho automatu sa zavádza koncept 0-ekvivalencie stavov a rozdelenia množiny stavov na 0-triedy: akékoľvek stavy Moorovho automatu, ktoré sú zhodne označené výstupnými signálmi, sa nazývajú 0-ekvivalenty. Ako príklad uvažujme minimalizáciu Moorovho automatu s tabuľkou prechodov a výstupov (tabuľka 1.14).

Tabuľka 1.14

Rozdelíme sa? 0:

? 0 = (B1, B2, B3);

B1 = (al, a2, a8), B2 = (a6, a9, a10, a11, a12), B3 = (a3, a4, a5, a7).

Poďme zostaviť tabuľku oddielov?0:

Rozdelíme sa?1:

1 = (C1, C2, C3, C4);

C1 = (al, a2, a8), C2 = (a6, a9, a11), C3 = (a10, a12), C4 = (a3, a4, a5, a7).

Poďme zostaviť tabuľku oddielov?1:

Rozdelíme sa?2 .

1 = (D1, D2, D3, D4);

D1 = (al, a2, a8), D2 = (a6, a9, a11), D3 = (a10, a12), D4 = (a3, a4, a5, a7).

Štiepenie?2 zopakuje štiepanie?1 - postup štiepania je ukončený.

Náhodne vyberieme jedného zástupcu z každej triedy ekvivalencie D1, D2, D3, D4 - v tomto prípade minimálnym počtom: A "= (a1, a3, a6 , a10).

Odstránením „extra“ stavov z pôvodnej tabuľky prechodov určíme minimálny Mooreov automat (tabuľka 1.15.)

Tabuľka 1.15.

Výkon

V procese vykonávania kontrolných prác sme sa oboznámili so základnými pojmami abstraktných digitálnych automatov; typy abstraktných automatov; spôsoby špecifikácie abstraktných automatov; prepojenie medzi modelmi Mealy a Moore; ekvivalentné automaty a ekvivalentné transformácie automatov; minimalizácia počtu vnútorných stavov automatu a Aufenkamp-Hohnov algoritmus - uviedol príklady.

Bibliografia

1. K. G. Samofalov, A. M. Romankevich a kol., Aplikovaná teória digitálnych automatov. - Kyjev. "Škola Vishcha" 1987.

2. Solovjev G.N. Počítačové aritmetické jednotky. - M. "Energia". 1978.

3. Saveliev A.Ya. Aplikovaná teória digitálnych automatov - M.“ stredná škola”. 1987.

4. Kagan B.M. Elektronické počítače a systémy. - M. Energoatomizdat. 1985.

5. Lysikov B.G. Aritmetické a logické základy digitálnych automatov. - Minsk. "Najvyššia škola". 1980.

Podľa spôsobu generovania výstupnej funkcie sa rozlišujú tri typy abstraktných automatov: Mealyho automat, Mooreov automat, C-automat. Automat Mealy je charakterizovaný systémom rovníc:

y(t)=(a(t), x(t));

a (t+1) = 5 (a (t), x (t)). (1-1)

Mooreov automat - systém rovníc:

a (t+1) = 5 (a (t), x (t)). (1-2)

C-stroj - sústava rovníc:

y1 (t) = (a (t), x (t));

Y2(t) = 2(a(t));

a (t+1) = 5 (a (t), x (t)).

Ľubovoľný abstraktný automat Mealy alebo Moore (obr. 1.1.) má jeden vstupný a jeden výstupný kanál. Ľubovoľný abstraktný C-automat má jeden vstupný a dva výstupné kanály (obr. 1.2.).

Obrázok 1.1 - Abstraktný automat

Obrázok 1.2 Abstraktný C-automat

Ak vstup abstraktného Mealyho alebo Moorovho automatu, nastaveného na počiatočný stav a o, dostane písmeno po písmene sekvenciu písmen vstupnej abecedy x(0), x(1),. je vstupné slovo, potom sa na výstupe automatu postupne objavia písmená výstupnej abecedy y (0), y (1). - výstupné slovo. V prípade C-automatu sa na jeho výstupoch objavia dve sekvencie: y 1 (0), y 1 (1),. a y2 (0), y2 (1). V abstraktnom C-automate je výstupný signál y 2 (t) = (a (t)) vydávaný po celú dobu, kým je automat v stave a (t). Výstupný signál y 1 (t) =λ 1 (a (t),x (t)) je vydaný pri pôsobení vstupného signálu x (t), keď je C-automat v stave a (t).

Na úrovni abstraktnej teórie sa teda fungovanie digitálneho automatu chápe ako transformácia vstupných slov na výstupné slová.

Existujú plne definované a čiastočné automaty.

Abstraktný digitálny automat sa nazýva plne definovaný, ak jeho prechodová funkcia alebo výstupná funkcia alebo obe tieto funkcie sú definované pre všetky dvojice prechodov (x i , a j).

Parciálny je abstraktný digitálny automat, v ktorom prechodová funkcia alebo výstupná funkcia, prípadne obe tieto funkcie nie sú definované pre všetky dvojice prechodov (x i ,a j).

Abstraktný digitálny automat sa nazýva počiatočný, ak na množine jeho stavov A je vyčlenený počiatočný stav a o.

1.3 Spôsoby definovania abstraktných automatov

Na definovanie konečného automatu S je potrebné popísať všetky prvky množiny: S=( X,A,Y,,,a o ). Existuje niekoľko spôsobov, ako nastaviť činnosť stroja, ale najčastejšie používané sú tabuľkové (maticové), grafické a analytické.

Pri tabuľkovej metóde je automat špecifikovaný dvomi tabuľkami: prechodovou tabuľkou a výstupnou tabuľkou alebo spojovacou maticou. Prechodová tabuľka ľubovoľného plne definovaného automatu je konštruovaná nasledovne: riadky tabuľky sú označené písmenami vstupnej abecedy automatu a stĺpce tabuľky sú označené písmenami stavovej abecedy automatu; V bunke tabuľky skokov umiestnenej na v priesečníku riadku označeného vstupným signálom x i a stĺpca označeného stavom a j sa nastaví stav a k, ktorý je výsledkom prechodu automatu zo stavu a j vplyvom vstupného signálu x i, ktorý je určený výrazom a k =(a j , x j).

Tabuľka 1.1 Prechodová tabuľka automatu

štátov
vstupné signály
				(a k, x j)

Príklad vyplnenia tabuľky prechodov nejakého abstraktného plne definovaného automatu so vstupnou abecedou X=(x 1 , x 2 ) - a stavovou abecedou A=(a 1 , a 2 , a 3 ) je uvedený v tabuľke 1.2.

Tabuľka 1.2

Ak je abstraktný automat čiastočný, potom sa do bunky jeho tabuľky prechodov umiestni pomlčka, ktorá sa nachádza na priesečníku riadku označeného vstupným signálom a stĺpca označeného zodpovedajúcim stavom (za predpokladu, že prechod do tohto stavu v rámci akcie tohto vstupného signálu nie je definovaný) a akékoľvek vstupné slovo vedúce k špecifikovanému prechodu je zakázané.

Vyplnenie zvyšku buniek je podobné ako v prípade plne definovaného automatu. Forma tabuľky prechodov nezávisí od typu daného automatu (Mealy, Moore, C-automat). Výstupné tabuľky automatov Mealy, Moore, C majú rozdiely.

Výstupná tabuľka plne definovaného automatu Mealy je zostavená nasledovne: identifikácia stĺpcov a riadkov a formát tabuľky zodpovedajú tabuľke prechodov plne definovaného automatu. V bunke výstupnej tabuľky umiestnenej na priesečníku riadku označeného vstupným signálom X j a stĺpca označeného stavom a k je umiestnený výstupný signál Y m, ktorý stroj produkuje v stave a k za prítomnosti vstupného signálu Xj, ktorý je určený výrazom Ym= (a k , x j).

Tabuľka 1.3 Tabuľka výstupov abstraktného automatu Mealy.

štátov
Vstupné signály

Príklad vyplnenia výstupnej tabuľky nejakého abstraktného plne definovaného automatu vstupnou abecedou X=(x 1 , x 2 ), stavovou abecedou A=(a 1 , a 2 , a 3 ) a výstupnou abecedou Y=(y 1 , y2, y3) je uvedený v tabuľke 1.4.

Tabuľka 1.4

Je zrejmé, že abstraktný plne definovaný C-automat je daný dvoma výstupnými tabuľkami, z ktorých prvá je výstupná tabuľka automatu Mealy a druhá je výstupná tabuľka Moore. Ak je automat čiastočný, potom v niektorých bunkách jeho tabuľky môže byť pomlčka, čo znamená, že neexistuje žiadny výstupný signál.

V praxi sa prechodové a výstupné tabuľky často kombinujú do jednej tabuľky, ktorá sa nazýva označená prechodová tabuľka automatu. Príklady označených tabuliek prechodov sú uvedené v tabuľke 1.6. - 1.8 (Celkový pohľad na označenú tabuľku prechodov - tabuľka 1.6., Tabuľka označených prechodov stroja Mealy - tabuľka 1.7., Tabuľka označených prechodov stroja Moore - tabuľka 1.8.).

Okrem vyššie uvedených prechodových a výstupných tabuliek môže byť ľubovoľný abstraktný automat definovaný spojovacou maticou.

Matica spojenia je štvorcová a obsahuje toľko stĺpcov (riadkov), koľko je rôznych stavov v abecede stavov daného automatu. Každý stĺpec (riadok) matice spojov je označený písmenom stavu automatu. V bunke umiestnenej na priesečníku stĺpca označeného písmenom aj a riadku označeného písmenom as automatu je umiestnený vstupný signál (alebo disjunkcia vstupných signálov), pod vplyvom ktorého sa tento prechod prenáša von.

Pre abstraktný Mealyho automat obsahuje bunka vedľa stavu aj výstupný signál, ktorý automat vydáva v dôsledku tohto prechodu (tabuľka 1.9.) Pre Mooreov automat je výstupný signál umiestnený v riadku vedľa stavu ( tieto stavy zodpovedajú počiatočným stavom automatu).

Tabuľka 1.6

štátov
Vstupné signály
		 (a 2, x j)		 (ak, x j)
		 (a 2, x j)		 (ak, x j)

Tabuľka 1.7

Tabuľka 1.9.

V grafickom spôsobe nastavenia sú abstraktné automaty reprezentované orientovanými grafmi. Automatový graf je orientovaný súvislý graf, ktorého vrcholy zodpovedajú stavom automatu a oblúky medzi nimi zodpovedajú prechodom medzi stavmi. Dva vrcholy a k a a s sú spojené oblúkom, ak má automat prechod zo stavu a k do stavu a s . Pre stroj Mealy sú vstupné a výstupné signály umiestnené na oblúku zodpovedajúcemu danému prechodu (obr. 1.3.), pre stroj Moore je vstupný signál umiestnený na oblúku a výstupný signál je umiestnený v blízkosti vrcholu. zodpovedajúce stavu (obr. 1.4.).

Tu sa berú do úvahy iba deterministické automaty, pre ktoré je splnená podmienka jednoznačnosti prechodov: automat, ktorý je v určitom stave, pôsobením akéhokoľvek vstupného signálu nemôže prejsť do viac ako jedného stavu. Vzhľadom na grafický spôsob špecifikácie automatu to znamená, že zo žiadneho vrcholu v grafe automatu nemôžu vzniknúť dva alebo viac oblúkov označených rovnakým vstupným signálom.

Obrázok 1.3 - Graf stroja Mealy Obrázok 1.4 - Graf stroja Moore

V analytickom spôsobe nastavenia sú abstraktné automaty dané štyrmi objektmi:

S=(X,A,Y,F), kde F definuje pre každý stav a j automatu mapovanie (ХхА) - > (AxY). Inými slovami, pri analytickom spôsobe špecifikácie pre každý stav automatu a j sa uvádza zobrazenie F ai, čo je množina všetkých trojíc a p, x m , y k a taká, že vplyvom vstupného signálu x m automat prechádza od štátu a j v stav a p, pričom vytvára výstupný signál y k .

Pokiaľ ide o všeobecnú definíciu abstraktného automatu, táto je ekvivalentná popisu funkcií δ a λ v súlade s výrazom: a p = δ (a i , x m), y k = λ (a i , x m).

Zobrazenie F ai je napísané takto:

F ai (a p (X m / y k), a i (X f / y z) ...).

Pre abstraktný automat Mealy (tabuľka 1.7.) má analytická úloha nasledujúcu formu:

S=(X,A,Y,F), X=(x1,x2), A=(a1, a2, a3), Y=(y1, y2, y3),

F a1 \u003d (a 2 (x 1 / y 2), a 1 (x 2 / y 3) ),

F a 2 \u003d (a 3 (x 1 / y 3), a 1 (x 2 / y 1)),

F a 3 \u003d (a 1 (x 1 / y 3) a 2 (x 2 / y 2)).

Treba si uvedomiť, že funkcia F ai sa vždy píše pre počiatočný stav.

Definujeme synchrónne a asynchrónne automaty. Stav a s automatu S sa nazýva stabilný stav, ak pre ľubovoľný vstupný signál x j X nastáva a s = δ (a i X m) a s = δ (a s , x m).

Automat S sa nazýva asynchrónny, ak je každý jeho stav a s A stabilný. Automat S sa nazýva synchrónny, ak nie je asynchrónny.

Treba si uvedomiť, že v praxi postavené automaty sú vždy asynchrónne a stabilita ich stavov je vždy zabezpečená tak či onak, napríklad zavedením synchronizačných signálov. Na úrovni teórie abstraktných automatov, keď je automat len ​​matematickým modelom, ktorý neodráža mnohé špecifické črty jeho implementácie, sa však často ukazuje ako pohodlnejšie pracovať so synchrónnymi automatmi.