Which simulate, NFA or DFA?

4

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 really simulate? NFA or DFA? I did not understand the practicality of simulating an NFA (probably by using ε-closures , but I understand that there is non-determinism, which I also did not see an advantage in using) , which contrarily, I could simulate DFA below with an extremely simple algorithm such as this:

#regex->a*b#tabeladetransiçãodtran={(0,'a'):1,(1,'a'):1,(1,'b'):2,(0,'b'):2}F=[2]#estado(s)deaceitaçãostr=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"

Now 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"
    
asked by anonymous 03.08.2014 / 04:13

1 answer

3

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

1) Why use non-determinism?

The main reason is that it is easier to code some things and if we can use non-determinism. A good example is regular expressions, which can be encoded directly and "modular" using NFAs. For example, consider RE (0|1)*1 . Notice how the NFA closely matches the regular expression.

DFAforthissameREisabithardertofindanddoesnothaveadirectstructuralmatchtotheoriginalregularexpression:

2) Empty transitions (ε) serve for what?

Again, the presence of empty transitions makes it easier to encode some automata. It's not fundamental (it's fairly 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 one?

The process of running DFA is much more efficient. In each iteration we only have to make a state transition rather than a transition to each reachable state.

4) Why not use a DFA every time then?

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

Because of this, if your automaton is not used often it may be more efficient to ultimately simulate direct NFA without trying to convert to DF first. On the other hand, if the automaton is reused it may often be worth paying the price of a pre-processing to convert the NFA to DFA and maybe even run a DFA minimization algorithm as well.

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

link

    
03.08.2014 / 06:43