TEORIA DELLA COMPUTAZIONE ED AUTOMI FINITI

informatica

TEORIA DELLA COMPUTAZIONE ED AUTOMI FINITI

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 242d39c '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).

L'automa riesce a raccogliere informazioni sullo svolgimento del calcolo e riesce a riconoscere le proprietà di ogni singola funzione. Tale funzione può essere rappresentata in vari modi:

Utilizzando una tabella in cui vengono messi in funzione i dati di "q" e quelli di "s" assegnando un valore a "T".

Mediante una rappresentazione grafica chiamata grafo di transizione. Questi consistono in particolari grafi, strutturanti dall'unione di tante sferette che rappresentano gli stati dell'automa, collegate tra loro da tanti vertici orientati che indicano le transizioni.

MACCHINA DI MEALY

E' un automa con 5 entità:

X = Insieme di ingressi;

Z = Insieme di uscite;

S = Stati interni;

sigma = Transizione (X * S S);

Lambda = Funzione di uscita (X * S Z).

MACCHINA DI MOORE

E' un automa con 5 entità:

X = Insieme di ingressi;

Z = Insieme di uscite;

S = Stati interni;

sigma = Transizione (X * S S);

Lambda = Funzione di uscita (S Z).