La teoria della computazione, si basa su quell’insieme di regole formali del calcolo ed il suo studio è avvenuto solo in periodi molto recenti, verso gli anni ’30. Il modello computazionale che si considera principalmente è l’automa finito. Esso può anche essere chiamato automa a stati finiti, ed è molto usato nella teoria dei sistemi. La caratteristica principale di questi automi è che il loro numero di stati è finito cioè conosciuto a priori, ciò provoca però una forte limitazione da parte dell’automa nel memorizzare più informazioni rispetto ai suoi stati. All’interno di un automa finito troviamo queste cinque entità: • Q = Insieme finito di stati interni (stati); • Σ = Alfabeto d’ingresso; • q = Stato iniziale; • f = Stati finali; • T = Funzione di transizione; Il processo che riguarda l’automa, può essere così schematizzato: L’automa parte da uno stato iniziale (q) ed inizia a leggere la stringa di valori (s) appartenente all’alfabeto di ingresso. Ad ogni stringa l’automa si porta su un nuovo stato tramite una funzione di transizione, in maniera tale che tutto il processo si scrive T(q,s).