ragazza disegna
la la casa SF
Gli automi finiti
Un automa finito è un dispositivo caratterizzato da un numero finito di stati e dotato di una testina di lettura, grazie alla quale l’automa può esaminare un nastro finito diviso in caselle (stati). Ogni casella può contenere un simbolo appartenente a un alfabeto finito. All'interno dell'insieme finito di stati distinguiamo lo stato iniziale, degli stati intermedi e lo stato finale, gli stati sono collegati tra loro da un certo numero di transizioni. L’automa procede da sinistra a destra, leggendo un simbolo alla volta e cambiando uno stato alla volta in base a un determinato percorso che va da sinistra a destra. Nella rappresentazione qui di seguito:
t1 t2 t3 t4
lo stato iniziale è SI, mentre S1, S2, S3 sono stati intermedi e SF è lo stato finale. La transizione t1 collega lo stato iniziale SI allo stato intermedio S1, la transizione t2 collega S1 a S2, fino alla transizione t4 collega S3 allo stato finale SF. Questo tipo di rappresentazione è detto grafo e gli stati sono anche definiti nodi.
Poniamo il caso che i simboli siano le parole dell’italiano “la, casa, ragazza, disegna” ed etichettiamo i nodi del grafo utilizzando tale insieme.
SI
Questo automa legge il simbolo la, transiterà nel secondo stato, tenendo memoria di quanto ha letto nel primo; dopo aver letto ragazza, determinerà la sequenza la ragazza e continuerà in questo modo fino ad arrivare al nodo finale, cioè alla fine del percorso, determinando la sequenza finita di simboli
La ragazza disegna la casa. Se, a un dispositivo di questo tipo, sottoponiamo le due sequenze di
simboli La ragazza disegna la e la ragazza disegna la casa, l'automa riconoscerà la seconda ma non la prima frase. Un automa come quello che abbiamo appena costruito è detto automa deterministico, perché definisce un unico percorso nel determinare una sequenza di simboli. Un automa è detto invece
non deterministico quando, in un dato punto di tale cammino, più percorsi sono attivi:
ragazza disegna
la la casa SF
va a SI
Questo automa non deterministico, che contiene non solo i simboli “la, ragazza, casa, disegna” ma anche “a, va” definirà le sequenze di simboli la ragazza disegna la casa e la ragazza va a casa.
