Extensión a cadenas de la función de transición

Views:
 
Category: Education
     
 

Presentation Description

Orientado al tema de Teoría de Autómatas

Comments

Presentation Transcript

Presentación de PowerPoint:

Universidad de Oriente Departamento de Ingeniería de Sistemas Cursos Especiales de Grado Área de Ciencias de la Computación Teoría de Autómatas y Lenguajes Formales (TALF) Profesora: Ing. Nelsys Vivenes. Abril, 2015 Unidad II AFD Extensión a cadenas de la función de transición Bachilleres: José Vásquez Argenis Gil Equipo: Python

Presentación de PowerPoint:

Contenido

Presentación de PowerPoint:

Introducción Los Autómatas Finitos (AF) poseen una característica indispensable como lo es su lenguaje, pero este puede contar o no con aceptación cuando se pretende establecer mediante una extensión.. Los Autómatas Finitos Deterministas, permiten aceptar su estudio mediante cadenas y además las mismas simplifican el entendimiento de cómo actúan ciertos autómatas.

Presentación de PowerPoint:

Presentación La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”. Antes de que existieran las computadoras, en la década de los años treinta, A. Turing estudió una máquina abstracta que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían calcular .

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Un autómata finito determinista consta de:

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Formalismo De Autómata Finito Determinista

Presentación de PowerPoint:

Extensión a cadenas de la función de transición El Lenguaje de un AFD

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Diagramas de transiciones

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Diagramas de transiciones EJEMPLO 2.2 La Figura 2.4 muestra el diagrama de transiciones del AFD que hemos diseñado en el Ejemplo 2.1. En este diagrama podemos ver los tres nodos correspondientes a los tres estados. Hay una flecha etiquetada como Inicio que entra en el estado inicial, q0, y un estado de aceptación, q1, representado mediante un doble círculo. De cada estado sale un arco etiquetado con 0 y otro con 1 (aunque los dos arcos se han combinado en uno con una doble etiqueta en el caso de q1). Cada uno de los arcos corresponde a una de las situaciones de δ desarrolladas en el Ejemplo 2.1. Figura 2.4. Diagrama de transiciones del AFD que acepta todas las cadenas que contienen la subcadena 01.

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Diagramas de transiciones Ejemplo 2.3: La tabla de transiciones correspondiente a la función δ del Ejemplo 2.1 se muestra en la Figura 2.5. También pueden verse otras dos características de una tabla de transiciones. El estado inicial se marca mediante una flecha y los estados de aceptación mediante un asterisco. Dado que es posible deducir los conjuntos de estados y los símbolos de entrada fijándose en los encabezamientos de las filas y las columnas, podemos obtener a partir de la tabla de transiciones toda la información necesaria para especificar el autómata finito de forma unívoca. Figura 2.5. Tabla de transiciones del AFD del Ejemplo 2.1.

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Definición

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Definición

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Universo del Discurso:

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Ejemplo

Presentación de PowerPoint:

Extensión a cadenas de la función de transición Ejemplo Ahora ya sabemos cómo especificar el AFD para el lenguaje L. Así A = ({q0,q1,q2,q3},{0,1},δ ,q0,{q0 }) Figura 2.6 Diagrama de transiciones Figura 2.7 Tabla de transiciones

Presentación de PowerPoint:

Cierre

Presentación de PowerPoint:

Conclusiones

Presentación de PowerPoint:

Referencias

Presentación de PowerPoint:

¡ GRACIAS POR SU ATENCIÓN!

authorStream Live Help