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

$NFA=\{Q_N,\mathrm{\Sigma },{\delta }_N,q_0,F_N\}$,

è possibile determinare un automa a stati finiti deterministico equivalente

$DFA=\{Q_D,\mathrm{\Sigma },{\delta }_D,\left\{q_0\right\},F_D\}$,

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

$Q_D=𝒫\left(Q_N\right)\Rightarrow \left|Q_D\right|=2^{\left|Q_N\right|}$,

l'insieme degli stati finali

$F_D=\{s\in Q_D|s\cap F_N\ne \mathrm{\varnothing }\}$

mentre la nuova funzione di transizione si calcola come:

${\delta }_D(s,a)=\bigcup _{p\in s}{\delta }_N(p,a),\mathrm{\forall }s\in Q_D$

dove la funzione $𝒫(\cdot )$ 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 $\delta$ viene valutata per ogni elemento appartenente al dominio $Q_D$, ossia per tutti i possibili sottoinsiemi di $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: $\left\{q_0\right\}$ è uno stato accessibile.
Ipotesi induttiva: $s$ stato accessibile.
Passo induttivo: $\mathrm{\forall }a\in \mathrm{\Sigma }$, $\delta (s,a)$ 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