Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Adriano Peron » 4.FSM: Macchine a Stati Finiti


Automa regolari

Automa regolare: la forma più nota di macchina Stato-Transizione a stati finiti.

Stati:

  • il numero degli stati è finito;
  • la sola componente dello stato è quella legata al controllo;
  • non vi sono variabili o strutture dati;
  • gli stati non presentano nessuna forma di strutturazione.

Transizioni:

  • il Trigger è un evento semplice;
  • non vi è nessuna Condizione;
  • non vi è nessuna Azione.
Fig.1: Esempio di automa regolare.

Fig.1: Esempio di automa regolare.


Automi regolari (segue)

Un automa regolare A è una tupla

\langle\Sigma ,Q, q_{0}, \Delta ,F \rangle , dove

  • \Sigma è l’alfabeto (finito) di input;
  • Q è l’insieme finito di stati;
  • q_{0} è lo stato iniziale;
  • \Delta \subseteq Q \times \Sigma \times Q è la relazione di transizione;
  • F \subseteq Q è l’insieme degli stati finali.

Determinismo
L’automa è deterministico quando

\langle q,a,q'\rangle,\langle q,a,q''\rangle \in Q \mbox{ implica } q' =<br />
q''

Automi regolari: comportamenti

Un comportamento (run) di A è una sequenza

q_0 \stackrel{a_0}{\rightarrow}q_1 \stackrel{a_1}{\rightarrow} \ldots\stackrel{a_{n-1}}{\rightarrow} q_n

dove \langle q_i, a_i, q_{i+1} \rangle  \in \Delta \mbox{  per ogni }0\leq i \leq n-1.

Interpretazione: comportamento dell’automa a fronte di una sequenza a_0\ldots a_n di sollecitazioni dall’ambiente esterno.

Tradizionalmente un automa regolare viene proposto come macchina per il riconoscimento di linguaggi regolari, qui si enfatizza invece la reattività all’ambiente.

Una parola a_0\ldots a_n \in \Sigma^* è accettata dall’automa A se esiste un run

q_0 \stackrel {a_0} {\rightarrow}q_1 \stackrel{a_1}{\rightarrow} \ldots<br />
\stackrel{a_{n}}{\rightarrow} q_{n+1} \mbox{ con } q_{n+1}\in F.

Il linguaggio accettato da A è l’insieme L(A)=\{v: \mbox{ \`e accettato da } A\}.

Automi regolari: Semantica

Semantica espressa in termini di LTS.

L’LTS per l’automa regolare A è il grafo etichettato su \Sigma

\langle\{ q_0\},Q,\Delta\rangle

Si osserva che vi è coincidenza tra LTS ed automa e che un run di A è un cammino nell’LTS a partire dallo stato iniziale.

Osservazione: Gli automi regolari sono un formalismo di specifica di basso livello che coincidono con la struttura semantica.

Interpretazione tradizionale: gli automi regolari sono accettori di linguaggi (finitari).

Il linguaggio accettato da un automa potrebbe essere già visto come la semantica dell’automa (visione tradizionale che astrae dai comportamenti oggetto di specifico interesse nella specifica).

Automi regolari: macchine reattive

Un automa è una macchina che reagisce agli stimoli di un ambiente esterno.

Caratteristiche e limiti.

  • La reazione agli stimoli è regolata da una nozione temporale implicita; si assume un dominio temporale discreto (ad esempio i naturali) e si suppone che l’i-esimo simbolo della parola sia comunicato dall’ambiente alla macchina al tempo i-esimo;
  • l’interazione ambiente-macchina avviene in tempo finito seppur illimitato;
  • la macchina reagisce allo stimolo esterno in modo strettamente sequenziale;
  • il flusso comunicativo è mono-direzionale (dall’ambiente alla macchina);
  • le mosse interne della macchina sono in corrispondenza biunivoca con le sollecitazioni (non ci sono mosse interne non controllate dall’esterno).

Automi regolari: caratteristiche

Potere espressivo: I limiti espressivi sono strettamente legati alla finitezza dello stato e alla mancanza di strutture dati (su domini illimitati).

Non adeguati a rappresentare sistemi che richiedono un numero illimitato di stati:

  • strutture dati su domini illimitati;
  • strutture di controllo con chiamate ricorsive ect.

Naturalezza espressiva: è formalismo di specifica di basso livello.
Non consente la rappresentazione esplicita di:

  • modularità verticale dei sistemi (strutturazione top-down); il sistema per essere rappresentqto deve essere appiattito (flattening);
  • modularità orizzontale del sistema (moduli paralleli e comunicanti); del sistema vanno rappresentati tutti gli interleaving;
  • attività interna indipendente dal triggering dell’ambiente esterno (ogni evoluzione è forzatamente sincrona con il triggering esterno).
  • strutture dati anche su domini limitati (il contenuto delle strutture deve essere codificato nello stato).
  • informazione temporale esplicita.

Automi regolari: caratteristiche

Proprietà di chiusura (rispetto all’accettazione di linguaggi).

Chiusura rispetto alle operazioni più comuni:

  • unione
  • intersezione
  • complementazione
  • concatenazione con linguaggi regolari
  • etc.

Decidilità e complesità.

Il problema della raggiungibilità di uno stato è risolubile in tempo lineare sulla taglia dell’automa (numero di nodi e archi).

Il problema del linguaggio vuoto (è possibile raggiungere uno stato finale?) è un caso particolare di raggiungibilità.

Esempio di costruzione dell’automa intersezione

L’intersezione di \langle\Sigma ,Q_1, q_{0,1}, \Delta_1 ,F_1 \rangle \mbox{ e } \langle\Sigma ,Q_2, q_{0,2}, \Delta_2 ,F_2 \rangle è l’automa

\langle\Sigma ,Q_1 \times Q_2, (q_{0,1},q_{0,2}), \Delta ,F_1 \timesF_2\rangle con \Delta = \{ \langle (q_1,q_2), a, (q'_1,q'_2)\rangle: \langle q_1,a,q'_1\rangle \in \Delta_1 \mbox{ e }\langle q_2,a,q'_2\rangle \in \Delta_2\}

L’automa intersezione è ottenuto mettendo in parallelo i due automi e sincronizzando la loro evoluzione:

  • lo stato è dato accoppiando lo stato di entrambi (stato delle due componenti parallele);
  • una transizione sincronizza una coppia di transizioni sullo stesso simbolo;
  • uno stato finale indica il simultaneo raggiungimento di uno stato finale nelle due componenti.

Intersezione di automi

Fig.2: Esempio di intersezione di automi regolari.

Fig.2: Esempio di intersezione di automi regolari.


Automi con azioni interne

Automi con \tau-transizioni per esprimere operazioni non controllabili.

Automi sull’alfabeto \Sigma \cup \{\tau\}

L’uso di transizioni interne etichettate da \tau permette di desincronizzare le azioni dell’automa rispetto all’input esterno.

Una parola a_0\ldots a_n \in \Sigma^* è accettata dall’automa se esiste un cammino dell’LTS dallo stato iniziale

q_0 \stackrel {b_0} {\rightarrow}q_1 \stackrel{b_1}{\rightarrow} \ldots\stackrel{b_{k}}{\rightarrow} q_{k+1} \mbox{ con } q_{k+1}\in F. e b_0\ldots b_k = (\tau)^{s_0}a_0 (\tau)^{s_1}a_1 \ldots a_n (\tau)^{s_n} \mbox{ con } s_i \geq 0.

In alcuni contesti gli automi con azioni interne permetto maggiore naturalezza espressiva:
È possibile desincronizzare l’azione interna dall’ambiente esterno.

Automi con azioni interne (segue)

Fig.3: Automa per il contatore con il registro di scorrimento. Le azioni di scorrimento sono interne. Incrementi e decrementi sono controllati dall’esterno.

Fig.3: Automa per il contatore con il registro di scorrimento. Le azioni di scorrimento sono interne. Incrementi e decrementi sono controllati dall'esterno.


Esempio chiusura per l’unione

L’azione interna permette di costruire facilmente l’automa per l’unione di due automi A_1, A_2 :

Con una azione interna, si sceglie non-deterministicamente di proseguire come A_1 \mbox{ oppure } A_2.

L’operazione di unione può essere utile per lo sviluppo incrementale di funzionalità (non interagenti) di una specifica.

Fig.4: Idea per l’unione di due automi.

Fig.4: Idea per l'unione di due automi.


Esempio: chiusura per concatenazione

L’azione interna permette di costruire facilmente l’automa per la concatenazione di due automi A_1, A_2 :

Con una azione interna, si collega ogni stato finale di A_1 con lo stato iniziale di A_2.

L’operazione di concatenazione è utile per comporre sequenzialmente due blocchi di specifica.

Fig.5: Idea per la concatenazione di due automi.

Fig.5: Idea per la concatenazione di due automi.


Espressività degli Automi con azioni interne

La possibilità di esprimere azioni interne non controllabili non aumenta il potere espressivo degli automi, aumenta soltanto la naturalezza espressiva.

Automa A=\langle\Sigma ,Q, q_{0}, \Delta ,F \rangle sull’alfabeto \Sigma \cup \{\tau\}

Costruzione di un automa A’ equivalente ad A senza azioni interne \tau.

Sia per q\in Q,\ \tau-R(q) = \{q_k\in Q: q_1<br />
\stackrel{\tau}{\longrightarrow} q_2 \stackrel{\tau}{\longrightarrow}\ldots<br />
\stackrel{\tau}{\longrightarrow}q_k, q_1=q, k\geq 1\}

Automa A'=\langle\Sigma ,Q, q_{0}, \Delta' ,F' \rangle sull’alfabeto \Sigma

  • \Delta' = \{(q,a,q') : q''\in \tau-R(q), a\in \Sigma, (q'',a,q')\in \Delta\}
  • Se \tau-R(q_0) \cap F \neq \emptyset \mbox{ allora } F'=F\cup\{q_0\} \mbox{ altrimenti } F'=F

Eliminazione transizioni interne

Fig.6: Esempio di rimozione delle transizioni interne: passo 1.

Fig.6: Esempio di rimozione delle transizioni interne: passo 1.


Eliminazione transizioni interne (segue)

Fig.7: Esempio di rimozione delle transizioni interne: passo 2 rimozione degli stati non raggiungibili.

Fig.7: Esempio di rimozione delle transizioni interne: passo 2 rimozione degli stati non raggiungibili.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion