1. DFA: DFA se refiere a un autómata finito determinista. Se dice que un autómata finito (FA) es determinista si corresponde a un símbolo de entrada, hay un solo estado resultante, es decir, solo hay una transición. Un autómata finito determinista es un conjunto de cinco tuplas representadas como,
Donde,
Q: Un conjunto finito no vacío de estados en el control finito (qo, q1, q2, …).
Σ: Un conjunto finito no vacío de símbolos de entrada.
δ: Es una función de transición que toma dos argumentos, un estado y un símbolo de entrada, devuelve un solo estado.
qo: Es el estado inicial, uno de los estados en Q.
F: Es un conjunto no vacío de estados finales/estados de aceptación del conjunto que pertenece a Q.
2. NFA:
NFA se refiere a un autómata finito no determinista. Se dice que un autómata finito (FA) no es determinista si hay más de una transición posible desde un estado en el mismo símbolo de entrada.
Un autómata finito no determinista también es un conjunto de cinco tuplas y se representa como,
Donde,
Q: Un conjunto de estados finitos no vacíos.
Σ: Un conjunto de símbolos de entrada finitos no vacíos.
δ: es una función de transición que toma un estado de Q y un símbolo de entrada y devuelve un subconjunto de Q.
qo: estado inicial de NFA y miembro de Q.
F: un conjunto no vacío de estados finales y miembro de Q .
Requisito previo: autómatas finitos
Diferencia entre DFA y NFA:
|
DFA |
NFA |
|---|---|
| DFA significa Deterministic Finite Automata. | NFA significa autómatas finitos no deterministas. |
| Para cada representación simbólica del alfabeto, solo hay una transición de estado en DFA. | No es necesario especificar cómo reacciona el NFA según algún símbolo. |
| DFA no puede utilizar la transición de string vacía. | NFA puede usar la transición de string vacía. |
| DFA puede entenderse como una máquina. | NFA puede entenderse como múltiples pequeñas máquinas computando al mismo tiempo. |
| En DFA, el siguiente estado posible se establece claramente. | En NFA, cada par de estado y símbolo de entrada puede tener muchos estados siguientes posibles. |
| DFA es más difícil de construir. | NFA es más fácil de construir. |
| DFA rechaza la string en caso de que termine en un estado diferente del estado de aceptación. | NFA rechaza la cuerda en caso de que todas las ramas mueran o rechacen la cuerda. |
| El tiempo necesario para ejecutar una string de entrada es menor. | El tiempo necesario para ejecutar una string de entrada es mayor. |
| Todos los DFA son NFA. | No todos los NFA son DFA. |
| DFA requiere más espacio. | NFA requiere menos espacio que DFA. |
| Puede ser necesario un estado muerto. | No se requiere estado muerto. |
| δ: QxΣ -> Q, es decir, el siguiente estado posible pertenece a Q. | δ: QxΣ -> 2^Q, es decir, el siguiente estado posible pertenece al conjunto potencia de Q. |
| El retroceso está permitido en DFA. | El retroceso no siempre es posible en NFA. |
| La conversión de expresiones regulares a DFA es difícil. | La conversión de expresiones regulares a NFA es más simple en comparación con DFA. |