Finia aŭtomato

Finia aŭtomatoKomputada Leksikono. estas abstrakta maŝino sen ekstera memoro, nombro de kies statoj
(kies interna memoro) estas finia.

Estas pluraj manieroj difini la algoritmon, per kiu funkcias finia aŭtomato. Ekzemple, oni povas specifi ĝin per kvinopo da aroj:
 ,
kie
 Σ estas la enigaĵa alfabeto (finia aro da enigaĵaj signoj), el kiu konstruiĝas enigaĵoj, t.e. vortoj ricevataj de la finia aŭtomato;
  estas la aro da internaj statoj;
  estas la komenca stato ;
  estas la aro da finaj, aŭ akceptaj statoj (a) ;
  estas la transirfunkcio, ĵeto  tia, ke , t.e. duopon
〈stato, enigaĵa signo aŭ vakuo〉 δ ĵetas al la aro da ĉiuj statoj, al kiuj povas transiri la aŭtomata ricevinte tian enigaĵon dum ĝi estas en la indikita stato.

Do, la finia aŭtomato komencas sian laboron en la stato ; ĝi laŭvice legas po unu la signojn de la enigaĵo, kaj ĉiu legita signo transigas la aŭtomaton en novan staton, laŭ la transirfunkcio.

Tiel legante la enigaĵon kaj transirante de unu stato en alian, la aŭtomato finas la legadon en iu stato . Se tiu stato estas unu el la finstatoj, , tiam oni diras, ke la aŭtomato akceptis la enigaĵon.

 Ekzemplo 
Jen estas ekzemplo de finia determinisma aŭtomato:
 Σ = {0, 1}
 Q = (q0, q1, q2)
 δ estas difinita per la tabelo:
    0  1q0  q0  q1q1  q2  q0q2  q1  q2
 F = {q0} (q0 estas kaj komenca, kaj akcepta stato).

Supozu ke la aŭtomato ricevas la enigaĵon 1011; tiam ĝi
funkcios jene.

Leginte la unuan signon, 1, la aŭtomato el la komenca stato
q0 transiros en la staton q1. Poste venas 0, kaj
de la stato q1 la aŭtomato transiros en la staton
q2. Venas 1, kaj de la stato q2 la aŭtomato
transiros en la staton q2 (do, restas en la sama stato).
Fine venas ankoraŭ unu 1, la aŭtomato ankoraŭfoje transiras en la
saman staton q2; la enigaĵo finiĝis, la aŭtomato restis en
la stato q2, kiu ne estas akcepta stato. La signoĉeno
1011 ne estas akceptita de la aŭtomato.

Fakte, ĉi tiu aŭtomato akceptas la signoĉenojn, kiuj estas obloj de 3,
kaj malakceptas ĉiujn aliajn. La nombro
10112 = 1110, ĝi ne estas trioblo.

 Diagrama prezento 
Anstataŭ la ĉi-supra formala difino eblas uzi pli facile kompreneblan grafikan prezenton (sur la diagramo la statojn simbolas ne Q, sed S kun la samaj malsupraj indicoj):

500px|Finia aŭtomato rekonanta
la trioblojn en la duuma nombrosistemo.

Duobla cirklo markas akceptan staton, la komenclan staton markas sago
venanata «el ekstere», sen elira nodo.

 Piednoto 

Kategorio:Komputiko
Kategorio:Komputaj modeloj