Automa a stati finiti non deterministico: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica
Struttura della lezione
Riga 47:
Come avremo modo di vedere, nel caso peggiore, a partire da un automa non deterministico dotato di <math>n</math> stati è possibile ricavare un automa equivalente deterministico dotato di <math>2^n</math> stati;
la semplificazione introdotta dal nuovo modello computazionale è quindi evidente.
 
=Struttura della lezione=
Nella prima parte della lezione verrà presentato il concetto di automa a stati finiti non deterministico, trascurando sia il suo ruolo come accettore, sia quello come trasduttore di linguaggi.
In questo modo si potranno studiare le caratteristiche salienti del modello, concentrandosi sull'elemento che lo caratterizza maggiormente: la funzione di transizione.
 
Una volta definita la versione più elementare del modello computazionale, verranno presentate ed analizzate due varianti: l'accettore non deterministico ed il trasduttore non deterministico;
questi nuovi formalismi verranno studiati servendosi di alcuni esempi, sviluppati dettagliatamente.
 
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.
 
{| style="border: 1px solid black; height: 50px; margin-bottom: 20px; margin-top: 20px"