Ejemplos de diagramas NFA.
Una herramienta, cuatro solicitudes. Todos los diagramas de abajo son resultados reales.
Qué es un diagrama NFA.
Un diagrama NFA es un diagrama de estados de un autómata finito no determinista. Los círculos son estados, las flechas son transiciones, una flecha entrante marca el inicio y un círculo doble marca un estado de aceptación.
A diferencia de un DFA, un NFA puede tomar más de una transición con el mismo símbolo de entrada y puede usar transiciones epsilon que no consumen entrada. Una cadena se acepta cuando al menos uno de los caminos posibles termina en un estado de aceptación.
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
Quién usa los diagramas NFA.
Ejercicios de lenguajes regulares que muestran cómo una máquina reconoce un sufijo, prefijo o subcadena.
Construcciones pequeñas de epsilon-NFA que hacen visible la unión de una expresión regular en los apuntes de clase.
Prefijos alternativos de tokens dibujados como ramas antes de convertirlos en una implementación.
Cómo crear un diagrama NFA en tres pasos.
Descríbelo
Basta con un párrafo para empezar.
Mira el diagrama
Lo dibuja el motor adecuado.
Indica qué cambiar
Cada cambio guarda una versión.
Preguntas habituales
¿Qué es un NFA?
Un autómata finito no determinista es una máquina de estados finitos que puede tener varias transiciones posibles para un símbolo de entrada. Acepta cuando al menos un camino de la máquina termina en un estado de aceptación.
¿En qué se diferencia un NFA de un DFA?
Un DFA tiene un único estado siguiente para cada estado y símbolo de entrada. Un NFA puede ramificarse hacia varios estados e incluir transiciones epsilon, pero los NFA y los DFA reconocen la misma clase de lenguajes regulares.
¿Qué es una transición epsilon?
Una transición epsilon cambia de estado sin consumir un carácter de la entrada. Se usa habitualmente para unir o dividir ramas al construir un NFA a partir de una expresión regular.
¿Cómo se muestran los estados de aceptación?
Un estado de aceptación, o estado final, se muestra con un círculo doble. La máquina acepta solo si algún camino termina en ese estado después de leer toda la entrada.
¿Puedo crear un NFA a partir de una expresión regular?
Sí. Describe la expresión y su alfabeto, y luego indica cualquier agrupación o alternancia que quieras hacer explícita en el diagrama de estados.
Otros diagramas para el mismo trabajo.
Dibuja tu primer NFA ahora.
Cuenta gratuita, sin tarjeta. Describe el lenguaje y visualiza el diagrama de estados en menos de un minuto.
Abrir el editor