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"