Nello scorso articolo abbiamo parlato degli automi, cosa sono e cosa permettono di fare. In questo articolo parleremo invece di come costruire un automa a stati finiti. Iniziamo!

Sappiamo che un automa a stati finiti descrive un sistema, e sappiamo anche che può essere descritto come M=(I,U,S,f,g).

Supponiamo che il sistema da descrivere sia l’accensione di una lampadina. Iniziamo ad analizzare il problema ricorrendo alla vita di tutti i giorni. Cosa fai per accendere la lampadina? Presumibilmente premi un interruttore. E cosa fai per spegnerla? Premi di nuovo lo stesso interruttore.

Partendo da questa descrizione iniziamo ad analizzare il problema in maniera più formale.

• I = Insieme finito dei possibili simboli in ingresso;
• U = Insieme finito dei possibili simboli in uscita;
• S = Insieme finito degli stati;
• f : I x S -> S funzione di transizione degli stati interni successivi, che collega lo stato nell’ istante successivo al valore attuale dell’ ingresso e dello stato;
• g : I x S -> U funzione delle uscite, che collega l’ uscita al valore attuale dell’ ingresso dello stato.

In questo caso:

• I = corrisponde alle azioni, essendo “Premi interruttore”  l’ unica azione possibile, I = {Premi interruttore};
• U = output, in questo caso la lampadina può essere accesa oppure spenta, quindi U = {Accesa, spenta};
• S = in questo caso S = U, in quanto gli stati dell’ automa corrispondono all’ output del sistema;
• f: I x S -> S, pensiamo di partire da uno stato iniziale in cui la lampadina è spenta (q0), premiamo il pulsante e passiamo ad uno stato in cui la lampadina si accende (q1). La funzione che descrive questo comportamento può essere formulata nel modo seguente:

“Premi interruttore“ x q0  -> q1 ed analogamente “Premi interruttore” x q1 -> q0

• g : I x S -> U, ragionamento analogo alla funzione f:

“Premi interruttore” x q0 -> “Lampadina accesa” ed analogamente “Premi interruttore” x q1 -> “Lampadina spenta”

Costruire l’ automa

Gli automi possono essere descritti in due modi:

• Funzione di transizione;
• Rappresentazione grafica.

La funzione di transizione è una tabella che descrive l’ automa sotto forma tabellare o matriciale.

Alle righe associamo gli stati ed alle colonne i simboli in input. Gli elementi della matrice rappresentano il risultato dell’applicazione della funzione di transizione.

La rappresentazione grafica invece permette di visualizzare l’ automa, tramite una determinata sintassi che descriveremo a breve.

Sintassi

Per rappresentare graficamente un automa bisogna avvalersi di determinati costrutti, ovvero:

• Stato: uno stato generico viene descritto da un cerchio, con all’ interno un nome (S2);
• Stato di accettazione: uno stato di accettazione viene descritto da due cerchi concentrici, con all’ interno un nome (S1), lo stato di accettazione serve ad indicare il raggiungimento di una certa condizione.
• Funzione di transizione: si indica con una freccia ed un simbolo. Se la freccia esce ed entra nel medesimo stato vuol dire che l’ automa rimane nello stesso stato (Ciclo).

Svolgimento

Proviamo a costruire un automa che descriva il sistema di cui sopra.

Supponendo che il sistema si trovi in uno stato iniziale in cui la lampadina è spenta, l’ obiettivo sarà quello di portare il sistema in uno stato in cui la lampadina sia accesa:

Viene facile pensare che azionando l’ interruttore una prima volta, si passi ad uno stato (q1) in cui la lampadina sia accesa, avendo raggiunto il nostro obiettivo, possiamo dichiarare q1 stato di accettazione. Allo stesso modo azionando l’ interruttore dallo stato q1, torniamo allo stato iniziale q0.

Proviamo a costruire la tabella della funzione di transizione:

Nel prossimo articolo parleremo della correlazione tra Automi e Linguaggi regolari.

Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.

Alla prossima!