Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Autómatas finitos




Enviado por FRANCISCO RIOS ACOSTA



Partes: 1, 2, 3, 4

    Monografias.com
    91 III AUTÓMATAS FINITOS. 3.1 INTRODUCCIÓN
    …………………………………. 92 3.2 AUTÓMATAS
    FINITOS DETERMINÍSTICOS ……………. 93 3.3
    AUTÓMATAS FINITOS NO DETERMINÍSTICOS ………….
    102 3.4 AUTÓMATAS FINITOS Y EXPRESIONES REGULARES …….
    105 3.5 EQUIVALENCIA ENTRE AFND Y AFD ……………….. 127
    3.6 OPTIMIZACIÓN DE AFD’s . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . 153 3.7 PROPIEDADES DE LOS
    LENGUAJES ACEPTADOS POR UN AUTÓMATA FINITO . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 3.8
    DETERMINACIÓN DE LENGUAJES REGULARES Y NO REGULARES . . .
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    168 3.9 EJERCICIOS PROPUESTOS . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . 169
    Monografias.com
    92 Palabras clave : Automátas finitos
    determinísticos, no deterministicos, AFD,AFND, reglas de
    Thompson, algoritmo de construcción de subgrupos,
    algoritmo de particiones.AFD óptimo, AFD reducido. 3.1
    INTRODUCCIÓN. Habíamos establecido en los
    capítulos anteriores, que un analizador léxico
    reconocía tokens, mediante un monitoreo de izquierda a
    derecha del programa fuente. Para hacer esta tarea menos
    difícil, utilizábamos las expresiones regulares
    para la especificación de los patrones o reglas que
    cumplen los tokens. Los autómatas finitos son las
    herramientas empleadas como reconocedores de tokens, fig. 3.1.
    (b) Fig. 3.1 a) Análisis léxico, b) Interior del
    analizador léxico. Un autómata finito es capaz de
    reconocer un conjunto regular, es decir, un conjunto de cadenas
    denotado por cualquier expresión regular. Recordemos que
    una expresión regular denota a un lenguaje regular. Un
    autómata finito es un reconocedor para un lenguaje, su
    programación no es una tarea compleja, su entrada es una
    cadena x y responde “si” si x es una sentencia del
    lenguaje, “no” de otra manera, fig. 3.2.
    AUTÓMATA FINITO CADENA X “SI” ( reconocimiento
    de X ) “NO” ( No reconocimiento o rechazo de X ) Fig.
    3.2. Entrada y salida de un autómata finito. ANALIZADOR
    LÉXICO (a) AUTÓMATA FINITO PROGRAMA FUENTE PROGRAMA
    FUENTE TOKENS TOKENS
    Monografias.com
    93 Los autómatas finitos se clasifican en : a)
    Determinísticos. b) No Determinísticos. 3.2
    AUTÓMATA FINITO DETERMINÍSTICO (AFD). Es un modelo
    matemático que consiste de : • Un conjunto de
    estados, denominado S. • Un conjunto (alfabeto) de
    símbolos de entrada, denominado ?. • Una
    función de transición move que mapea un par P ( s ,
    a ) a un estado t. s y t son estados contenidos en S, a es un
    símbolo de entrada. • Un estado de inicio, denotado
    por s0. • Un conjunto de estados de aceptación
    (finales), denotado por F. Además, un autómata
    finito determinístico AFD debe cumplir con las siguientes
    características : a) No hay transiciones etiquetadas por
    ?. b) Para cada estado s y un símbolo de entrada a, existe
    a lo más un arco etiquetado por a saliendo de s. Ejemplo
    3.1. El AFD que reconoce al token id identificador en Pascal es
    mostrado en la fig. 3.3. La definición regular es : Letra
    Dig Sub Id ? ? ? ? 0 1 [ A-Za-z ] [ 0-9 ] _ Letra ( Letra | Dig |
    Sub ) * Letra Inicio Letra Dig Fig 3.3 AFD para el token id en
    Pascal. Sub
    Monografias.com
    94 Un autómata es una representación gráfica
    que muestra el proceso de reconocimiento de una cadena de
    entrada. La simbología utilizada es simple : Un
    círculo representa un estado n, donde n es un
    número natural o bien una letra, generalmente. Un arco
    representa la lectura de un símbolo a en la entrada.
    Transición entre estados. Estado de inicio s. s es
    generalmente 0 (cero). Estado de aceptación f. 2. del AFD.
    El conjunto o alfabeto de símbolos de entrada, se obtiene
    de los arcos a ? = { A, B, … , Z, a, b, … , z, 0, 1, … , 9
    , _ } Letra Dig Sub Es decir el alfabeto ? es el conjunto de las
    letras mayúsculas y minúsculas, unidas a los
    dígitos y el símbolo de subrayado ( _ ). 3. La
    función de transición move es realmente una tabla
    de transición, donde los renglones son los estados y las
    columnas son símbolos de entrada. s n a inicio f LyA De
    acuerdo a la notación anterior, dispongámonos a
    obtener los componentes del AFD de la fig. 3.3. 1. El conjunto de
    estados del autómata AFD es : S = { 0,1 } Dos estados…
    !!!
    Monografias.com
    95 Ing. Fco. Ríos Acosta En las columnas debemos ubicar a
    todos los posibles símbolos del alfabeto que pueden
    ocurrir, al efectuar una lectura en la entrada (cadena). En
    nuestro caso son: Letra, Dígito y Subrayado.
    Autómatas Finitos LyA Símbolos en la entrada
    Estados Fig. 3.4 Función move para el AFD que reconoce al
    token id en Pascal. La construcción de la tabla de
    transición -función move- se inicia identificando
    los estados que tienen al menos un arco que “salga”
    de ellos. Para nuestro ejemplo el estado 0 (cero) tiene un arco
    etiquetado por Letra que “sale” de él, y el
    estado 1 tiene 3 arcos: Letra, Dig y Sub. Los estados que tengan
    esta característica son añadidos como los renglones
    en la tabla. Sólo los estados que tengan arcos saliendo de
    ellos, … eeh !!!!!

    Partes: 1, 2, 3, 4

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter