Autómatas finitos deterministas y no deterministas

2 comentarios

Hoy traemos un pequeño resumen acerca de los autómatas finitos deterministas (AFD) y los autómatas finitos no deterministas (AFND)
Autómata finito determinista (AFD)
Cada estado de un autómata de este tipo tiene una transición por cada símbolo del alfabeto.

AFD.

Autómata finito no determinista (AFND)
Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada símbolo del alfabeto. El autómata acepta una palabra si existe al menos un camino desde el estado q0 a un estado final F etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra es rechazada.
Autómata finito no determinista con transiciones ε (AFND-ε)
Además de ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin leer ningún símbolo. Si un estado tiene transiciones etiquetadas con \epsilon, entonces el AFND puede encontrarse en cualquier de los estados alcanzables por las transiciones \epsilon, directamente o a través de otros estados con transiciones \epsilon. El conjunto de estados que pueden ser alcanzados mediante este método desde un estado q, se denomina la clausura \epsilon de q.

Sin embargo, puede observarse que todos estos tipos de autómatas pueden aceptar los mismos lenguajes. Siempre se puede construir un AFD que acepte el mismo lenguaje que el dado por un AFND.

Anuncios

Autómatas finitos no deterministas

Deja un comentario

Estamos realizando actualizaciones sobre los apuntes e imágenes acerca de los autómatas finitos no deterministas, espero que os sirvan de ayuda

Chomsky Backus y Greibach

Deja un comentario

Hoy seguimos actualizando el blog y ya está casi terminado toda la sección de gramáticas, Chomsky, Backus y Greibach además de la explicación de que es una gramática y como se utilizan las gramáticas.

Autómatas finitos deterministas

Deja un comentario

Hoy acabaremos con la explicación de los autómatas finitos deterministas, mañana continuaremos con los autómatas finitos no deterministas

Actualización del blog de autómatas gramáticas y lenguajes formales

Deja un comentario

Continuamos actualizando el de forma continua, en estos días hemos empezado a hablar acerca de los automátas finitos deterministas y de los autómatas finitos no deterministas, a lo largo de esta semana empezaremos hablando de los lenguajes formales y de las gramáticas como por ejemplo Chomsky, Greibach y la nomenclatura de Backus.

Un saludo

Bienvenidos a nuestro nuevo blog

Deja un comentario

Hola y bienvenidos a nuestro nuevo blog en el que vamos a ofrecer una serie de apuntes, transparencias y resúmenes acerca de la asignatura del grado de informática de Teoría de Autómatas y Lenguajes Formales, los puntos de esta asignatura a los que más importacia vamos a dar, van a ser los autómatas finitos deterministas, autómatas finitos no deterministas, lenguajes formales y gramáticas.

A lo largo de la semana iremos publicando alguna entrada, ya con algún resumen.

Un saludo y bienvenidos.