Abstrakt automat

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. maj 2021; checks kræver 2 redigeringer .

En abstrakt automat (i teorien om algoritmer ) er en matematisk abstraktion , en model af en diskret enhed , der har én indgang, én udgang og er i én tilstand ud af mange mulige på et givet tidspunkt. Denne enhed modtager symboler for ét alfabet ved input , og ved output producerer den symboler (i det generelle tilfælde) af et andet alfabet.

Formelt defineres en abstrakt automat som en femmer

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

Hvor S er det endelige sæt af automattilstande, X, Y er henholdsvis de endelige input- og output-alfabeter, hvorfra de strenge, der læses og udlæses af automaten, dannes, er overgangsfunktionen, er outputfunktionen. $\delta :S\ gange X\højrepil S$ $\lambda :S\ gange X\højrepil Y$

En abstrakt automat med en fornem initial tilstand kaldes en initial automat. Således definerer en abstrakt automat en familie af initiale automater

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

Hvis overgangs- og outputfunktionerne er unikt defineret for hvert par , kaldes automaten deterministisk. Ellers kaldes automaten ikke-deterministisk eller delvist defineret. ${\boldsymbol {(s,x)\i S\ gange X}}$

Hvis overgangsfunktionen og/eller outputfunktionen er tilfældige, kaldes automaten probabilistisk .

Begrænsning af antallet af tilstande af en abstrakt automat definerede et sådant koncept som en endelig automat .

Automatens funktion består i genereringen af to sekvenser: sekvensen af de næste tilstande af automaten og sekvensen af outputsymboler , som for sekvensen af symboler udfolder sig på diskrete tidspunkter t = 1, 2, 3, .. Diskrete tidsmomenter kaldes cyklusser. ${\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]...))$

Automatens funktion på diskrete tidspunkter t kan beskrives ved systemet med gentagelsesrelationer: ${\fedsymbol {s(t+1)=\delta (s(t),x(t));}}$

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

For at tydeliggøre egenskaberne ved abstrakte automater er der indført en klassifikation .

Abstrakte automater udgør en grundlæggende klasse af diskrete modeller både som en model i sig selv og som en kernekomponent i Turing -maskiner , push-down- automater , finite automater og andre informationsomformere.

Den abstrakte automatmodel er meget brugt som en grundlæggende model til at konstruere diskrete modeller af automater, der genkender, genererer og transformerer karaktersekvenser .

Litteratur

Viktor Mikhailovich Glushkov . Abstrakt teori om automater. - Advances in Mathematical Sciences , bind XVI, no. 5 (101). - M. , 1961. - S. 476.

Viktor Mikhailovich Glushkov . Syntese af digitale automater. - M . : Statens forlag for fysisk og matematisk litteratur , 1962. - S. 476.

Ordbøger og encyklopædier	Stor russer