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

       --------------------------------------------------------- 
         |   | # |a1|a2| ....... |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 a_i, kie 0≤i≤N, a₀ estas la vakuo, finia signaro A={a_i} 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 S_j, 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).

• ŝ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.

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 X_h; 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

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

--------------------------------------------------------- 
  |   | # |a1|a2| ....... |ai| ... |an| # |   | 
--------------------------------A------------------------ 
                                | 
                       ,--------+----------. 
                       | Finia  stirorgano | 
                       `--------+----------' 
                                 \ 
                                  \_ 
                                    \ 
                                     \ 
     ---------------------------------V----------------------- 
       |   | # |s1|s2| ....... |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.

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

kie (kp aŭtomato)

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

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