Conversione automa NFA a DFA

[RinOkumura]

Ciao a tutti!
Sto cercando di imparare a convertire un automa NFA in DFA seguendo il metodo che utilizza il libro consigliato dal mio professore (Introduzione alla teoria della computazione di Michael Sipser).
Con il metodo trovato sul libro in teoria non avrei problemi, ma cercando online ho notato che il metodo usato da altre persone è completamente diverso e porta ad un risultato diverso.
In particolare, il problema riguarda il numero di stati che avrà l'automa DFA finale.
Sul libro viene detto che il DFA avrà un numero di stati pari all'insieme delle parti dell'insieme di stati dell'automa NFA (quindi ad esempio un automa con gli stati:
Q = {1, 2, 3}
avrà i seguenti stati:
Q': { insieme vuoto, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
ho notato che questa regola non viene praticamente mai seguita da altre persone che scrivono online...
qualcuno potrebbe farmi chiarezza?

[ludovica_97]

Ciao a tutti!
Sto cercando di imparare a convertire un automa NFA in DFA seguendo il metodo che utilizza il libro consigliato dal mio professore (Introduzione alla teoria della computazione di Michael Sipser).
Con il metodo trovato sul libro in teoria non avrei problemi, ma cercando online ho notato che il metodo usato da altre persone è completamente diverso e porta ad un risultato diverso.
In particolare, il problema riguarda il numero di stati che avrà l'automa DFA finale.
Sul libro viene detto che il DFA avrà un numero di stati pari all'insieme delle parti dell'insieme di stati dell'automa NFA (quindi ad esempio un automa con gli stati:
Q = {1, 2, 3}
avrà i seguenti stati:
Q': { insieme vuoto, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
ho notato che questa regola non viene praticamente mai seguita da altre persone che scrivono online...
qualcuno potrebbe farmi chiarezza?

Quando converti un NFA in un DFA, il DFA ottenuto puo' avere al massimo $2^n$ stati se l' NFA corrispondente ha n stati, che sarebbe un numero di stati pari all'insieme delle parti dell'insieme di stati dell'automa NFA, come dici tu. Il fatto e' che un DFA convertito a partire da un NFA non e' detto abbia $2^n$ stati, quello e' il massimo numero di stati che puo' avere ma non per tutti e' cosi.