Automatas de estado finito

25
Autómatas de Estado Finito 1 Automatas de Estado Finito

description

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.

Transcript of Automatas de estado finito

Page 1: Automatas de estado finito

Automatas de Estado Finito

Autómatas de Estado Finito

1

Page 2: Automatas de estado finito

2

Autómatas de Estado Finito

Mis [email protected]

[email protected]

Facebook y TwitterFacebook.com/pavillaltatwitter.com/pavillalta

Pedro Antonio Villaltahttps://plus.google.com/u/0/105223072803758915793/about

Page 4: Automatas de estado finito

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

Page 5: Automatas de estado finito

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

Page 6: Automatas de estado finito

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

Page 7: Automatas de estado finito

¿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

Page 8: Automatas de estado finito

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

Page 9: Automatas de estado finito

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

Page 10: Automatas de estado finito

EJEMPLO GRÁFICO DE AUTÓMATA FINITO

Automatas de Estado Finito

10

Page 11: Automatas de estado finito

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

Page 12: Automatas de estado finito

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

Page 13: Automatas de estado finito

EJEMPLO DE ALGORITMO PARA AUTÓMATA

Automatas de Estado Finito

13

Page 14: Automatas de estado finito

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

Page 15: Automatas de estado finito

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

Page 16: Automatas de estado finito

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

Page 17: Automatas de estado finito

ANALIZAR EL SIGUIENTE EJEMPLO.

Automatas de Estado Finito

17

Page 18: Automatas de estado finito

QUÉ PODEMOS DEDUCIR DE ÉSTE EJEMPLO?

Sobre las transiciones

Sobre los estados

Sobre los símbolos procesados.

Automatas de Estado Finito

18

Page 19: Automatas de estado finito

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

Page 20: Automatas de estado finito

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

Page 21: Automatas de estado finito

TUPLAS DEL AUTÓMATA FINITO

Automatas de Estado Finito

21

Page 22: Automatas de estado finito

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

Page 23: Automatas de estado finito

EXPLICACIÓN DEL DIAGRAMA DETERMINISTA

Automatas de Estado Finito

23

Page 24: Automatas de estado finito

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

Page 25: Automatas de estado finito

EJEMPLO: AUTÓMATA

Automatas de Estado Finito

25