Automat abstract

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

Un automat abstract (în teoria algoritmilor ) este o abstractizare matematică , un model al unui dispozitiv discret care are o intrare, o ieșire și se află într-o stare din multe posibile la un moment dat. Acest dispozitiv primește simboluri ale unui alfabet la intrare , iar la ieșire produce simboluri (în cazul general) ale altui alfabet.

Formal, un automat abstract este definit ca un cinci

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

Unde S este mulțimea finită de stări ale automatului, X, Y sunt alfabetele finite de intrare și, respectiv, de ieșire, din care sunt formate șirurile citite și ieșite de automat, este funcția de tranziție, este funcția de ieșire. $\delta :S\time X\rightarrow S$ $\lambda :S\time X\rightarrow Y$

Un automat abstract cu o stare inițială distinsă se numește automat inițial. Astfel, un automat abstract definește o familie de automate inițiale

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

Dacă funcțiile de tranziție și de ieșire sunt definite în mod unic pentru fiecare pereche , atunci automatul se numește determinist. În caz contrar, automatul se numește nedeterminist sau parțial definit. ${\boldsymbol {(s,x)\in S\time X}}$

Dacă funcția de tranziție și/sau funcția de ieșire sunt aleatoare, atunci automatul se numește probabilistic .

Limitarea numărului de stări ale unui automat abstract a definit un astfel de concept ca un automat finit .

Funcționarea automatului constă în generarea a două secvențe: succesiunea stărilor următoare ale automatului și succesiunea simbolurilor de ieșire , care pentru succesiunea de simboluri se desfășoară la momente de timp discrete t = 1, 2, 3, .. Momentele de timp discrete se numesc cicluri. ${\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]...))$

Funcționarea automatului la momente discrete t poate fi descrisă prin sistemul de relații de recurență: ${\boldsymbol {s(t+1)=\delta (s(t),x(t));}}$

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

Pentru a clarifica proprietățile automatelor abstracte, a fost introdusă o clasificare .

Automatele abstracte formează o clasă fundamentală de modele discrete atât ca model în sine, cât și ca componentă de bază a mașinilor Turing , a automatelor push-down , a automatelor finite și a altor convertoare de informații.

Modelul automat de abstract este utilizat pe scară largă ca unul de bază pentru construirea de modele discrete de automate care recunosc, generează și transformă secvențe de caractere .

Literatură

Viktor Mihailovici Glushkov . Teoria abstractă a automatelor. - Progrese în științe matematice , vol. XVI, nr. 5 (101). - M. , 1961. - S. 476.

Viktor Mihailovici Glushkov . Sinteza automatelor digitale. - M . : Editura de stat de literatură fizică și matematică , 1962. - S. 476.

Dicționare și enciclopedii	Rusă mare