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
[modifica | modifica wikitesto]Dato un automa a stati finiti non deterministico
- ,
è possibile determinare un automa a stati finiti deterministico equivalente
- ,
tale che . L'insieme di stati diventa
- ,
l'insieme degli stati finali
mentre la nuova funzione di transizione si calcola come:
dove la funzione 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 wikitesto]L'algoritmo per la costruzione dell'automa equivalente discende direttamente dalla definizione dell'automa. La definizione della funzione di transizione viene valutata per ogni elemento appartenente al dominio , ossia per tutti i possibili sottoinsiemi di .
Lazy evaluation
[modifica | modifica wikitesto]È 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: è uno stato accessibile.
Ipotesi induttiva: stato accessibile.
Passo induttivo: , 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 wikitesto]Altri progetti
[modifica | modifica wikitesto]- Wikimedia Commons contiene immagini o altri file sulla Costruzione dei sottoinsiemi