Automa a stati finiti non deterministico: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Presentazione dell'automa a stati finiti non deterministico |
Definizione di automa a stati finiti non deterministico |
||
Riga 85:
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''.
==Definizione di automa a stati finiti non deterministico==
Un automa a stati finiti non deterministico è una terna ordinata di valori <math>N=(Q, I, \delta)</math> definiti come segue:
* <math>Q</math> è un insieme finito di stati;
* <math>I</math> è un insieme finito di simboli detto alfabeto d'ingresso;
* <math>\delta : Q \times I \cup \left \{ \epsilon \right \} \rightarrow \mathcal{P}(Q)</math> è la funzione di transizione.
La definizione di funzione di transizione merita un commento più specifico.
Anzitutto si nota che gli elementi dell'insieme di partenza sono coppie ordinate in cui il primo elemento è sempre uno stato, mentre il secondo può essere o un simbolo dell'alfabeto d'ingresso, oppure la stringa vuota.
In questo modo si tiene conto della possibilità di non leggere nulla dal nastro d'ingresso.
L'insieme d'arrivo è indicato con la dicitura <math>\mathcal{P}(Q)</math>, che indica l'insieme delle parti dell'insieme degli stati;
come conseguenza gli elementi dell'insieme d'arrivo sono sottoinsiemi dell'insieme degli stati: in questo modo un solo simbolo d'ingresso può innescare contemporaneamente più transizioni.
{| style="border: 1px solid black; height: 50px; margin-bottom: 20px; margin-top: 20px"
| |||