Sekvan paĝon! Antaŭan paĝon! Indekson! Instrukcion!

Aŭtomatoj

  1. Abstraktaj aŭtomatoj: Ĝeneralaj trajtoj
  2. La Turinga aŭtomato
  3. La reĝistra aŭtomato
  4. Pri kompliko: de komputado
  5. Pri la komplikteorio
  6. Petri-retoj

Abstraktaj aŭtomatoj

Difino
La terminaro de la teorio de aŭtomatoj implicas fikcian meĥanismon, kiel tiu bildigita sur la figuro:
       --------------------------------------------------------- 
         |   | # |a₁|a₂| ....... |ai| ... |an| # |   | 
       ---------------------------------A----------------------- 
                                        | 
   ,---------.                 ,--------+----------. 
   |Malfinia  \      ,---------| Finia  stirorgano | 
   `.   memoro )›----'         `-------------------' 
    |_________/

Ĝi konsistas el

Aŭtomato faras elementajn paŝojn, kiuj dependas je la stato de la stirorgano, de signo legata de la enigrubanda kapeto, kaj de finia datumo el la interna memoro. Per unu paŝo la aŭtomato povas Se por ĉia situacio ekzistas ne pli ol unu ebla elementa paŝo, la aŭtomato estas determinisma. Sen la postulo pri tiu unikeco la aŭtomato (kaj la komputado per ĝi farata) estas nomata nedeterminisma. Do, determinismo estas triviala kazo de nedeterminismo.

Komence la eniga rubando estas en tia pozicio, ke ĝia legilo vidas la unuan (la plej maldekstran) signon, la interna memoro estas virga kaj prezentas sian unuan fakon al la legil-skribilo, la stirorgano estas en la komenca stato X₀.

La aŭtomato haltas atinginte iun el la specialaj haltstatoj Xh; ekz-e, se necesas konstrui aŭtomaton kiu kontrolu, ĉu la signoĉeno skribita sur ĝia eniga rubando apartenas al koncerna formala lingvo, oni povas antaŭvidi du haltstatojn: SUKCESO (la signoĉeno estas akceptita, aŭ rekonita) kaj FIASKO (ĝi certe ne apartenas al la lingvo). Por iuj lingvoj kaj aŭtomatoj eblas tria eventualo: la aŭtomato laboras senfine, ne povante atingi haltstaton.

Ĉiu determinisma aŭtomato kalkulas komputeblan funkcion: la argumento estas la signoĉeno skribata sur la eniga rubando, la rezulto estas la signoĉeno skribata sur la memorrubando (kajaŭ la haltstato).

Aplikoj
La nocio de aŭtomato estas uzata en diversbranĉaj komputikaj studoj, precipe rilataj al cirkvitoj, algoritmoj, formalaj lingvoj.

Aŭtomatoj estas instrumento kiu servas al formaligo de la analizaj procedoj dum strukturrekono. Ekz-e, en la teorio de formalaj lingvoj oni rilatigas al ĉiu speco de gramatikoj ekvivalentan tipon de aŭtomatoj kiuj akceptas la signoĉenojn obeantajn tian gramatikon — tiel oni rilatigas al la senkuntekstaj gramatikoj la stakajn aŭtomatojn; al la kuntekstohavaj gramatikoj, la lineare baritajn aŭtomatojn; al la regulaj esprimoj, la finiajn aŭtomatojn, kaj al la plej ĝenerala tipo, la Turingan aŭtomaton (vd hierarkio laŭ Ĉomski).

La Turinga aŭtomato

La skemon de Turinga aŭtomato prezentas la sekva figuro.
--------------------------------------------------------- 
  |   | # |a₁|a₂| ....... |ai| ... |an| # |   | 
--------------------------------A------------------------ 
                                | 
                       ,--------+----------. 
                       | Finia  stirorgano | 
                       `--------+----------' 
                                 \ 
                                  \_ 
                                    \ 
                                     \ 
     ---------------------------------V----------------------- 
       |   | # |s₁|s₂| ....... |sj| ... |sm| # |   | 
     ---------------------------------------------------------

La interna malfinia memoro (vd aŭtomato) de Turinga aŭtomato estas linia rubando kun legil-skribilo (lega-skriba kapeto). Per unu paŝo la Turinga aŭtomato povas

Simbole, Turinga aŭtomato estas 7-opo

M=(X,A,S,D,x₀,s₀,F) 

kie (kp aŭtomato)

Se (y,s′,dl,di)∈D(x,a,s), tio signifas jenon: kiam la Turinga aŭtomato M, estante en la stato x, legas a-n de la eniga kaj s-n de la internmemora rubandoj, tiam ĝi rajtas transiri en la staton y, anstataŭigi s-n je la nevakua signo s′ kaj movi la enigan kaj internan kapetojn je dl kaj di paŝojn respektive (−1 estas ŝovo maldekstren, 0 estas nemovo, +1 estas ŝovo dekstren).


Sekvan paĝon Indekson Instrukcion