Absztrakt automata

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 7-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Az absztrakt automata (az algoritmusok elméletében ) egy matematikai absztrakció , egy olyan diszkrét eszköz modellje , amelynek egy bemenete, egy kimenete van, és a sok lehetséges állapot közül egy adott időpontban van. Ez az eszköz egy ábécé szimbólumait fogadja a bemeneten , a kimeneten pedig egy másik ábécé szimbólumait állítja elő (általános esetben).

Formálisan az absztrakt automatát ötösként határozzák meg

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

Ahol S az automata állapotok véges halmaza , X, Y a véges bemeneti és kimeneti ábécé, amelyekből az automata által kiolvasott és kiadott karakterláncok keletkeznek, az átmeneti függvény, a kimeneti függvény. $\delta :S\times X\rightarrow S$ $\lambda :S\szor X\jobbra Y$

A kitüntetett kezdeti állapotú absztrakt automatát kezdeti automatának nevezzük. Így egy absztrakt automata meghatározza a kezdeti automaták családját

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

Ha az átmeneti és a kimeneti függvények minden párhoz egyedileg vannak definiálva , akkor az automatát determinisztikusnak nevezzük. Egyébként az automatát nem-determinisztikusnak vagy részben definiáltnak nevezzük. ${\boldsymbol {(s,x)\in S\times X}}$

Ha az átmeneti függvény és/vagy a kimeneti függvény véletlenszerű, akkor az automatát valószínűséginek nevezzük .

Az absztrakt automata állapotainak számának korlátozása egy ilyen fogalmat véges automatának definiált .

Az automata működése két szekvencia létrehozásából áll: az automata következő állapotainak sorozatából és a kimeneti szimbólumok sorozatából , amelyek a szimbólumsorozatra t = 1, 2, 3, .. diszkrét időpillanatokban bontakoznak ki. A diszkrét időpillanatokat ciklusoknak nevezzük. ${\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]...))$

Az automata működése diszkrét t időpontokban az ismétlődési relációk rendszerével írható le: ${\boldsymbol {s(t+1)=\delta (s(t),x(t));))$

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

Az absztrakt automaták tulajdonságainak tisztázására egy osztályozást vezettünk be .

Az absztrakt automaták a diszkrét modellek alapvető osztályát alkotják, mind önálló modellként, mind a Turing -gépek , a lenyomó automaták , a véges automaták és más információátalakítók alapvető összetevőjeként.

Az absztrakt automata modellt széles körben használják alapmodellként olyan automaták diszkrét modelljeinek megalkotásához, amelyek felismerik, generálják és átalakítják a karaktersorozatokat .

Irodalom

Viktor Mihajlovics Glushkov . Az automaták absztrakt elmélete. - Advances in Mathematical Sciences , XVI. 5 (101). - M. , 1961. - S. 476.

Viktor Mihajlovics Glushkov . Digitális automaták szintézise. - M . : Állami Fizikai és Matematikai Irodalmi Kiadó , 1962. - S. 476.

Szótárak és enciklopédiák	Nagy orosz