Abstrakt automat

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 maj 2021; kontroller kräver 2 redigeringar .

En abstrakt automat (i teorin om algoritmer ) är en matematisk abstraktion , en modell av en diskret enhet som har en ingång, en utgång och är i ett tillstånd av många möjliga vid varje given tidpunkt. Den här enheten tar emot symboler för ett alfabet vid ingången och vid utgången producerar den symboler (i det allmänna fallet) för ett annat alfabet.

Formellt definieras en abstrakt automat som en femma

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

Där S är den ändliga uppsättningen av automattillstånd, X, Y är de finita ingångs- respektive utgående alfabeten, från vilka strängarna som läses och utmatas av automaten bildas, är övergångsfunktionen, är utgångsfunktionen. $\delta :S\ gånger X\högerpil S$ $\lambda :S\ gånger X\högerpil Y$

En abstrakt automat med ett distingerat initialtillstånd kallas en initial automat. Således definierar en abstrakt automat en familj av initiala automater

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

Om övergångs- och utgångsfunktionerna är unikt definierade för varje par , kallas automaten deterministisk. Annars kallas automaten icke-deterministisk eller delvis definierad. ${\boldsymbol {(s,x)\i S\ gånger X}}$

Om övergångsfunktionen och/eller utgångsfunktionen är slumpmässiga kallas automaten probabilistisk .

Att begränsa antalet tillstånd för en abstrakt automat definierade ett sådant koncept som en finit automat .

Automatens funktion består i genereringen av två sekvenser: sekvensen av nästa tillstånd för automaten och sekvensen av utgående symboler , som för sekvensen av symboler utspelar sig vid diskreta tidpunkter t = 1, 2, 3, .. Diskreta tidsmoment kallas cykler. ${\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 vid diskreta tidpunkter t kan beskrivas av systemet med återkommande relationer: ${\boldsymbol {s(t+1)=\delta (s(t),x(t));))$

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

För att förtydliga egenskaperna hos abstrakta automater har en klassificering införts .

Abstrakta automater utgör en grundläggande klass av diskreta modeller både som en modell i sig själv och som en kärnkomponent i Turing -maskiner , push-down- automater , finita automater och andra informationsomvandlare.

Den abstrakta automatmodellen används ofta som en grundläggande modell för att konstruera diskreta modeller av automater som känner igen, genererar och transformerar teckensekvenser .

Litteratur

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

Viktor Mikhailovich Glushkov . Syntes av digitala automater. - M . : Statens förlag för fysisk och matematisk litteratur , 1962. - S. 476.

Ordböcker och uppslagsverk	Stor ryss