Avere epsilon-transizioni implica avere un NFA, mentre non vale necessariamente il contrario. In ogni caso, l'algoritmo per passare da un epsilon-NFA a un DFA deriva, con minime variazioni, da quello necessario per passare da un generico NFA a un DFA. Non credo abbia molto senso rimuovere le epsilon-transizioni per ottenere comunque un NFA (anche se magari in teoria è possibile).
Dato un insieme di stati S raggiungibili applicando una stringa di input alfa ad un certo stato iniziale all'interno di S, la epsilon closure di S è S union "stati raggiungibili da S tramite sequenze di epsilon-transizioni".
Il DFA finale ha come stati le psilon-closure di insiemi di stati dell'automa di partenza (è questa l'unica differenza rispetto all'algoritmo per NFA normali, dove gli stati del DFA sono semplicemente insiemi di stati del NFA) così ottenute:
1. Si inizia prendendo la epsilon-closure dello stato iniziale del NFA e la si mette in una coda; essa sarà lo stato iniziale del DFA;
2. Per ogni closure nella coda:
I. trova le epsilon-closure raggiungibili, a partire da quella estratta, applicando una singola transizione;
II. per ogni closure trovata, se non era già stata visitata:
a. aggiungila alla coda;
b. crea un nuovo stato nel DFA corrispondente alla closure e collegato al precedente mediante lo stesso tipo di transizione che collegava la closure trovata a quella estratta dalla coda;
3. Segna come stati finali del DFA tutti quegli stati raggiungibili mediante la/le stringa/stringhe con cui si raggiungevano gli stati finali dell'automa di partenza (questo è forse il passaggio più difficile, se non conosci a priori le stringhe in questione, ma fortunatamente solitamente le stringhe sono note perché l'automa viene creato in funzione di esse).