4

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:

inserir a descrição da imagem aqui

# 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:

inserir a descrição da imagem aqui

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"

1 Resposta 1

3

Acho que a pergunta mais importante a responder é a utilidade dos NFAs. O resto vem fácil depois.

1) Pra que usar o não determinismo?

A principal razão é que é mais fácil codificar algumas coisasse pudermos usar o não determinismo. Um bom exemplo são as expressões regulares, que podem ser codificadas de forma direta e "modular" usando NFAs. Por exemplo, considere a RE (0|1)*1. Repare como o NFA corresponde bem diretamente com a expressão regular.

NFA

Já o DFA para essa mesma RE é um pouco mais difícil de achar e não tem uma correspondência estrutural direta com a expressão regular original:

inserir a descrição da imagem aqui

2) Transições vazias (ε) servem pra que?

Novamente, a presença de transições vazias deixa mais fácil codificar alguns autômatos. Não é algo fundamental (é bastante fácil modificar um NFA para eliminar as transições vazias) mas também não custa nada e é bem útil.

3) Para que usar um autômato determinístico ao invés de um não determinístico?

O processo de execução do DFA é bem mais eficiente. Em cada iteração só temos que fazer uma transição de estado em vez de uma transição para cada estado alcançável.

4) Por que não usar um DFA toda vez então?

Converter um NFA em um DFA pode ser bastante custoso, especialmente em termos de memória. No pior caso pode até ocorrer um crescimento exponencial no número de estados, já que os estados do DFA correspondem a subconjuntos de estados no NFA.

Por causa disso, se o seu autômato não for usado muitas vezes pode ser mais eficiente no final das contas simular o NFA direto sem tentar converter para DF primeiro. Por outro lado, se o autômato for reutilizado muitas vezes pode ser que valha a pena pagar o preço de um pré-processamento para converter o NFA para DFA e talvez até rodar um algoritmo de minimização de DFA também.


Essa página em inglês tem vários exemplos do que eu falei, incluindo um exemplo concreto onde o DFA é exponencialmente maior que o NFA.

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .