Scribd
Cargar
26 vistas3 páginas

NFA: Algoritmos No Deterministas

Este documento describe la diferencia entre autómatas finitos deterministas (DFA) y no deterministas (NFA). Los NFA permiten múltiples transiciones entre estados con un solo símbolo de entrada, lo que da como resultado varias posibles soluciones, mientras que los DFA solo permiten una transición por estado y símbolo. Aunque un DFA y un NFA pueden reconocer el mismo lenguaje, un NFA generalmente requiere menos estados debido a su no determinismo. El documento incluye ejemplos de DFA y NFA y explica cómo pasar de

Cargado por

Luis Carlos Bacasehua
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
26 vistas3 páginas

NFA: Algoritmos No Deterministas

Este documento describe la diferencia entre autómatas finitos deterministas (DFA) y no deterministas (NFA). Los NFA permiten múltiples transiciones entre estados con un solo símbolo de entrada, lo que da como resultado varias posibles soluciones, mientras que los DFA solo permiten una transición por estado y símbolo. Aunque un DFA y un NFA pueden reconocer el mismo lenguaje, un NFA generalmente requiere menos estados debido a su no determinismo. El documento incluye ejemplos de DFA y NFA y explica cómo pasar de

Cargado por

Luis Carlos Bacasehua
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

NFA y Expresiones regulares

Luis Carlos BACASEHUA M ORALES


7 de noviembre de 2019

Generación: 2014
Clave única: 235470
Email: [Link]@[Link]
Clase: Algoritmos y su complejidad
Instructor: Dr. Juan Carlos Cuevas Tello

Resumen
El no determinismo es un concepto que ha tenido grandes impactos en la teorı́a
de la computación. En ciencias de la computación, un algoritmo no determinista es
un algoritmo que con la misma entrada ofrece muchos posibles resultados, y por
tanto no ofrece una solución única. No se puede saber de antemano cuál será el
resultado de la ejecución de un algoritmo no determinista.

1. Contenido
La gran diferencia entre un DFA (autómata finito determinista) y un NFA (autóma-
ta finito no determinista) es que para cada estado de un DFA existe solamente una
transición a otro estado con un único sı́mbolo del alfabeto. En los NFA esto no es ası́,
existen transiciones entre estados con más de un sólo sı́mbolo del alfabeto, esto nos
lleva a tener muchas posibles soluciones[1].
Un NFA funciona como un árbol que explora todas las posibles soluciones, si en algu-
na transición se queda sin más opciones explora otra de sus posibles ramas hasta que
estas se agoten o se termine en un estado de aceptación lo cual harı́a que el autómata
aceptara la cadena.

En la figura 1 vemos la representación de un NFA. Si la cadena de entrada para este


autómata fuera: 010110, el autómata harı́a la transición entre estados que se muestra en
la figura 2. Al final la cadena es aceptada porque termina en el estado q4 que es parte
del conjunto de estados de aceptación del autómata.

1.1. Comparación entre un DFA y un NFA


Los autómatas mostrados en la figura 3 y figura 4 reconocen el mismo lenguaje, sin
embargo uno es determinista y el otro no determinista. Aunque uno tiene el doble de
estados que el otro, siguen resolviendo lo mismo y reconociendo el mismo lenguaje.

1
Figura 1: Autómata finito no determinista M1

Figura 2: The computation of N1 on input 010110

2
Figura 3: The NFA N2 recognizing A

Figura 4: A DFA recognizing A

Hay formas para pasar de un DFA a un NFA y viceversa.

La descripción formal del Autómata N2 es:

1. Q = {q1 , q2 , q3 , q4 },
2. Σ = {0, 1},
3. δ = ,

4. q0 = q1 ,
5. F = {q4 }

2. Conclusiones
En compiladores e interpretes se ven estos temas, siempre es mucho más interesante
verlos desde la parte matemática y como lo ve las ciencias de la computación antes de
llegar a la práctica. La práctica también es muy interesante, pero lo fundamental es
esto.

Referencias
[1] M. Sipser, Introduction to the Theory of Computation, 1st ed. International Thom-
son Publishing, 1996.

También podría gustarte