Costruzione dei sottoinsiemi

Da Wikipedia, l'enciclopedia libera.

Nella teoria dei linguaggi formali, la costruzione dei sottoinsiemi o subset construction è la tecnica di costruzione dell'automa a stati finiti deterministico equivalente ad un automa a stati finiti non deterministico.

Equivalenza tra automa deterministico e non deterministico[modifica | modifica sorgente]

Dato un automa a stati finiti non deterministico

NFA=\left\{ Q_{N},\Sigma,\delta_{N},q_{0},F_{N}\right\},

è possibile determinare un automa a stati finiti deterministico equivalente

DFA=\left\{ Q_{D},\Sigma,\delta_{D},\left\{ q_{0}\right\} ,F_{D}\right\},

tale che L\left(NFA\right)=L\left(DFA\right). L'insieme di stati diventa

Q_{D}=\mathcal{P}\left(Q_{N}\right)\Rightarrow\left|Q_{D}\right|=2^{\left|Q_{N}\right|},

l'insieme degli stati finali

F_{D}=\left\{ s\in Q_{D}|s\cap F_{N}\neq\emptyset\right\}

mentre la nuova funzione di transizione si calcola come:

\delta_{D}\left(s,a\right)=\bigcup_{p\in s}\delta_{N}\left(p,a\right),\forall s\in Q_{D}

dove la funzione \mathcal{P}\left(\cdot\right) indica l'insieme delle parti. È possibile dimostrare che l'automa deterministico così definito risulta essere equivalente all'automa non deterministico a partire dal quale è costruito. Entrambi gli automi riconoscono quindi lo stesso linguaggio.

Algoritmo di costruzione per sottoinsiemi[modifica | modifica sorgente]

L'algoritmo per la costruzione dell'automa equivalente discende direttamente dalla definizione dell'automa. La definizione della funzione di transizione \delta viene valutata per ogni elemento appartenente al dominio Q_{D}, ossia per tutti i possibili sottoinsiemi di Q_{N}.

Lazy evaluation[modifica | modifica sorgente]

È possibile che la costruzione dell'automa equivalente tramite l'algoritmo di costruzione per sottoinsiemi possa portare alla definizione di stati non accessibili, la cui presenza risulta ridondante e che porta ad un eccesso di calcolo che può essere ridotto. La lazy evaluation permette di evitare i calcoli necessari a definire gli stati che non sono raggiungibili dall'automa. Tale algoritmo viene definito induttivamente non prendendo in considerazione tutti gli elementi dell'insieme della parti.
Base: \left\{q_{0}\right\} è uno stato accessibile.
Ipotesi induttiva: s stato accessibile.
Passo induttivo: \forall a\in\Sigma, \delta\left(s,a\right) accessibile.
La lazy evaluation porta alla determinazione di tutti e soli gli stati accessibili. La definizione della funzione di transizione può essere quindi eseguita solo su tali stati.

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]