Una macchina a stati finiti con uno o più stati designati come stati di accettare. Input string è accettata se c'è un percorso dallo stato iniziale ad uno stato accetta.