Finia aŭtomato

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search

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. Ekz‑e 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[redakti | redakti fonton]

Jen estas ekzemplo de finia determinisma aŭtomato:

Σ = {0, 1}
Q = (q0, q1, q2)
δ estas difinita per la tabelo:
  0 1
q0 q0 q1
q1 q2 q0
q2 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 ebloj de 3, kaj malakceptas ĉiujn aliajn. La nombro 10112 = 1110, ĝi ne estas trioblo.

Diagrama prezento[redakti | redakti fonton]

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

Finia aŭtomato rekonanta la trioblojn en la duuma nombrosistemo.

Duobla cirklo narkas akceptan staton, la komenĉan staton markas sago venanata «el ekstere», sen elira nodo.

Piednoto[redakti | redakti fonton]

  1. Komputada Leksikono.