| 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}