¿Cuáles son las principales diferencias entre nfa y dfa?


Respuesta 1:

La diferencia entre NFA y DFA es que:

  • En un DFA es necesario que los autómatas pasen a un estado para cada terminal, mientras que en NFA no es necesario ir a un estado para cada terminal.

NFA-fig: 1

DFA-fig: 2

En este ejemplo, en la figura 1, como puede ver, es un NFA, por lo tanto, el estado q1 no tiene ningún estado para el terminal a o c y q2 no tiene ningún estado al que ir para el símbolo a, b o c. Si vemos fig: 2, que es un dfa, por lo que cada estado tiene un estado de transición para cada terminal, aquí en este caso es 0 y 1.

  • NFA puede ser con o sin movimientos nulos, ya que DFA es completamente sin movimientos nulos. Puede existir más de una transición de estado en NFA, mientras que solo existe una transición de estado en DFA.

Como es un DFA, solo se produce una transición de estado para 0 y 1.

Donde como,

Si vemos este NFA, q0 puede ir a q1 en 0 o puede permanecer en q0.

  • Podemos convertir NFA a DFA y viceversa.

Si te gusta la respuesta, ¡vota por favor! :)