Costruzione dei sottoinsiemi

Nella teoria dei linguaggi formali, la costruzione dei sottoinsiemi o costruzione per 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

Dato un automa a stati finiti non deterministico

${\displaystyle NFA=\left\{Q_{N},\Sigma ,\delta _{N},q_{0},F_{N}\right\}}$,

è possibile determinare un automa a stati finiti deterministico equivalente

${\displaystyle DFA=\left\{Q_{D},\Sigma ,\delta _{D},\left\{q_{0}\right\},F_{D}\right\}}$,

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

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

l'insieme degli stati finali

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

mentre la nuova funzione di transizione si calcola come:

${\displaystyle \delta _{D}\left(s,a\right)=\bigcup _{p\in s}\delta _{N}\left(p,a\right),\forall s\in Q_{D}}$

dove la funzione ${\displaystyle {\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

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

Lazy evaluation

È 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: ${\displaystyle \left\{q_{0}\right\}}$ è uno stato accessibile.
Ipotesi induttiva: ${\displaystyle s}$ stato accessibile.
Passo induttivo: ${\displaystyle \forall a\in \Sigma }$, ${\displaystyle \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

• Automa a stati finiti
• Linguaggio regolare

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla Costruzione dei sottoinsiemi