What simulate, NFA or DFA?

Question

Well, we know that theoretically and practically, every NFA can be converted to a DFA that accepts the same language. My question is this::

Which one should I actually simulate? NFA or DFA? I don’t understand the practicality of simulating an NFA (probably by the use of ε-closures, but I understand that there is nondeterminism, which also did not see an advantage in using) , that conversely, I could simulate the DFA below with an extremely simple algorithm such as this:

# regex -> a*b

# tabela de transição
dtran = {
    (0, 'a'): 1, (1, 'a'): 1, (1, 'b'): 2, (0, 'b'): 2
}

F = [2] # estado(s) de aceitação

str = raw_input(">>> ")
s = 0 # estado atual
for c in str:
    try:
        s = dtran[s,c] # retorna o próximo estado possível para [estado atual, char]
    except KeyError:
        break # encerramos o loop, alguma transição não existente na tabela foi atingida

if s in F: # checamos se o estado final está presente nos estados aceitáveis
    print "Aceita"
else:
    print "Rejeitada"

Already our NFA simulation:

F = [4]
str = raw_input(">>> ")
s = 0
s = eclosure(s)

for c in str: 
    s = eclosure(mova(s, c))

if s in F:
    print "Aceita"
else 
    print "Rejeitada"

Answer 1

I think the most important question to answer is the usefulness of Nfas. The rest comes easy later.

1) Why use nondeterminism?

The main reason is that it is easier to encode some things if we can use nondeterminism. A good example are regular expressions, which can be encoded directly and "modular" using Nfas. For example, consider RE (0|1)*1. Notice how NFA matches well directly with regular expression.

The DFA for this same RE is a little more difficult to find and does not have a direct structural correspondence with the original regular expression:

2) Empty transitions (ε) serve what?

Again, the presence of empty transitions makes it easier to encode some automata. It is not something fundamental (it is quite easy to modify an NFA to eliminate empty transitions) but it also costs nothing and is very useful.

3) Why use a deterministic automaton instead of a non-deterministic automaton?

The DFA execution process is much more efficient. In each iteration we just have to make a state transition instead of a transition to each reachable state.

4) Why not use a DFA every time then?

Converting an NFA into a DFA can be quite costly, especially in terms of memory. In the worst case, there may even be an exponential growth in the number of states, since the DFA states correspond to subsets of states in the NFA.

Because of this, if your automaton is not used often it can be more efficient in the end simulating direct NFA without trying to convert to DF first. On the other hand, if the automaton is reused many times it may be worth paying the price of a preprocessing to convert NFA to DFA and maybe even run a DFA minimizing algorithm as well.

---

This page in English has several examples of what I said, including a concrete example where DFA is exponentially larger than NFA.

http://www.cs.wcupa.edu/rkline/fcs/nfas.html