Abstraktní automat

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. května 2021; kontroly vyžadují 2 úpravy .

Abstraktní automat (v teorii algoritmů ) je matematická abstrakce , model samostatného zařízení , které má jeden vstup, jeden výstup a je v jednom stavu z mnoha možných v daném okamžiku. Toto zařízení přijímá na vstupu symboly jedné abecedy a na výstupu vytváří symboly (obecně) jiné abecedy.

Formálně je abstraktní automat definován jako pětka

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

Kde S je konečná množina stavů automatu, X, Y jsou konečná vstupní a výstupní abeceda, v tomto pořadí, ze kterých jsou tvořeny řetězce čtené a výstupní automatem, je přechodová funkce, je výstupní funkce. $\delta :S\krát X\šipka doprava S$ $\lambda :S\krát X\šipka doprava Y$

Abstraktní automat s rozlišeným počátečním stavem se nazývá počáteční automat. Abstraktní automat tedy definuje rodinu počátečních automatů

${\boldsymbol {(s_{i},A),s_{i}\in S))$

Pokud jsou přechodové a výstupní funkce jednoznačně definovány pro každý pár , pak se automat nazývá deterministický. Jinak se automat nazývá nedeterministický nebo částečně definovaný. ${\boldsymbol {(s,x)\in S\times X}}$

Pokud jsou přechodová funkce a/nebo výstupní funkce náhodné, pak se automat nazývá pravděpodobnostní .

Omezení počtu stavů abstraktního automatu definovalo takový koncept jako konečný automat .

Fungování automatu spočívá v generování dvou sekvencí: sekvence dalších stavů automatu a sekvence výstupních symbolů , které se pro sekvenci symbolů odvíjejí v diskrétních časových okamžicích t = 1, 2, 3, .. Diskrétní časové momenty se nazývají cykly. ${\boldsymbol {s_{1}[1]s_{2}[2]s_{3}[3]...))$ ${\boldsymbol {y_{1}[1]y_{2}[2]y_{3}[3]...))$ ${\boldsymbol {x_{1}[1]x_{2}[2]x_{3}[3]...))$

Fungování automatu v diskrétních časech t lze popsat systémem rekurentních vztahů: ${\boldsymbol {s(t+1)=\delta (s(t),x(t));}}$

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

Pro objasnění vlastností abstraktních automatů byla zavedena klasifikace .

Abstraktní automaty tvoří základní třídu diskrétních modelů jak jako model sám o sobě, tak jako základní součást Turingových strojů , zásobníkových automatů , konečných automatů a dalších konvertorů informací.

Abstraktní model automatu je široce používán jako základní model pro konstrukci diskrétních modelů automatů, které rozpoznávají, generují a transformují sekvence znaků .

Literatura

Viktor Michajlovič Gluškov . Abstraktní teorie automatů. - Advances in Mathematical Sciences , díl XVI, no. 5 (101). - M. , 1961. - S. 476.

Viktor Michajlovič Gluškov . Syntéza číslicových automatů. - M . : Státní nakladatelství fyzikální a matematické literatury , 1962. - S. 476.

Slovníky a encyklopedie	Velký Rus