AUTOMA RICONOSCITORE

Stati

Gli stati sono indicati con una S e un numero, gli stati finali hanno scritto < finale> e il numero

Nodi

I nodi sono rappresentati da un dizionario che come chiave ha il suo stato e come valore ha un altro dizionario, dove per ogni carattere possibile, indica un altro stato: {"S1": {"A": "S1", "B": "S2"}}.

Come funziona

L'algoritmo segue questi step:

1. Ordinamento sequenze
   Le sequenze che sono già contenute all'inizio di un altra sequenza verranno eliminate (verranno comunque onservate per capire quali stati sono finali)
2. Creazione nodi iniziali
   Inizialmente vengono creati tutti i nodi necessari per la creazione, vedendo quali nodi servono se si inseriscono solo caratteri "giusti".
   Ogni nodo contiene una lista sequenze, che indica quali sequenze quel nodo deve riconoscere, una lista attuale, che indica quali sequenze sono state inserite fino al quel nodo, un dizionario puntaA, dove la chiave è il carattere e il valore è a quale nodo punta.
   1. Per ogni sequenza S in sequenze controlla se esiste già un collegamento per la prima lettera di S, se esiste allora deve soltanto aggiungere S senza la prima lettera nella lista sequenze del secondo nodo.
   2. Se non esiste allora controlla se esiste già un nodo dove nella sua lista sequenze esiste S senza la prima lettera, se esiste allora la prima lettera di S deve puntare a quel nodo, inoltre deve aggiungere ad attuale del secondo nodo, ogni elemento di attuale di questo nodo + la prima lettera di S.
   3. Se non esiste allora deve craere un nuovo nodo.
3. Creare tutti i collegamenti
   Adesso per ogni nodo bisogna controllare se manca un carattere. Se manca un carattere allora si cerca a quale nodo bisogna collegarlo in questo modo:
   1. Itera per ogni sequenza in attuale e ci aggiunge il carattere mancante (creando S).
   2. Itera per ogni nodo e cerca quale ha una sequenza in sequenze che se aggiunta a S crea una sequenza da riconoscere.
   3. Se la trova allora si collega a quel nodo.
   4. Se non lo trova allora leva la prima lettera di S e ricomincia dal punto 2.
4. Definire nodi finali
   I nodi finali sono tutti i nodi che nella loro lista sequenze contengono una sequenza da riconoscere.