Automi finiti

Symbol Meaning Example
Q finite set called the States sciacquo, carico, centrifuga, scarico, lavaggio
Σ finite state called Alphabet on, off, error
δ:QxΣ→Q transition function carico x on → lavaggio
q0∈Q start state scarico
F⊆Q Set of accepted states scarico finale

Un automa a stati finiti può accettare o non accettare una serie ordinata di valori del dizionario.
Dato un entrypoint (quello definito come q0), se al termine della serie di valori sono arrivato a un elemento Q appartenente a F, allora la serie è valida ed è accettata dall'algoritmo, altrimenti no.

Per esempio, questo:

è un automa descrivibile come: ({q1, q2}, {0,1}, δ, q1, q2})

dove δ è definito come

0 1
q1 q1 q2
q2 q1 q2

in questo automa, la sequenza 100 non è valida, perché termina su un elemento che non è uno stato accettato (cioè non appartiene a F).

1101 invece termina in q2, che appartiene a F. Quindi 1101 è una sequenza accettata.

Il significato dell'automa - non sempre così facile da comprendere - è che le uniche stringhe accettate sono quelle che terminano con 1.

L(M) = {w | w ends in a 1}