Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 323 vistas

    3.2 Conversión de Un Autómata Finito No Determinista (Afnd) A Autómata Finito Determinista (AFD)

    Cargado por

    Aldair Leonides Escobar Ciriaco
    Este documento describe cómo convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) en 3 pasos: 1) Transformar los estados del AFND en subconjuntos de estados del AFD. 2) Aplicar la clausura de estados para eliminar el indeterminismo. 3) Eliminar los estados y transiciones inalcanzables desde el estado inicial en el AFD resultante. Se incluye un ejemplo completo de esta conversión.

    Copyright:

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

    3.2 Conversión de Un Autómata Finito No Determinista (Afnd) A Autómata Finito Determinista (AFD)

    Cargado por

    Aldair Leonides Escobar Ciriaco
    323 vistas7 páginas
    Este documento describe cómo convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) en 3 pasos: 1) Transformar los estados del AFND en subconjuntos de estados del AFD. 2) Aplicar la clausura de estados para eliminar el indeterminismo. 3) Eliminar los estados y transiciones inalcanzables desde el estado inicial en el AFD resultante. Se incluye un ejemplo completo de esta conversión.

    Descripción original:

    fh

    Título original

    3.2

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe cómo convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) en 3 pasos: 1) Transformar los estados del AFND en subconjuntos de estados del AFD. 2) Aplicar la clausura de estados para eliminar el indeterminismo. 3) Eliminar los estados y transiciones inalcanzables desde el estado inicial en el AFD resultante. Se incluye un ejemplo completo de esta conversión.

    Copyright:

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

    3.2 Conversión de Un Autómata Finito No Determinista (Afnd) A Autómata Finito Determinista (AFD)

    Cargado por

    Aldair Leonides Escobar Ciriaco
    Este documento describe cómo convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) en 3 pasos: 1) Transformar los estados del AFND en subconjuntos de estados del AFD. 2) Aplicar la clausura de estados para eliminar el indeterminismo. 3) Eliminar los estados y transiciones inalcanzables desde el estado inicial en el AFD resultante. Se incluye un ejemplo completo de esta conversión.

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 7

    3.

    2 CONVERSIÓN DE UN AUTÓMATA FINITO NO


    DETERMINISTA (AFND) A AUTÓMATA FINITO DETERMINISTA
    (AFD).
    INTEGRANTES
    SAUL ELIEZER VALDES LÓPEZ
    VICTOR MANUEL DOMINGUEZ NAVA
    MANUEL CONTRERAS MARMOLEJO
    • puede ser transformado a AFD utilizando un algoritmo que
    transforma los estados del AFND en nuevos estados que son
    subconjuntos de los estados originales y aplica a los mismos la
    clausura para confirmar la conexidad entre cada uno de los
    componentes y así eliminar el indeterminismo.
    Algoritmo
    • Sea un autómata finito estrictamente no determinista (AFND)
    definido por la 5-tupla
    • A=<Q, T, g, F, q0>, donde Q es el conjunto de estados, T el alfabeto de
    símbolos terminales, la relación de transiciones, F son los estados
    finales o de llegada dentro de Q, q0 es el estado inicial o de partida.
    • Paso 1
    • A se transforma en AAFD=<QA,T, gA,FA,q0A>
    • Paso 2
    • Luego se eliminan de AAFD todos los estados y sus correspondientes
    transiciones inalcanzables desde el estado inicial q0A.
    Ejemplo
    • Véase el proceso de transformación de AFND a AFD del
    autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>
    },{f},q0>, que reconoce a las cadenas de as y bs que comienzan con
    cualquiera cantidad de estas letras y terminan forzosamente en ab. El
    siguiente puede ser su diagrama de estados
    • Primero se obtiene autómata
    derivado AAFD=<VAFD,TAFD,gAFD,FAFD,{q0}> a partir del conjunto potencia
    de los estados de A donde:
    • VAFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f}, {q0,q1,f}}.
    • TAFD={a,b}.
    • FAFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.
    Paso 2
    • Luego se retiran los estados inaccesibles {q1}, {f}, {q1,f}, {q0,q1,f},
    determinados mediante la clausura de {q0}, y queda:
    • AAFD={{q0,{q0,q1},{q0,f}},{a,b},{<{q0},b,{q0}>,<{q0},a,{q0,q1}>,<{q0,q1}
    ,a,{q0,q1}>,<{q0,q1},b,{q0,f}>,<{q0,f},a,{q0,q1}>,<{q0,f},b,{q0}>},{
    {q0,f} },{q0}}.
    •

    También podría gustarte