FSA

Un automa a stati finiti (FSA) è un modello matematico di una semplice macchina. Il sistema può trovarsi in un numero finito di stati possibili.

Si distinguono diverse classi di FSA a seconda dei vincoli imposti alla loro formalizzazione.

DFA - Automi deterministici
NFA - Automi non deterministici
e-NFA - Automi non deterministici con epsilon transizioni

Si dimostra tuttavia che tutte le classi di automi sono tutte tra loro equivalenti. Gli automi così descritti sono in grado di riconoscere tutti e soli i Linguaggi Regolari.

---

Torna ad Informatica Teorica