Automi a stati finiti

premi qui per vedere la dispensa completa.

Uno degli argomenti più importanti che oggi entra in gioco nei corsi di matematica e fisica è il processo di modellizzazione: in questo processo si parte da una descrizione della realtà così come si presenta e si perviene ad una sua rappresentazione (modello).
L'introduzione dell'informatica nello studio della matematica e della fisica ha portato ad una proliferazione di modelli di diversa natura: la matematica che ci permette di rappresentare la "realtà" fisica in termini quantitativi assume ora volti diversi: funzioni, grafici sul piano cartesiano, logica proposizionale e predicativa, insiemi, algebra booleana, circuiti logici, diagrammi di flusso, automi, calcolo combinatorio e calcolo delle probabilità. Questa pluralità, come ogni aumento di libertà, ci mette in una situazione inizialmente difficile dal momento che ci costringe ad un approccio "problematico" in cui dobbiamo scegliere delle strategie non precostituite, ma consente una grandissima integrazione tra gli insegnamenti della fisica, della matematica e dell'informatica.

Succede così che, non potendo seguire sequenzialmente questo o quel libro di testo, diventa necessario reperire materiale didattico da tutte le fonti possibili e produrne anche di proprio.
Imbattutomi spesso nel concetto di automa, in particolare di automa a stati finiti, e non trovando sufficienti elementi nei testi per il biennio (soprattutto per quanto attiene esempi concreti), ho raccolto e adattato un gruppo di problemi tratti da: alcuni testi di "teoria dei sistemi" per I.T.I., appunti di corsi di aggiornamento, "Luccio - Strutture, Linguaggi, Sintassi - Boringhieri", "Balossino - Informatica - Lattes", "Callegarin,Varagnolo - corso di informatica generale - Cedam", appunti personali.
In questa dispensa ogni automa è rappresentato solamente mediante il relativo grafo orientato, ma è sicuramente interessante prendere in considerazione anche la rappresentazione logica (diagramma di flusso) dell'automa e la sua traduzione in un linguaggio di programmazione, oppure ancora si può "tradurre" l'automa in un circuito elettrico corrispondente.
La prima parte della dispensa è dedicata ad illustrare i concetti di sistema, modello, automa, automa a stati finiti. Il corpo centrale contiene la descrizione e il grafo di 24 automi a stati finiti tra i quali sono presenti i soliti distributori di bevande, distributori di gettoni, cambia-monete, riconoscitori di sequenze, controllori di parità, ascensore, porte di una banca, microlinguaggi. Infine sono date alcune indicazioni su come realizzare il diagramma di flusso e il programma Pascal di un automa a stati finiti.
La dispensa, i listati dei programmi e gli stessi programmi su dischetto sono reperibili presso A.I.F. di Cagliari. (Colgo l'occasione per invitarti, se non lo sei, ad iscriverti).
Di seguito è fornito un esempio di automa.

Anche un solo esempio mostra la "valenza" didattica dell'argomento, che può evolvere dalla descrizione generale del funzionamento dell'automa all'individuazione degli stati, degli ingressi e delle uscite, al grafo , al diagramma di flusso fino alla stesura del codice Pascal (o altro linguaggio). L'automa si ispira ad uno dei "problemi" in cui può incorrere l'acquirente di un fustino di detersivo: la regolazione di un orologio digitale.

Descrizione. L'automa è un sistema di regolazione di un orologio digitale. L'orologio è munito di tre pulsanti la cui pressione chiameremo P1, P2, P3 che servono per la regolazione delle ore, minuti, mese, giorno e per il passaggio dalla modalità del display in cui vengono mostrati ore e minuti alla modalità in cui vengono mostrati mese e giorno.Il tasto P1 serve per passare dallo stato in cui il display mostra ore-minuti agli stati di regolazione, il tasto P2 serve per incrementare il valore attualmente presente sul display (inc=incrementa), il tasto P3 è un tasto bistabile tra le modalità del display ore-minuti e mese-giorno.

Ecco il grafo:


Lino Talloru

premi qui per vedere la dispensa completa.


per un altro automa

per l'home page