Diagnóstico del estado de la alfabetización en información ...
Automatas de estado finito
-
Upload
pedro-antonio-villalta-pavillalta -
Category
Education
-
view
2.694 -
download
1
description
Transcript of Automatas de estado finito
Automatas de Estado Finito
Autómatas de Estado Finito
1
2
Autómatas de Estado Finito
Facebook y TwitterFacebook.com/pavillaltatwitter.com/pavillalta
Pedro Antonio Villaltahttps://plus.google.com/u/0/105223072803758915793/about
Mis perfiles en Redes Sociales
http://compiladores-interpretes.blogspot.com /
http://programacion-visualbasic-net.blogspot.com /
http://ingenieria-en-sistemas-informaticos.blogspot.com/
http://investigacion-cientifica-docente.blogspot.com /
http://soporteredes.blogspot.com/
http://ecomerce-comercio-electronico.blogspot.com /
http://miw2012.blogspot.com/
http://programacion-visual-c-net.blogspot.com /
http://programacion-web-php.blogspot.com/
http://programacion-moviles.blogspot.com/
http://noticias-detecnologia.blogspot.com /
MIS BLOG EDUCATIVOS
OBJETIVOS
Revisión de tarea, preguntas de la guía anterior.
Conocer el concepto de los autómatas finitos
Conocer los tipos de autómatas finitos DFA y
DNFA.
Funcionamiento de los autómatas finitos DFA
Funcionamiento de los autómatas finitos DNFA.
Ejemplos de autómatas finitos usando JFLAP
Automatas de Estado Finito
5
SECCIÓN DE PREGUNTAS SOBRE JFLAP ¿Qué es JFlap, como se instala y para qué se usa?
¿Qué es JLex, cómo se instala y para qué se usa?
¿Cómo implementar problemas de lenguajes
formales según la jerarquía de Chomsky, con
Jflap?
Qué son los autómatas finitos y autómatas de pila.
Automatas de Estado Finito
6
¿QUÉ ES UN AUTÓMATA FINITO? Un autómata finito es un conjunto de nodos y aristas
que representan trayectorias para generar una expresión bajo un alfabeto.
Un diagrama de transición es un autómata finito.
Automatas de Estado Finito
7
ELEMENTOS DEL AUTÓMATA FINITO Los estados se identifican dentro de un circulo.
El estado inicial recibe una flecha de transición que llega
de ninguna parte.
Los estado aceptadores pueden identificarse con doble
circulo o con una cruz(igual que signo +) al lado de ellos.
Las posibles transiciones se indicaran con flechas que
van de un estado a otro, o incluso a sí mismos. Deben
etiquetarse con el símbolo que produce el cambio de
estado.
Automatas de Estado Finito
8
LOS ESTADO DEL AUTÓMATA
Entonces decimos que los estado del autómata pueden ser:
Estados iniciales Estados finales llamados aceptadores Estados finales no aceptadores
La palabra que va de un estado a otro solo pertenece al lenguaje si el estado que la recibe es aceptador.
Y lo contrario, si llega al final hasta un estado no aceptador, la palabra no pertenece al lenguaje.
Automatas de Estado Finito
9
EJEMPLO GRÁFICO DE AUTÓMATA FINITO
Automatas de Estado Finito
10
SUPONGAMOS UN LENGUAJE X El lenguaje X es capaz de identificar la siguiente
cadena.
w=aabab
Tratemos de identificar los procesos del Autómata.
Automatas de Estado Finito
11
EXPLICACIÓN DEL AUTOMATA
1. Para comenzar estamos en el estado A, podemos llamarle estado 1.
2. Hacemos la transición a B cuando leemos el símbolo a.
3. Realizamos la siguiente transición de B hacia B porque leemos nuevamente otro símbolo a.
4. Para leer b creamos otro estado D al que llegaremos desde donde estamos que es B.
5. Para leer el siguiente símbolo que es a transferimos de nuevo hacia B.
6. Luego para leer el siguiente símbolo b, el autómata regresa hasta D.
Automatas de Estado Finito
12
EJEMPLO DE ALGORITMO PARA AUTÓMATA
Automatas de Estado Finito
13
CLASIFICACIÓN DE LOS AUTÓMATAS FINITOS
O Autómatas finitos determinísticos (DFA)
O Autómatas finitos no determinísticos (DNFA)
Automatas de Estado Finito
14
AUTÓMATA FINITO DETERMINISTA (DFA) Es un dispositivo que puede estar en un estado de
entre un número finito de los mismos; uno de ellos será el estado inicial y por lo menos uno será estado de aceptación.
Tiene un flujo de entrada por el cual llegan los
símbolos de una cadena que pertenecen a un
alfabeto determinado.
Automatas de Estado Finito
15
AUTÓMATA FINITO DETERMINISTA (DFA) Se detecta el símbolo y dependiendo de este
y del estado en que se encuentre hará una transición a otro estado o permanece en el mismo.
El mecanismo de control o programa es que
determina cual es la transición a realizar.
Automatas de Estado Finito
16
ANALIZAR EL SIGUIENTE EJEMPLO.
Automatas de Estado Finito
17
QUÉ PODEMOS DEDUCIR DE ÉSTE EJEMPLO?
Sobre las transiciones
Sobre los estados
Sobre los símbolos procesados.
Automatas de Estado Finito
18
PORQUÉ FINITO, POR QUÉ DETERMINISTA?
Porqué finito:
Se refiere que hay un conjunto finito de estados.
Porque determinista:
La palabra determinista es porque el programa
no debe tener ambigüedades, es decir, en
cada estado solo se puede dar una y solo
una (ni dos ni ninguna) transición para cada
símbolo posible.
Automatas de Estado Finito
19
El autómata acepta la cadena de entrada si la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena.
Si después del último símbolo la máquina no queda
en estado de aceptación, se ha rechazado la
cadena.
Automatas de Estado Finito
20
TUPLAS DEL AUTÓMATA FINITO
Automatas de Estado Finito
21
EXPLICACIÓN DEL DIAGRAMA DETERMINISTA
Estará caracterizado porque debe estar totalmente definido:
Para cada estado solo debe salir un arco y solo
uno para cada símbolo (el autómata no puede
determinar la transición en el caso de que
haya dos arcos con el mismo símbolo o no
haya ninguno).
Automatas de Estado Finito
22
EXPLICACIÓN DEL DIAGRAMA DETERMINISTA
Automatas de Estado Finito
23
EJEMPLO: DEFINICIÓN El alfabeto S = { a, b, c }
Reconoce la cadena c
La cadena a
Las cadenas que empiezan por a y acaban en a o en b y
Las que empiezan por a, seguidas de una serie de a ó de
b y acaban en c
Automatas de Estado Finito
24
EJEMPLO: AUTÓMATA
Automatas de Estado Finito
25