Gli automi

Gli automi sono modelli di elaborazioni basati sui linguaggi regolari.

Tipi di automi

Esistono due tipologie di automi a stati finiti

• Automi deterministici (DFA)
  In ogni stato è indicata una e una sola transizione per ogni evento.
• Automi non deterministici (NFA)
  In uno stato non sono indicate le transizioni per ogni evento. Inoltre, per un dato evento possono esistere anche più transizioni dallo stesso stato di partenza.

Pro e contro degli automi

Gli automi hanno i seguenti vantaggi

• La semplicità
  Il punto di forza degli automi è la semplicità di interpretazione.

Gli automi hanno i seguenti svantaggi

• Linguaggi regolari
  Gli automi hanno un potere descrittivo limitato perché accettano soltanto i linguaggi regolari.

  Nota. I sistemi che utilizzano linguaggi formali non regolari non possono essere rappresentati da un'automa. In questi casi occorre usare altri linguaggi formali come le reti di Petri o la macchina di Turing.

Automa semplice

Un automa semplice elabora un evento in ingresso alla volta e produce una transizione verso uno stato.

Una sequenza di eventi genera una sequenza di transizioni ed eventuali cambiamenti di stato.

Nota. Non necessariamente un evento determina un cambiamento dello stato. Alcune transizioni generano la permanenza sullo stesso stato ( cappio ).

Automi con più ingressi e uscite

Un automa con più ingressi e più uscite può elaborare più eventi in entrata e in uscita.

Un esempio tipico è il dispositivo di controllo.

Tipi di automi

I modelli di automi si classificano in due categorie

• Modelli Logici
  Gli automi logici considerano soltanto gli eventi. Non prendono in considerazione il tempo. Generalmente, sono realizzati tramite sistemi a eventi discreti (SED).
• Modelli temporizzati
  Gli automi temporizzati considerano gli eventi e gli istanti temporali in cui si verificano. Pertanto, prendono in considerazione il fattore tempo. Possono essere realizzati con modelli a eventi discreti temporizzati o sistemi ad avanzamento temporale (SAT).

E così via