Home

Federica EU

1/13

Adriano Peron » 5.FSM: Non-determinismo e succintezza

Ruolo del non-determinismo

Il non determinismo viene considerato nella specifica dei sistemi essenzialmente per:

Astrazione:
può essere utilizzato come un mezzo per astrarre dettagli del sistema da specificare ritenuti non rilevanti al livello di dettaglio considerato.

Ad esempio:

astrazione rispetto alla scelta tra alternative diverse quando il livello di dettaglio porta a trascurare i criteri per operare la scelta effettiva tra le varie possibilità;
astrazione dall’effettivo contenuto di alcune strutture dati;
etc.

Succintezza:
il non-determinismo se permesso nelle macchine a stati finiti consente di ottenere specifiche più compatte.

Il non-determinismo non influenza la capacità espressiva delle FSM.

Non-determinismo e astrazione

Esempio di astrazione:
Inserimento/estrazione di richieste in due code gestite con liste a scorrimento.

Se è possibile inserire in entrambe le code, non si stabilisce il criterio di preferenza
- (ad es. alternanza, fattore di riempimento etc.).
Se è possibile estrarre da entrambe le code, non si stabilisce il criterio di preferenza
- (ad es. alternanza, fattore di riempimento etc).

L’astrazione è opportuna se non è di interesse lo studio delle prestazioni della struttura di memorizzazione e ci si concentra solo sulla funzionalità dell’immissione e dell’estrazione.

Fig.1 Inserimento, estrazione da doppia lista di scorrimento.

Non-determinismo e astrazione (segue)

Esempio di astrazione:
Analisi del flusso di controllo.

Il flusso del controllo dipende dal contenuto della variabile x.
Si astrae dal contenuto della variabile x scegliendo non-deterministicamente quale ramo della scelta percorrere.

L’astrazione è opportuna se non è di interesse valutare il flusso del controllo in dipendenza dal contenuto della variabile x.

(Ad esempio, se interessa vedere quali sono gli stati di controllo raggiungibili nell’ipotesi che sia valori maggiori sia minori di 5 possano essere associati a x).

Fig.2 Esempio di astrazione.

Non-determinismo e succintezza

Gli automi non-deterministici sono più succinti degli automi deterministici.

Per poter affermare che la classe degli automi non-deterministici è più succinta
di quella degli automi deterministici, occorre verificare che:

è possibile trovare per ogni automa deterministico A un automa non-deterministico equivalente A’ di dimensione polinomiale nella dimensione di A;
- (ovvio, poiché un automa deterministico è un caso speciale di automa non-deterministico);
è possibile trovare un automa non-deterministico B tale per cui ogni automa deterministico B’ equivalente a B è di dimensione esponenziale rispetto alla dimensione di B.

(Esempio: nelle diapositive successive)

Osservazione: il concetto di succintezza introdotto ha carattere quantitativo (la differenza di succintezza implica una differenza di taglia esponenziale nel caso peggiore).

Succintezza: esempio

Linguaggio L con parole sull’alfabeto $\Sigma=H \cup \{\sharp \} \mbox{ con }\sharp \not\in H$ aventi la forma

$v_1\ldots v_k\sharp w_1\ldots w_h \mbox{ con } v_1\ldots v_k \in H^{\star}\mbox{ e } w_1\ldots w_h\in H^{\star}$ parole tali che qualche simbolo che occorre in
$\alpha=v_1\ldots v_k$ occorre anche in $\beta=w_1\ldots w_h$ .

Automa deterministico:

occorre memorizzare nello stato l’insieme dei simboli che occorrono in $\alpha$ ;
l’insieme dei simboli deve contenere un sottoinsieme di stati in corrispondenza biunivoca con $2^H$ (insieme delle parti di H).

Esempio succintezza

Definizione automa deterministico

$A =\langle\Sigma,Q, q_{0}, \Delta ,F \rangle, \mbox{ dove }$

$\begin{array}{lll} Q & = & 2^{{\Sigma} \cup \{ok\}};\\ Q_{0} & = &\emptyset;\\ \Delta & = & \{ (q,a,q\cup\{a\}) : q\in 2^{H}, a \in \Sigma\} \cup \\ & & \{ (q,a,q) : q\in 2^{H}, \sharp \in q, a \in H, a \not\in q\} \cup\\ & & \{ (q,a,ok) : q\in 2^{H}, \sharp \in q, a \in H, a\in q\} \cup\\ & & \{ (ok,a,ok) : a \in H\};\\ F & = & \{q \in Q : ok \in q\}. \end{array}$

Intuitivamente (sarebbe necessaria una prova formale), non è possibile costruire un automa deterministico con un numero di stati di cardinalità inferiore all’insieme delle parti $2^{\Sigma}$ .

La taglia esponenziale dipende dal problema e non dalla particolare soluzione adottata.

Esempio: Automa deterministico

Fig.3 Automa deterministico per esempio succintezza.

Succintezza: automa non-deterministico

Idea: il non-determinismo è usato per ‘ipotizzare’ il simbolo che verrà ripetuto nella prima e seconda parte della stringa prima dell’inizio della computazione:

ipotesi iniziale sul simbolo che verrà ripetuto (per tutti i simboli);
verifica che il simbolo ipotizzato realmente occorra prima di $\sharp$ ;
verifica che il simbolo venga realmente replicato.

Se un simbolo viene replicato esiste una ipotesi iniziale corretta che soddisfa i controlli (ne basta una).

La costruzione ha dimensione polinomiale sull’alfabeto ed è dunque più succinta della costruzione deterministica.

Esempio: Automa non-deterministico

Fig. 4 Automa non-deterministico per esempio succintezza.

Esempio succintezza

Definizione automa non-deterministico

$A =\langle\Sigma,Q, q_{0}, \Delta ,F \rangle, \mbox{ dove }$

$\begin{array}{lll} Q & = & \{q\in 2^(\Sigma \cup \{ck,ok\}) : q\cap H \mbox{ \`e un singoletto}\};\\ Q_{0} & = & \emptyset;\\ \Delta & = & \{ (\emptyset ,a,\{a,ck\}),(\emptyset ,a,\{b\}): b \in H\} \cup \\& & \{ (\{a\},a,\{a,ck\}) : a\in H\} \cup \\ & & \{ (\{a\},b,\{a\}) : b\in H, b\neq a\} \cup \\ & & \{ (q,\sharp,q\cup\{\sharp\}) : \sharp \not\in q\} \cup \\ & & \{ (q,a,q\cup\{ok\}) : a \in q\} \cup \\ & & \{ (q,a,q) : a \not\in q, a\in H\}\\ F & = & \{q \in Q : ok\in q\}. \end{array}$

Il numero degli stati è lineare nella dimensione dell’alfabeto.

Non determinismo e capacità espressiva

Gli automi regolari sono determinizzabili: per ogni automa non-deterministico è possibile trovare un automa deterministico che accetta lo stesso linguaggio.

(Si noti il criterio di equivalenza, la bisimulazione sarebbe un criterio troppo forte perché distingue rispetto alle scelte deterministiche).

Sia l’automa regolare A (non-deterministico)
$\langle\Sigma ,Q, q_{0}, \Delta ,F \rangle$

un automa deterministico equivalente è

$\langle\Sigma ,2^Q, \{q_{0}\}, \Delta' ,F' \rangle$

$\Delta' = \{ \langle s,a,s'\rangle :\ s \in 2^Q,\ s' = \{ q' : \langle q,a,q'\rangle\in \Delta,\ q\in s\} \}$

$F' = \{ s :\ s \in 2^Q,\ s \cap F \neq \emptyset\}$

Determinizzazione: Intuizioni

Idea: L’automa determinizzato simula l’esecuzione simultanea di tutti comportamenti legati a scelte non-deterministiche alternative.

Stato: Insieme di stati raggiungibili mediante transizioni che rappresentano una scelta non deterministica;

Transizione: Simultanea esecuzione di transizioni che rappresentano una scelta non deterministica;

Stato finale: L’insieme degli stati raggiunti simultaneamente deve contenere almeno uno stato finale dell’automa non-deterministico
(nel caso non deterministico per l’accettazione basta che esista un comportamento di accettazione).

Taglia dell’automa determinizzato:
Può coinvolgere un numero esponenziale di stati e transizioni nella taglia dell’automa non-deterministico.