Indietro

ⓘ Costruzione dei sottoinsiemi




                                     

ⓘ Costruzione dei sottoinsiemi

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

                                     

1. Equivalenza tra automa deterministico e non deterministico

Dato un automa a stati finiti non deterministico

N F A = { Q N, Σ, δ N, q 0, F N } {\displaystyle NFA=\left\{Q_{N},\Sigma,\delta _{N},q_{0},F_{N}\right\}},

è possibile determinare un automa a stati finiti deterministico equivalente

D F A = { Q D, Σ, δ D, { q 0 }, F D } {\displaystyle DFA=\left\{Q_{D},\Sigma,\delta _{D},\left\{q_{0}\right\},F_{D}\right\}},

tale che L N F A = L D F A {\displaystyle L\leftNFA\right=L\leftDFA\right}. Linsieme di stati diventa

Q D = P Q N ⇒ | Q D | = 2 | Q N | {\displaystyle Q_{D}={\mathcal {P}}\leftQ_{N}\right\Rightarrow \left|Q_{D}\right|=2^{\left|Q_{N}\right|}},

linsieme degli stati finali

F D = { s ∈ Q D | s ∩ F N ≠ ∅ } {\displaystyle F_{D}=\left\{s\in Q_{D}|s\cap F_{N}\neq \emptyset \right\}}

mentre la nuova funzione di transizione si calcola come:

δ D s, a = ⋃ p ∈ s δ N p, a, ∀ s ∈ Q D {\displaystyle \delta _{D}\lefts,a\right=\bigcup _{p\in s}\delta _{N}\leftp,a\right,\forall s\in Q_{D}}

dove la funzione P ⋅ {\displaystyle {\mathcal {P}}\left\cdot \right} indica linsieme delle parti. È possibile dimostrare che lautoma deterministico così definito risulta essere equivalente allautoma non deterministico a partire dal quale è costruito. Entrambi gli automi riconoscono quindi lo stesso linguaggio.

                                     

2. Algoritmo di costruzione per sottoinsiemi

Lalgoritmo per la costruzione dellautoma equivalente discende direttamente dalla definizione dellautoma. La definizione della funzione di transizione δ {\displaystyle \delta } viene valutata per ogni elemento appartenente al dominio Q D {\displaystyle Q_{D}}, ossia per tutti i possibili sottoinsiemi di Q N {\displaystyle Q_{N}}.

                                     

3. Lazy evaluation

È possibile che la costruzione dellautoma equivalente tramite lalgoritmo 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 dallautoma. Tale algoritmo viene definito induttivamente non prendendo in considerazione tutti gli elementi dellinsieme della parti. Base: { q 0 } {\displaystyle \left\{q_{0}\right\}} è uno stato accessibile. Ipotesi induttiva: s {\displaystyle s} stato accessibile. Passo induttivo: ∀ a ∈ Σ {\displaystyle \forall a\in \Sigma }, δ s, a {\displaystyle \delta \lefts,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.