SCELTA O SOMMA

Questo operatore è dinamico e soprattutto può descrivere un sistema non deterministico. Si indica di solito con il simbolo + ai cui lati troviamo due espressioni di processo. Si parla di scelta perché se abbiamo E + F allora il sistema può eseguire le transizioni di E o quelle di F. In particolare si perde il determinismo quando queste due espressioni cominciano con la stessa azione $\alpha$ perché con lo stesso comportamento si possono seguire due strade diverse (ad esempio nel processo $\: \alpha.E + \alpha.F \:$).

Le due regole di transizione indicano quale scelta viene fatta.

$$\renewcommand {\arraystretch}{1.2} \begin{array}{c}E \stackrel{\... ...tarrow} F'\\ \hline E+F \stackrel{\alpha}{\longrightarrow} F' \end{array}$$

E'possibile definire una somma più generale con più di due operandi. Questo avviene utilizzando il simbolo di sommatoria e si definisce la regola di transizione generale:

$$\renewcommand {\arraystretch}{1.2} \begin{array}{c}E_j \stackrel... ... I} E_i \stackrel{\alpha}{\longrightarrow} E_j' \end{array} \quad (j \in I)$$

Quindi con la somma si sceglie un solo cammino tra tutti quelli possibili. Ovviamente quando $I = \emptyset$ siamo di fronte al processo inattivo.

Nel processo $\:\: N \stackrel{{def}}{{=}}\beta.0 + \alpha.\gamma.0 \:\:$ si può fare la sequenza di azioni $\alpha$ $\gamma$ oppure si esegue soltanto $\beta$ ed il processo si ferma. Se fosse $\beta = \alpha$ si troverebbe il non determinismo già all'inizio perché con la stessa azione si raggiungono due stati differenti.

Quello che abbiamo descritto è l'operatore di scelta più comunemente usato nelle algebre di processi, ma possiamo anche suddividerlo in due tipi di somma che si comportano in modo differente rispetto alle azioni interne.

Con l'operatore di scelta interna pura $\quad E \:\oplus\: F\quad$ la scelta del processo che deve proseguire avviene tramite azioni invisibili non controllabili dall'esterno:

$$\renewcommand {\arraystretch}{1.2} \begin{array}{c}\\ \hline E... ...}\\ \hline E \oplus F \stackrel{\varepsilon}{\longrightarrow} F \end{array}$$

L'operatore di scelta esterna $\quad E \:\Box\: F\quad$ ha le seguenti regole di transizione:

$$\renewcommand {\arraystretch}{1.2} \begin{array}{c}E \stackrel{\... ...line E \Box F \stackrel{\varepsilon}{\longrightarrow} E' \Box F \end{array}$$

in caso di azione interna (anche sapendo quale espressione la causa) non si viene effettuata la scelta.

Esempio Bill-Ben 3: Utilizzando gli operatori di base, possiamo descrivere l'esempio utilizzato in precedenza per gli LTS. Osservando il grafo di transizione disegnato nel paragrafo 2.1 si ottiene la seguente espressione con sequenzializzazione e somma:

$$play.\:work\:\tau.\:nil \:+\: work.\:play.\:\tau.\:nil$$

dove $nil$ è il processo inattivo che non esegue alcuna attività.