Finia aŭtomato

Finia aŭtomato 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:

$M=(\Sigma ,Q,q_{0},F,\delta )$,

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;
• $Q$ estas la aro da internaj statoj;
• $q_{0}$ estas la komenca stato $(q_{0}\in Q)$;
• $F$ estas la aro da finaj, aŭ akceptaj statoj (a) $(F\subset Q)$;
• $\delta$ estas la transirfunkcio, ĵeto $\delta \colon Q\times (\Sigma \cup \{\Lambda \})\rightarrow Q$ tia, ke $\delta (q,a)=\{r\colon q\,\,{\underset {a}{\to }}\,\,r\}$, 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 $q_{0}$; ĝ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 $q'$. Se tiu stato estas unu el la finstatoj, $q'\in F$, tiam oni diras, ke la aŭtomato akceptis la enigaĵon.

Ekzemplo

Jen estas ekzemplo de finia determinisma aŭtomato:

Σ = {0, 1}

Q = (q₀, q₁, q₂)

δ estas difinita per la tabelo:

	0	1
q0	q0	q1
q1	q2	q0
q2	q1	q2

F = {q₀} (q₀ 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 q₀ transiros en la staton q₁. Poste venas 0, kaj de la stato q₁ la aŭtomato transiros en la staton q₂. Venas 1, kaj de la stato q₂ la aŭtomato transiros en la staton q₂ (do, restas en la sama stato). Fine venas ankoraŭ unu 1, la aŭtomato ankoraŭfoje transiras en la saman staton q₂; la enigaĵo finiĝis, la aŭtomato restis en la stato q₂, 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 1011₂ = 11₁₀, ĝ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):

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