### 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

- movebla eniga rubando, nebarita, dividita en fakojn, ĉiu el kiuj povas enteni ĝuste po unu signon ai, kie 0≤i≤N, a₀ estas la vakuo, finia signaro A={ai} estas la ekstera alfabeto de la aŭtomato, la limojn de la enigaĵo indikas speciala kromsigno (sur la figuro,`"#"`);
- malfinia interna memoro, kiu normale havas ian strukturon. Ofte ĝi estas prezentata kiel movebla memorrubando, eventuale barita unuflanke, finia aŭ malfinia, dividita en fakojn; en ajnan fakon eblas skribi po ĝuste unu signon Sj, kie 0≤j≤M, S₀ estas la vakuo, la finia signaro S estas la interna alfabeto de la aŭtomato;
- finia stirorgano, kiu ĉiam estas en unu el la finia aro da statoj X; kiu havas legilon (legkapeton) por la eniga rubando; kaj legil-skribilon (lega-skriban kapeton) por la interna memoro (memorrubando).

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

- ŝanĝi la staton de la stirorgano;
- ŝovi la enigrubandan kapeton je unu fako ajndirekte aŭ lasi ĝin senmova;
- fari finian ŝanĝon en la interna memoro.

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

- ŝanĝi la staton de la stirorgano;
- ŝanĝi la signon en la fako, ĉe kiu staras la legil-skribilo;
- ŝovi unu aŭ ambaŭ kapetojn, sendepende unu je la alia, je unu fako ajndirekte aŭ lasi ilin senmovaj.

Simbole, Turinga aŭtomato estas 7-opo

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

kie (kp aŭtomato)

- X estas finia aro da statoj, x₀∈X estas la komenca stato;
- A estas finia ekstera alfabeto;
- S estas la finia interna signaro, s₀∈S estas vakuo;
- D estas ĵeto el X×(A+{#})×S en la subararon de

  X×(S−{s₀})×{−1,0,+1}×{−1,0,+1}

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).