Bem, nós sabemos que teoricamente e praticamente, toda NFA pode ser convertida para uma DFA que aceite a mesma linguagem. Minha dúvida é a seguinte:
Qual eu devo realmente simular? NFA ou DFA? Eu não entendi a praticidade de simular uma NFA (provavelmente pelo uso das ε-closures
, mas eu entendo que há o não determinismo, que também não vi uma vantagem no uso) , que contrariamente, eu poderia simular a DFA abaixo com um algoritmo extremamente simples tal como esse:
# 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"
Já a nossa simulação da NFA:
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"