Costruzione dei sottoinsiemi

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 deterministicoModifica

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 sottoinsiemiModifica

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 evaluationModifica

È 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 correlateModifica

Altri progettiModifica