Automatas de Estado Finito

Autómatas de Estado Finito

1

2

Autómatas de Estado Finito

Mis Correospavillalta@gmail.com

pavillalta@ugb.edu.sv

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