MODELLI DI MEALY E MOORE

Le reti sequenziali sincrone (RSS) si differenziano da quelle asincrone (RSA) per il fatto che lo stato può
evolvere  solo  a  determinati  istanti.  Questi  istanti  sono  determinati  dalla  transizione  da  0  a  1  di  una
particolare  variabile  detta  clock.    Il  generatore  di  segnali  periodici  consente  quindi  la  sincronizzazione
facendo in modo che i valori delle variabili di stato siano presenti simultaneamente.
Quindi, per quanto riguarda l’evoluzione dello stato è come se il tempo fosse discreto e non continuo.
La frequenza di clock indica quante volte il clock passa da 0 a 1 e viceversa nell’unità di tempo. Per esempio
1Mhz = 1 ciclo di clock ogni μs.
Le reti sequenziali sincrone sono di due tipi: 
  Modello di Mealy: l’uscita dipende sia dall’ingresso che dallo stato
  Modello di Moore: l’uscita dipende solo dallo stato
Ed è possibile trasformare una macchina di Mealy in una macchina di Moore equivalente, e viceversa.

 MODELLO DI MEALY
Le regole che descrivono il modello di Mealy sono le seguenti:
•  ogni  volta  che  all’ingresso  dell’automa  si  presenta  un  nuovo  ingresso  I(t)

e
l’automa si trova in un stato S(t), a questa nuova coppia segue un nuovo stato;
questo passaggio viene indicato come transizione da uno stato all’altro ; 
•  ogni  volta  che  all’ingresso  dell’automa  si  presenta  un  nuovo  ingresso  I(t)

e
l’automa si trova in un stato S(t), a questa nuova coppia segue una nuova uscita;
abbiamo allora la trasformazione ingresso-uscita.




Possiamo quindi affermare che le uscite sono funzione degli ingressi e dello stato presente e reagiscono
immediatamente alle variazioni degli ingressi. 
Nelle macchine di Mealy, l’uscita va “letta” mentre la macchina subisce una transizione di stato.
MODELLO DI MOORE
Il modello di Moore si può descrivere nel seguente modo: 
•  ogni  volta  che  all’ingresso  dell’automa  si  presenta  un  nuovo  ingresso  I(t)

e
l’automa si trova in un stato S(t)

, a questa nuova coppia segue un nuovo stato;
questo passaggio viene indicato come transizione da uno stato all’altro; 
•  ogni volta che all’ingresso dell’automa si presenta un nuovo ingresso I(t)

e l’automa
si trova in un stato S(t), a questo stato corrisponde una nuova uscita.

 

In questo caso le uscite sono funzione solo dello stato presente e reagiscono a variazioni degli ingressi solo
al prossimo “colpo” di clock.  Questo impplica che sono meno rapide delle macchine di Mealy.
Nelle macchine di Moore, l’uscita viene letta mentre la macchina si trova in un determinato stato.

DEFINIZIONE GENERALE DI AUTOMA

Un Automa, "per definizione" è un insieme di segnali in entrata, stati interni e segnali in uscita, in modo che per ogni input, dia un output che cambia a seconda dello stato interno in cui il sistema stesso si trova.
Quindi un automa non è altro che un sistema informatico che risponde ai nostri input (digitazioni di dati, numeri, parole,  ecc........) fornendoci, come output una risposta o una azione differente a seconda della sua situazione interna.
Ad esempio un ascensore, è un automa, perchè quando noi digitiamo\scegliamo un piano lui, a seconda di dove gia si trova ( 1° piano, 2° piano, ecc......) sceglierà se salire, scendere o restare fermo.

Oppure un altro esmpio di automa è la macchinetta del caffè o degli spunti\merendine, che quando digitiamo un codice la macchinetta risponde al nostro input con la richiesta all'utilizzatore del denaro e alla fine, risponde consegnandoci cio che è stato scelto in precedenza.
Questi naturalmente, sono degli automi relativamente semplici dette macchine sequenziali o automi sequenziali cioè adibite a compiere un dato compito quando richiesto dall'utente.
Gli automi negli esempi precedentemente illustrati sono definiti in informatica "automi a stato finito" perchè è dotato di un insiemi limitato di stati e controllano una stringa di simboli in entrata (per la macchina sono ancora simboli, alla fine di questo processo li riconoscerà come parole)in maniera ordinata per decidere se appartiene o meno ad un alfabeto a lui noto.
questi tipi di automi sono chiamati delle quintuple perchè sono formati da 5 insiemi che sono:
(Q)=un insieme finito di stati,nel quale si distingue,
un insieme finito di simboli di input Σ,
funzione di transizione che applicata ad un simbolo e ad uno stato restituisce uno stato: δ : Σ ×Q→Q ;
uno stato iniziale (q0) scelto fra gli stati di Q ;
un insieme di stati finali F ⊆Q .
Dunque un automa a stati finiti è una quintupla: A = (Q , Σ, δ , q0, F ).
 Un "automa a stati finiti" può essere espressoelencando le sue componenti e descrivendo la funzione di transizione, oppure mediante un grafo detto diagramma delle transizioni di stato o mediante una matrice
di transizione.
Dato un automa a stati finiti deterministico questo definisce un linguaggio sull’alfabeto Σ, costituito da tutte le stringhe ottenute concatenando le etichette presenti sul grafo delle transizioni sugli spigoli dei cammini che vanno dallo stato iniziale ad uno degli stati accettanti.
In altre parole il linguaggio L su Σ definito da A =(Q , Σ, δ , q0, F ) è dato da tutte le stringhe che producono una sequenza di transizioni dallo stato iniziale q0 ad uno degli stati accettanti di F .
Conˆ δ indichiamo la funzione di transizione estesa, che descrive cosa succede
(in quale stato si arriva) quando, a partire da un certo stato, l’automa elabora non
un solo simbolo, ma una stringa costituita da una sequenza di simboli.
Possiamodefinire ricorsivamente la funzione di transizione estesa (con ε indicheremo d’ora
in avanti la stringa vuota):

Allora il linguaggio di un automa a stati finiti deterministico A = (Σ,Q , δ , q0, F ) è de-finito come L( A) = {w :ˆδ (q0, w ) ∈ F }. I linguaggio L = L( A) per qualche automa a stati finiti deterministico A si chiamano linguaggi regolari.
Un automa a stati finiti non deterministico  è un automa che può trovarsi contemporaneamente in diversi stati. Anche un  si definisce come una quintupla A = (Σ,Q , δ , q0, F ), dove:
• Σ è l’alfabeto finito di simboli;

• Q è l’insieme finito di stati;
• q0 ∈Q è lo stato iniziale;
• F ⊆Q è l’insieme degli stati finali accettanti;
• δ è una funzione δ : Q ×Σ → P (Q ),che a fronte di un simbolo e di uno stato
restituisce un sottoinsieme degli stati (dunque anche più di uno stato).

 In parole semplici il funzionamento di un automa si può spiegare in tre veloci punti:

1. partendo dallo stato iniziale e dal primo simbolo della stringa in ingresso si decide in base alla funzione di transitare in un determinato stato (potrebbe anche essere lo stesso stato);
2. finché esiste un altro simbolo nella stringa da scandire si opera alla stessa maniera fino ad esaurire la stringa in ingresso;
3. la stringa si dirà "accettata" se si giunge in uno stato appartenente al sottoinsieme degli stati finali.

Tali automi sono in grado di riconoscere i linguaggi regolari.
Gli automi con output invece sono una classe differente da quella prima spiegata infatti, tale classe di automi a stati finiti può associare l'emissione di simboli appartenenti ad un altro alfabeto detto "di output". Questi automi vengono chiamati macchine di Moore o di macchina di Mealy, a seconda che l'output sia associato agli stati (caso più particolare), o alle transizioni fra stati.