Automa a stati finiti non deterministico: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Struttura della lezione |
Presentazione dell'automa a stati finiti non deterministico |
||
Riga 57:
L'ultima parte della lezione sarà dedicata al teorema di equivalenza tra gli automi a stati finiti non deterministici e quelli deterministici;
la dimostrazione, parzialmente sviluppata con metodo costruttivo, definirà un metodo per attuare la conversione tra i modelli.
=Automa a stati finiti non deterministico=
Nelle occasioni in cui abbiamo introdotto nuovi modelli computazionali è stata sempre seguita la convenzione di partire dalla rappresentazione di un dispositivo fisico che si comporti in modo paragonabile al modello da analizzare.
Nel caso degli automi a stati finiti non deterministici, il dispositivo fisico è identico al caso deterministico: un'unità di controllo, un nastro suddiviso in celle e una testina di lettura.
La differenza, in questo caso, risiede nel principio di funzionamento dell'unità di controllo, che ci apprestiamo ad analizzare dettagliatamente.
==Condizioni iniziali e ciclo di lavoro==
Inizialmente l'unità di controllo si trova nello stato di partenza e la testina di lettura viene posizionata sopra la cella più a sinistra del nastro.
A questo punto viene avviato il ciclo di lavoro, che si sviluppa come segue:
# viene letto un simbolo dal nastro d'ingresso;
# in base allo stato attuale e al simbolo letto, si determina un insieme di stati prossimi;
# se l'insieme degli stati prossimi è l'insieme vuoto, si interrompe l'esecuzione nello stato attuale.
# immaginiamo di avere una macchina identica per ognuno degli stati prossimi, facendo in modo che il suo stato coincida con uno di quelli definiti al punto 2.
Le macchine vengono avviate in parallelo ed il ciclo prosegue, per tutte, dal punto 1.
Il punto più delicato del ciclo di lavoro è sicuramente l'ultimo, che si può parafrasare in questo modo: quando ad uno stesso simbolo corrispondono più transizioni, l'automa non deterministico le segue tutte in parallelo.
Dall'analisi del ciclo di lavoro possiamo anche dedurre che non tutti gli automi che vengono azionati in parallelo terminano la loro computazione: è infatti possibile che, in un determinato stato, la ricezione di particolari simboli d'ingresso non inneschi alcuna transizione.
In questa situazione, già riscontrata negli automi a stati finiti, la funzione di transizione è parziale.
È importante, in questo contesto, dare un senso al concetto di ''terminazione'' di una computazione: per il presente modello, la computazione viene completata quando non ci sono più simboli da leggere dal nastro d'ingresso.
Ciò significa che la computazione non termina quando, pur essendoci ancora simboli da leggere, l'automa non è più in grado di cambiare il proprio stato.
Nel contesto attuale, il non determinismo è rappresentato da due aspetti:
* a partire da uno stato, un unico simbolo d'ingresso può attivare più di una transizione;
* a partire da uno stato, un simbolo d'ingresso può non attivare alcuna transizione.
Accanto a questi aspetti, gli automi a stati finiti non deterministici hanno la possibilità di effettuare transizioni senza leggere simboli dal nastro d'ingresso;
i cambiamenti di stato che avvengono senza leggere simboli dal nastro d'ingresso si chiamano ''<math>\epsilon</math>-mosse''.
{| style="border: 1px solid black; height: 50px; margin-bottom: 20px; margin-top: 20px"
| |||