Come implementare un automa di Mealy

Per i meno esperti è doveroso fornire una spiegazione su cosa sia l'automa, o macchina, di Mealy.
Questo è un particolare modello in cui ogni spostamento del dato (E quindi in sostanza il dato in uscita da una generica operazione) dipende da una doppia e cioè dal dato entrante in ingresso e dallo stato precedente. Questa va differenziata con la macchina di Moore dove l'uscita dipende solo dallo stato.
La definizione formale della macchina è descritta da una sestupla e in generale si descrive cosi:
{S, S0, E, A, T, G}
Dove:
- S è un'insieme finito di dati
- S0 è uno stato iniziale che è elemento di S
- E è un insieme finito degli ingressi
- A è un insieme finito di uscite
- T è una funzione di transazione e viene indicata con T: SxE -> S
- G è una funzione d'uscita e viene indicata con SxE -> A
Ecco quindi una breve guida su come implementare un automa di Mealy.

Prima di passare all'esercizio vero è proprio (per chi non fosse riuscito ad afferrare il concetto esposto precedentemente) viene proposto qui un esempio.
Si consideri una macchinetta che rilascia bibite (ognuna di esse dal prezzo di 50 cent.) dopo aver ricevuto un inserimento di un certo numero di monete. Le monete accettate saranno 10, 20 e 50 cent.
Per costruire il grafico si consideri che se si parte dall'inserimento di 50 cent. Oppure 0 cent. Lo stato non cambierà ma nel primo caso vi sarà un'uscita (corrispondente al rilascio della bibita). Se si inserisce 10 cent o 20 cent si ricadrà in insieme differenti. Con la combinazione finale tra 10 e 20 cent. Si otterrà un grafico ciclico se si inseriranno sempre 10 cent. E uno che rilascia un'uscita dopo due inserimenti da 20 cent.

Partendo da un esercizio dato bisogna prima di tutto individuare l'insieme dell'ingresso, scrivendolo eventualmente in alto, tenendo conto che vanno inseriti in questo caso anche il minimo (Di solito indicato con 0) e il massimo, se non è specificatamente richiesto di farne a meno. Si consideri poi uno stato iniziale in cui l'ingresso è 0 (o comunque uno stato in generale detto "neutro"). A questo punto, per ogni ingresso stabilito nell'insieme iniziale, creare uno stato proprio. In questo modo si avranno inizialmente n stati. Ora fare passare ad uno stato successivo e reinserire di nuovo l'insieme di ingressi in base all'esercizio. Eseguendo questo processo per ogni stato sarà possibile ottenere un grafico completo con massimo 5 stati considerabili (essi possono essere anche infiniti ma in questo caso per effettuarne una semplificazione è necessario l'ausilio di strumenti esterni e appositi).

Nella tabella delle transazioni vengono inseriti tutti i dati ottenuti dal grafo e questi vengono "codificati" per essere semplificati. Se per esempio il nostro insieme di riferimento è composto da 8 elementi, saranno necessari 3 bit (e cioè 3 valori in quanto 3^2=8). Essa è una tabella riassuntiva in quanto l'esercizio vero è proprio consiste nella creazione del grafo sopra spiegata.

• Come implementare un automa di Moore