Finia aŭtomato
From Wikipedia, the free encyclopedia
Finia aŭtomato[1] 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.