No, por los motivos expuestos a continuación por Abhishek y Greetta: ambos tienen el mismo poder computacional y definen la misma clase de lenguajes regulares.
Los DFA están restringidos por la regla de que cada estado debe tener exactamente una transición [matemática] \ delta [/ matemática] para cada carácter [matemático] \ en [/ matemático] [matemático] \ Sigma [/ matemático]. Pero un NFA puede tener cero, una o más transiciones de un solo estado para un solo carácter. Es por eso que es fácil suponer que un NFA tiene más poder computacional que un DFA. Pero si lo piensas bien, la [matemática] \ delta [/ matemática] de la NFA se define por el conjunto de potencia de Q (recuerda que la [matemática] \ delta [/ matemática] de la DFA se define solo por Q). Por lo tanto, podemos ver que cualquier NFA se puede convertir en un DFA, solo podría tomar más estados para representar.
- ¿Cuál es la diferencia entre las diferentes bases de datos NoSQL?
- ¿Se puede obtener toda la información a través de preguntas sí / no?
- Si podemos navegar por los contenidos de Internet en el sandbox (como el navegador Chrome), ¿por qué necesitamos establecer otros valores?
- ¿Es un NFA más poderoso que un DFA? Por favor justifícalo.
- Cómo instalar dos sistemas operativos en la misma máquina
Este diagrama de estado es un NFA porque en [math] q_2 [/ math], en la entrada 1, hay dos opciones para [math] \ delta [/ math]: quedarse o pasar al estado [math] q_3 [/ math] . Además, en [math] q_3 [/ math], no hay [math] \ delta [/ math] para la entrada 0. En un DFA equivalente, debería haber una distinción entre estos dos [math] \ delta [/ math] ‘s, y un estado para representar [math] \ delta [/ math] en 0 de [math] q_3 [/ math], que requiere más estados. (Crédito de diseño FSM: Diseñador de máquinas de estado finito)
Estudiamos NFA porque nos permiten modelar FSM de manera más simple en los casos anteriores. Aquí hay una manera que podría ayudarlo a pensar sobre el determinismo frente al no determinismo, desde la introducción de Sipser hasta la teoría de la computación :
Ambos cálculos se representan como árboles de posibilidades. Cuando el cálculo no determinista tiene múltiples opciones en cada nodo, la versión determinista tiene una única opción para cada uno.
