Sintassi e Semantica: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
m Bot: Sostituzione automatica (-<br/> +<br />)
Riga 11:
 
===La sintassi: Gli automi a stati finiti===
I riconoscitori in grado di verificare che una certa stringa appartenga o meno ad un certo linguaggio, possono essere definiti come macchina a stati. questo perché, nel processo di riconoscimento di una stringa, c'è un preciso momento in cui, quando stiamo esaminando un singolo simbolo della stringa, il processo può proseguire nel riconoscimento oppure fermarsi; questi vari momenti vengono chiamati stati. Il processo di riconoscimento funziona in questo modo: viene presa una certa stringa di simboli del linguaggio, nel primo stato della macchina viene controllato il primo simbolo: se questo trova una o più "vie" verso lo stato successivo, la computazione continua andando a considerare il simbolo successivo e così via. La computazione termina quando i simboli sono finiti e ci troviamo in uno stato finale, e quindi possiamo affermare che la stringa fa parte del linguaggio, quando i simboli sono finiti ma non ci troviamo in uno stato finale oppure quando il simbolo che esaminiamo no trova una "via" da continuare; in questi ultimi due casi, la stringa non è riconosciuta.<br />
Formalmente, un automa (macchina a stati) può essere definito con la seguente quintupla: <A,E,S,F,G>, dove A rappresenta l'alfabeto del linguaggio che stiamo considerando, E l'insieme finito degli stati dell'automa, S lo stato iniziale (quindi S appartiene all'insieme E), F l'insieme finito degli stati finale, G ci rappresenta un'associazione tra una coppia ed uno stato, del tipo:<br />
<a,s>-->s1; ovvero se mi trovo nello stato s e stò esaminando il simbolo a, posso continuare la computazione nello stato s1 esaminando il simbolo successivo ad a.
 
====Macchina a stati====
Per poter meglio rappresentare il funzionamento dei riconoscitori che abbiamo descritto prima, esiste una speciale rappresentazione grafica che prende il nome di macchina a stati. Questo perché, durante la computazione, è possibile specificare i precisi momenti in cui avviene una transizione; questi particolari momenti nella computazione, si chiamano appunti stati.<br />
Vengono utilizzati particolari simboli: nodi, per rappresentare stati, archi, per rappresentare le transizioni tra due stati. <br />
I nodi sono rappresentati come cerchi, mentre gli archi sono rappresentati come frecce; sia i nodi che gli archi sono etichettati con dei simboli, ovvero i nodi sono etichettati con il simbolo dello stato che rappresentano, gli archi sono rappresentati con l simbolo del linguaggio che permette di passare da uno stato precedente ad uno successivo. <br />
Tra i nodi possibili, esistono due tipi di nodi particolari: il nodo di inizio, rappresentato da un arco entrante ma che non proviene da nessun altro nodo; questo nodo ci rappresenta lo stato iniziale. I nodi terminali o finali sono >=1, e ci rappresentano tutti quei possibili stati in cui la computazione può terminare, e sono rappresentati da un doppio cerchio.