Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 182 vistas

    Definición y Clasificación Autómatas Finitos (AFD)

    Cargado por

    Rojas Lol
    Este documento presenta una introducción a los autómatas finitos deterministas (AFD). Define un AFD como una quintupla que consta de un conjunto de estados, un alfabeto, un estado inicial, una función de transición y un conjunto de estados finales. Explica que un AFD solo puede tener una transición por cada combinación de estado y símbolo de entrada, y que su objetivo es reconocer lenguajes regulares aceptando o rechazando cadenas de entrada. También clasifica los autómatas finitos en deterministas y no deterministas, y propor

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Definición y Clasificación Autómatas Finitos (AFD)

    Cargado por

    Rojas Lol
    182 vistas3 páginas
    Este documento presenta una introducción a los autómatas finitos deterministas (AFD). Define un AFD como una quintupla que consta de un conjunto de estados, un alfabeto, un estado inicial, una función de transición y un conjunto de estados finales. Explica que un AFD solo puede tener una transición por cada combinación de estado y símbolo de entrada, y que su objetivo es reconocer lenguajes regulares aceptando o rechazando cadenas de entrada. También clasifica los autómatas finitos en deterministas y no deterministas, y propor

    Descripción original:

    Autómatas Finitos AFD

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta una introducción a los autómatas finitos deterministas (AFD). Define un AFD como una quintupla que consta de un conjunto de estados, un alfabeto, un estado inicial, una función de transición y un conjunto de estados finales. Explica que un AFD solo puede tener una transición por cada combinación de estado y símbolo de entrada, y que su objetivo es reconocer lenguajes regulares aceptando o rechazando cadenas de entrada. También clasifica los autómatas finitos en deterministas y no deterministas, y propor

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    182 vistas3 páginas

    Definición y Clasificación Autómatas Finitos (AFD)

    Cargado por

    Rojas Lol
    Este documento presenta una introducción a los autómatas finitos deterministas (AFD). Define un AFD como una quintupla que consta de un conjunto de estados, un alfabeto, un estado inicial, una función de transición y un conjunto de estados finales. Explica que un AFD solo puede tener una transición por cada combinación de estado y símbolo de entrada, y que su objetivo es reconocer lenguajes regulares aceptando o rechazando cadenas de entrada. También clasifica los autómatas finitos en deterministas y no deterministas, y propor

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 3

    Instituto Tecnológico de Ciudad Madero

    Lenguajes y Autómatas I

    3.1 Conceptos:
    Definición y clasificación
    de Autómatas Finitos
    (AFD)

     Alumno: Juan David Rojas Vallejo

     Número de Control: 19070066

     Carrera: Ingeniería en Sistemas Computacionales

     Catedrático: M.S.I. Armando Becerra del Ángel

     Grupo: 16:00 – 17:00 hrs.

    27 de abril del 2021


    Definición de un Autómata Finito (AFD)

     Un autómata finito es una modelo computacional que realiza cálculos y operaciones de


    manera automática sobre una entrada que le es dada, produciendo como resultado una
    salida. Para que esto pueda ser llevado a cabo, es necesario que el modelo esté
    conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre
    los estados mencionados.
     El funcionamiento se basa principalmente en partir de un estado inicial donde se recibe
    una cadena de caracteres pertenecientes a un alfabeto que el modelo posee, esta es la
    entrada. Posteriormente, se lee la cadena donde el autómata se desplaza de un lado a
    otro, y se detiene cuando se llega al final de dicha cadena, arribando al conocido “estado
    final” o “estado de aceptación”.
     El objetivo principal de los autómatas finitos es el reconocer lenguajes regulares.

     Su definición formal es la siguiente:

    o Un autómata finito es una quíntupla (Q, Σ, q0, δ, F), donde:


     Q es un conjunto finito de estados.
     Σ es un alfabeto finito.
     q0 ϵ Q es el estado inicial.
     δ: Q x Σ -> Q es una función de transición.
     F ⊆ Q es un conjunto de estados finales.

    Clasificación de Autómatas Finitos

     Deterministas: Cada combinación produce solamente un estado.


     No deterministas: Cada combinación produce varios estados y además son posibles
    transiciones con λ.
    Autómatas Finitos Deterministas

     Este tipo de autómatas admite su definición de dos maneras: Como autómatas


    traductores o reconocedores.
     La definición como autómatas traductores continua a la definición de las máquinas
    secuenciales, y se los podría definir como una subclase de estas, ya que los
    autómatas finitos tendrían como limitante no poder iniciar desde cualquier estado
    como lo hacen en las máquinas secuenciales.

     Los autómatas finitos deterministas son como autómatas reconocedores, ya que


    se ajusta con los contenidos de la informática teórica y utilización que se les da
    dentro del diseño de los analizadores léxicos.
     Estos autómatas solo se limitarán a aceptar o no una determinada cadena recibida en la
    entrada, por lo tanto, podemos decir que la salida de los mismos solo tendrá dos valores
    posibles aceptar o no aceptar a la palabra de entrada.
     Al igual que en las máquinas secuenciales, estos autómatas transitarán entre un
    conjunto finito de estados posibles, a medida que reciban sucesivamente los caracteres
    de entrada, en un instante determinado de tiempo el autómata solo podrá estar en uno y
    solo uno de los estados posibles.

    También podría gustarte