|
|
Una tecnica di programmazione molto utile e significativa consiste nella costruzione
e "simulazione" di automi o macchine a stati finiti. Formalmente, un automa
finito M è un sistema 
dove K è un insieme finito e non vuoto di stati in cui si può trovare M;
è un alfabeto finito di simboli
di ingresso;
è la funzione di transizione di
stato, che dato uno stato e un simbolo letto dice in quale stato andrà M;
q 0 è lo stato iniziale;
F è l'insieme degli stati finali.
L'automa parte dallo stato q0 e legge un simbolo
(cioè, un dato) alla volta. A seconda dello stato in cui si trova, la lettura
del simbolo gli fa cambiare stato, fino a raggiungere uno stato finale, che
corrisponde a uno dei possibili risultati della computazione. Un automa può
essere convenientemente rappresentato in forma tabulare (tabella degli stati)
o in forma grafica. Ci sono molti problemi che possono essere risolti in modo
elegante definendo un automa appropriato. Si supponga per esempio di dover scrivere
un programma che filtra un file sorgente C, C++ o Java eliminando tutti i commenti,
che sono di due tipi:
commenti che iniziano con i due simboli // e si estendono
fino alla fine della linea;
commenti racchiusi tra i due simboli /* e */.
Risolveremo
questo problema definendo un automa che legge un file di ingresso un carattere
alla volta e, a seconda dei caratteri letti, si troverà in uno dei cinque stati
seguenti:
1 è lo stato iniziale, in procinto di copiare i caratteri letti,
che non appartengono a un commento. Se viene letto il carattere "/", l'automa
passa nello stato 2;
2 incontrato il carattere "/" se viene letto ancora il carattere "/", l'automa
passa nello stato 3; se viene letto il carattere "*", l'automa passa nello stato
4; altrimenti torna allo stato 1;
3 dentro un commento, in procinto di scartare tutti i caratteri letti; se viene
raggiunta la fine della linea, l'automa ritorna nello stato 1;
4 dentro un commento racchiuso tra i due simboli /* e */, in procinto di scartare
tutti i caratteri letti; se viene letto il carattere "*", l'automa passa allo
stato 5;
5 se viene letto il carattere "/", l'automa passa allo stato 1, altrimenti passa
allo stato 4, a meno che non venga letto il carattere "*", nel qual caso l'automa
rimane in questo stato.
Si possono a questo punto scrivere cinque sottoprogrammi per ognuno degli stati,
in modo che a seconda dello stato in cui si trova l' automa, venga eseguito
l'uno o l'altro sottoprogramma.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.