Automatas Finitos Deterministas

Views:
 
Category: Education
     
 

Presentation Description

En la siguiente presentación animada, conoceremos a profundidad sobre los AFD.

Comments

Presentation Transcript

Presentación de PowerPoint:

Universidad de Oriente Núcleo Monagas Departamento de Ingeniería de Sistemas Curso Especial de Grado Área: Ciencias de la Computación Teoría de Autómatas y Lenguajes Formales Unidad II- Visión de los autómatas con salida. Autómatas Finitos Deterministas Tutor: Equipo PHP: Ing. Nelsy Vívenes Ileanne Leal Marycarmen Ramos Maturín, Abril de 2015

Presentación de PowerPoint:

Contenido Introducción Marco teórico Autómata Finito Determinista (AFD) Procesamiento de las cadenas de un Autómata Finito Determinista (AFD) Notaciones simples para los AFD Conclusiones Bibliografía

Presentación de PowerPoint:

Introducción

Presentación de PowerPoint:

Marco Teórico Autómata Finito Determinista (AFD ) Al describir una máquina de estados finitos en particular, debemos incluir las informaciones que varían de un autómata a otro; es decir, no tiene sentido incluir descripciones generales aplicables a todo autómata. Estas informaciones son exactamente las que aparecen en un diagrama de estados y transiciones. • Autómatas : trabaja por sí mismo. • Autómata finito : hace referencia a la variedad determinista. • Determinista : hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado al que el autómata puede hacer la transición a partir de su estado actual . Normalmente , en las demostraciones , definiremos un AFD utilizando la notación de “quíntupla” siguiente : A es el nombre del AFD K: identifica el conjunto de estados. Σ: es el alfabeto de entrada. Q0: es el estado inicial. F: es un conjunto de estados finales. δ: es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado. A = (K, Σ, δ, Q0, F)

Presentación de PowerPoint:

Marco Teórico Procesamiento de las cadenas de un Autómata Finito Determinista (AFD ) Supongamos que (a1, a2 · · · an ) es una secuencia de símbolos de entrada. Comenzaremos con el AFD en el estado inicial, q0. Consultamos la función de transición δ. Para hallar estado al que pasará el AFD A después de procesar el primer símbolo de entrada a1. δ (q0, a1) = q1 a2 δ ( q1, a2 ) (q3, q4,..., qn ) δ ( qi−1, ai ) = qi para todo i Si qn pertenece a F, entonces la entrada ( a1,a2 · · · an ) se acepta y, si no lo es se “rechaza”.

Presentación de PowerPoint:

Marco Teórico Notaciones simples para los AFD Especificar un AFD utilizando una quíntupla con una descripción detallada de la función de transición δ resulta bastante complicado de leer

Presentación de PowerPoint:

Marco Teórico N otaciones simples para los AFD Diagrama de transición: Un diagrama de transiciones de un AFD A = (Q, Σ, δ, q0, F) es un grafo definido como sigue

Presentación de PowerPoint:

Marco Teórico N otaciones simples para los AFD Tabla de transición: Una tabla de transición es una representación tabular convencional de una función, como por ejemplo δ, que toma dos argumentos y devuelve un valor.   0 1 q0 q2 q0 *q1 q1 q1 q2 q2 q1

Presentación de PowerPoint:

Marco Teórico Inicio q0 1 0 q1 0 1 0,1 q2 A = (K, q0, Σ , F, δ ) K {q0, q1, q2} q0 Σ {0,1 } F {q2} δ δ ( q0, 1)= q0 δ ( q0, 0)= q1 δ ( q1, 0)= q1 δ ( q1, 1)= q2 δ ( q2, 0)= q2 δ ( q2, 1)= q2 A = ({q0, q1, q2}, {0,1}, δ, q0, { q2})

Presentación de PowerPoint:

Un autómata finito determinista está dado por un conjunto finito de estados, a menudo determinado como Q. Seguido de un conjunto finito de símbolos de entrada, propuesto como Σ. Una función de transición que toma como demostraciones un estado y un símbolo de entrada, el cual da como resultado un estado. La función de transición se designa corrientemente como δ. Existen dos formas mas simple de representar un autómata que con una quíntuple. Diagrama y tabla de transiciones. Conclusiones

Presentación de PowerPoint:

Bibliografías Hopcroft , J. E.; Motwani , R.; Ullman , J. D, Introducción a la teoría de autómatas, Lenguajes y computación. PEARSON EDUCACIÓN S.A., Madrid, 2007 Quiroga, Edgar, Autómatas y lenguajes formales [en línea], Bogotá, Universidad nacional abierta y a distancia (UNAD) ,2008. Amaya, C (2015). Autómatas y Lenguajes Formales. Duitama, Boyacá, Colombia. . [En línea] Disponible en https://www.camayat.com

Presentación de PowerPoint:

Marycarmen Ramos Ileanne Leal

authorStream Live Help