Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 48 vistas

    Automatas

    Cargado por

    jerryter28
    El documento describe el proceso de minimización de un autómata finito. Inicialmente, se presenta el autómata original con 9 estados y un alfabeto de {0,1}. Luego, se identifican los estados distinguibles y no distinguibles, y se realizan cambios en las transiciones para eliminar estados no distinguibles. Finalmente, se obtiene un autómata mínimo equivalente con 5 estados.

    Copyright:

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

    Automatas

    Cargado por

    jerryter28
    48 vistas7 páginas
    El documento describe el proceso de minimización de un autómata finito. Inicialmente, se presenta el autómata original con 9 estados y un alfabeto de {0,1}. Luego, se identifican los estados distinguibles y no distinguibles, y se realizan cambios en las transiciones para eliminar estados no distinguibles. Finalmente, se obtiene un autómata mínimo equivalente con 5 estados.

    Descripción original:

    automatas

    Título original

    automatas

    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?

    El documento describe el proceso de minimización de un autómata finito. Inicialmente, se presenta el autómata original con 9 estados y un alfabeto de {0,1}. Luego, se identifican los estados distinguibles y no distinguibles, y se realizan cambios en las transiciones para eliminar estados no distinguibles. Finalmente, se obtiene un autómata mínimo equivalente con 5 estados.

    Copyright:

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

    Automatas

    Cargado por

    jerryter28
    El documento describe el proceso de minimización de un autómata finito. Inicialmente, se presenta el autómata original con 9 estados y un alfabeto de {0,1}. Luego, se identifican los estados distinguibles y no distinguibles, y se realizan cambios en las transiciones para eliminar estados no distinguibles. Finalmente, se obtiene un autómata mínimo equivalente con 5 estados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 7

    AUTOMATAS Y LENGUAJES FORMALES

    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063


    APORTE MOMENTO 2

    Problemas a desarrollar
    PARTE 1: HALLAR EL AUTMATA MNIMO CORRESPONDIENTE al siguiente autmata finito

    1. Realice la descripcin (notacion) (caracterizacin) matematica del automata (antes de minimizar)


    M es un quintuplo ( k , , , s , F ) , donde :
    :es una funcinde transicin, que a partir de un estado y un simbolo del alfabeto obtiene un nuevo estado
    x {1,0 } { q 0 , q1 , q2 , q3 , q4 , q 5 , q 6 , q 7 ,q 8 }

    K= { q0 , q1 , q2 , q3 , q 4 ,q 5 ,q 6 , q7 , q8 } identifica al conjunto de estados del autmata

    {0,1 } , es el alfabeto de entrada


    s : es el estado inicial, en este caso q0

    AUTOMATAS Y LENGUAJES FORMALES


    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063
    APORTE MOMENTO 2

    F :es un conjunto de estados finales , en este caso q3 , q5 , q8


    es un AFD porque es una funcin , estoimplica que para un estado y un simbolodel alfabeto dados ,

    hbra un y soloun estado siguiente


    2. Plasme la tabla de transicin del autmata. (No es la que generas VAS). (Antes de minimizar)
    Q

    (q,)

    q0

    q2

    q2

    q3

    q0

    q1

    q1

    q5

    q0

    q1

    q1

    q9

    q9

    q4

    q4

    q6

    q6

    q8

    3. Identifique El Lenguaje que reconoce. (Antes de minimizar)

    AUTOMATAS Y LENGUAJES FORMALES


    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063
    APORTE MOMENTO 2

    L= A { 0,1 } / A :ellenguaje que reconoce ser el de todas las posibles cadenas que empiezan por 0 por 1,
    y que terminanen 0 1, sequidos de una combinacin de uno o varios 0 1,bajo ciertas condiciones

    ( propiedades ) que resultan complejas ( ER ) por eso es que se reduce o minimiza el autmata .
    4. Identifique la ER y en una tabla de validacin (puede ser de Excel), verifique una cadena vlida y una no vlida. Tenga en cuenta la
    jerarqua de operadores. (Antes de minimizar)
    ER = ((10+01+00(00)*01+11(11)*10)0)*(00(00)*+11(11)*+(00(00)*1(00)*1+(11(11)*0+00(00)*1(00)*01)(11+10(00)*01)*(0+10(00)*1))
    (1(00)*1+(0+1(00)*01)(11+10(00)*01)*(0+10(00)*1))*+(10+01+00(00)*01+11(11)*10)(10(00)*1+(11+10(00)*01)
    (11+10(00)*01)*(0+10(00)*1))(1(00)*1+(0+1(00)*01)(11+10(00)*01)*(0+10(00)*1))*)
    11
    1111
    111111
    111
    00000
    01

    Cadena valida
    Cadena valida
    Cadena valida
    Cadena no valida
    Cadena no valida
    Cadena no valida

    5. Identifique los estados Distinguibles y los No distinguibles.


    Estados Distinguibles:
    q3,q6
    q3, q2
    q5,q7
    q5,q1

    AUTOMATAS Y LENGUAJES FORMALES


    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063
    APORTE MOMENTO 2

    q8,q6
    q8, q7
    Estados No Distinguibles:
    q0
    q4
    q9
    7. En el proceso de eliminacin de estados, identifique que transiciones se eliminan y cules se re direccionan.
    Muestre la tabla de estados distinguibles.

    AUTOMATA A MINIMIZAR:

    AUTOMATAS Y LENGUAJES FORMALES


    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063
    APORTE MOMENTO 2

    Etapa 0:
    Se debe re direccionar la relacin que parte del estado q0 hasta los estados q1,q2; tambin se re direcciona la
    relacin entre q1,q5. Por lo tanto resulta lo siguiente:

    Etapa 1:
    Se debe re direccionar la relacin entre el estado q1,q2 con los estados q3 y q5. Tambin se re direcciona la
    relacin entre q5 y q7. Queda lo siguiente:

    AUTOMATAS Y LENGUAJES FORMALES


    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063
    APORTE MOMENTO 2

    Etapa 2:
    Debemos de re direccionar las relaciones entre el estado q4 y q7, de igual manera con la relacin entre q7 y
    q8.

    AUTOMATA MINIMIZADO:

    AUTOMATAS Y LENGUAJES FORMALES


    PRESENTADO POR: JUEN FRANCISCO GUTIERREZ LOPEZ C.C. 1.110.533.063
    APORTE MOMENTO 2

    TABLA DE ESTADOS DISTINGUIBLES:


    1
    2
    3
    4
    5
    6
    7
    8
    9

    X
    X

    X X
    0 1 2 3 4 5 6 7 8

    También podría gustarte