Introduzione allo studio dell'informatica teorica: differenze tra le versioni

Per formarsi un'idea di cosa siano gli automi a stati finiti è quindi importante definire il concetto di computazione, che secondo alcuni autori si può far risalire ad un ''comportamento'', intendendo con questo una successione finita o infinita di passi.

 

 

Descrivere una computazione implica la capacità di rappresentare la successione dei passi che la caratterizza, ognuno dei quali viene spesso interpretato come un'''azione'', come uno ''stato'', oppure come una ''transizione'', intesa come una coppia <math>(stato, azione)</math>.

Nelle sezioni seguenti verranno riportati tre esempi con lo scopo di illustrare le tecniche appena introdotte.

 

Supponiamo di voler calcolare l'area di un rettangolo conoscendo il suo perimetro e la lunghezza di uno dei lati.

 

La necessità di questo accorgimento mostra un importante limite di questa tecnica di rappresentazione: è poco comunicativa.

 

Supponiamo di voler rappresentare la computazione precedente impiegando una successione di stati anziché di azioni.

 

Come si può notare questa descrizione riesce a rendere l'idea senza che sia necessario includere informazioni aggiuntive a dimostrazione del fatto che è più espressiva rispetto alla precedente.

 

Anche in questa sezione rappresenteremo la stessa computazione esaminata negli altri due casi, ma impiegando la logica delle transizioni.