Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 5 vistas

    Solución Hoja de Trabajo 4-3

    Cargado por

    Wilson Andr� Aguirre Cardona
    El resumen describe los pasos para convertir un autómata finito no determinista (AFN) a una expresión regular equivalente mediante la eliminación sucesiva de estados. Se proporcionan ejemplos de cómo cambiar las etiquetas de transición al eliminar estados y cómo combinar las etiquetas para obtener la expresión regular final. También se muestra cómo minimizar un autómata finito determinista (AFD) mediante la partición de estados equivalentes.

    Copyright:

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

    Solución Hoja de Trabajo 4-3

    Cargado por

    Wilson Andr� Aguirre Cardona
    5 vistas7 páginas
    El resumen describe los pasos para convertir un autómata finito no determinista (AFN) a una expresión regular equivalente mediante la eliminación sucesiva de estados. Se proporcionan ejemplos de cómo cambiar las etiquetas de transición al eliminar estados y cómo combinar las etiquetas para obtener la expresión regular final. También se muestra cómo minimizar un autómata finito determinista (AFD) mediante la partición de estados equivalentes.

    Título original

    SOLUCIÓN HOJA DE TRABAJO 4-3

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El resumen describe los pasos para convertir un autómata finito no determinista (AFN) a una expresión regular equivalente mediante la eliminación sucesiva de estados. Se proporcionan ejemplos de cómo cambiar las etiquetas de transición al eliminar estados y cómo combinar las etiquetas para obtener la expresión regular final. También se muestra cómo minimizar un autómata finito determinista (AFD) mediante la partición de estados equivalentes.

    Copyright:

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

    Solución Hoja de Trabajo 4-3

    Cargado por

    Wilson Andr� Aguirre Cardona
    El resumen describe los pasos para convertir un autómata finito no determinista (AFN) a una expresión regular equivalente mediante la eliminación sucesiva de estados. Se proporcionan ejemplos de cómo cambiar las etiquetas de transición al eliminar estados y cómo combinar las etiquetas para obtener la expresión regular final. También se muestra cómo minimizar un autómata finito determinista (AFD) mediante la partición de estados equivalentes.

    Copyright:

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

    Curso: Lenguajes Formales y Autómata

    Hoja de trabajo unidad 4-3


    SOLUCIÓN

    1. Encuentre una Expresión Regular que describa el lenguaje aceptado por el AF con estado
    inicial P, conjunto de estados finales {P}, sobre el alfabeto {0,1} y su función de transición de
    estados descrita por la siguiente matriz de transición:

    SOLUCIÓN:
    El grafo asociado es:

    Se inicia normalizando el AFD, el AFN obtenido es el siguiente:

    Primero, se procede a eliminar el estado R. OJO! Como se dijo en clase, no hay un orden pre-
    establecido para eliminar estados. Se sugiere empezar eliminando los más fáciles es decir lo que
    involucren menos rutas a analizar. Cuando se eliminan estados es necesario GENERAR nuevas
    etiquetas para todos los pares de estados tales que tiene arcos que salen de R o tiene arcos que
    llegan hacia R. Estos estados son S y Q. Para el cambio de S a Q, vía R, la nueva etiqueta será
    “0+10*1” dado que podemos pasar de S a Q directamente, por medio de 0. Después de eliminarse
    el estado R se obtiene el siguiente grafo:

    Después, se remueve el estado S. El estado S tiene tanto arcos salientes como entrantes. Es
    necesario cambiar las etiquetas de transición de los arcos de “P a Q” y “Q a Q”.
     La nueva etiqueta de “P a Q” es “0(0+10*1)”
     La nueva etiqueta de Q a Q se convierte en “1(0+10*1)”

    Después de la eliminación de s, se obtiene:

    Ahora, se elimina el estado Q. Es necesario cambiar las etiquetas de los caminos de “P a P”.
     La nueva etiqueta de “P a P” es “1*+0(0+10*1)(1(0+10*1))*0”
     Dado que hay una forma directa de pasar de “P a P” por medio del carácter “1” y otra
    de pasar de “P a P”, vía Q. Por lo que obtenemos:
    Finalmente, se elimina P. La nueva etiqueta para el camino I a F será la etiqueta vieja de P a P
    estrella. De donde obtenemos:

    De donde obtenemos la respuesta:


    (1*+0(0+10*1)(1(0+10*1))*0)*

    2. Encuentre una Expresión Regular para el AF representado por el grafo siguiente:

    SOLUCIÓN:
    Primero se normaliza el AF:
    Primero, se eliminarán los estados B y A, note que en este caso es bastante simple hacer las
    sustituciones. Se cambiará la etiqueta del camino que va de V a V, vía B con “ab”. Y se cambiará la
    etiqueta del camino que va de I a W con “ab”. El autómata resultante después de la eliminación es:

    Elimínese el estado V. Si se elimina V debe introducirse un arco de I a F con la etiqueta “a(ab)*”.


    Además se debe introducir un arco de I a W con la etiqueta “a(ab)*b”. También debe ser agregado
    un arco de W a W con la etiqueta “a(ab)*b”. Finalmente, agregamos un arco de I a F etiquetando
    con “a(ab)*”. Así que es posible eliminar el estado V, y los arcos que van hacia él y salen de él. Se
    obtiene el nuevo grafo:

    Ahora se elimina el estado W. Solamente es necesario agregar un nuevo arco de I a F con la etiqueta
    “(ab+a(ab)*b)(a(ab)*b)*(λ+a(ab)*)” El grafo se convierte a:
    Al unir las expresiones que aparecen en los arcos obtenemos:

    Por lo tanto la solución buscada es:


    (ab+a(ab)*b)(a(ab)*b)*(λ+a(ab)*)+ a(ab)*

    3. Utilice el algoritmo de minimización para encontrar el AF mínimo equivalente.

    SOLUCIÓN:

    De la primera partición se observa que los estados {a,e,g} son equivalentes de igual manera {b,h} y
    {d,f}, por lo que se realiza la siguiente partición, con cuatro clases de equivalencia:
    De esta partición, a partir de los estados equivalentes, se obtienen 5 clases de equivalencia, {b,h},
    {a,e}, {d,f}, {g}, {c}.

    La anterior partición es la última que puede realizarse ya que al aplicar nuevamente el algoritmo,
    ésta queda invariante. El AFD minimizado es:
    4. Dado el AFD que se presenta a continuación, obtenga el AFD mínimo equivalente
    sobre el alfabeto {a,b}. Utilice el algoritmo de conversión.

    5. Demuestre utilizando el lema de Bombeo que los siguientes lenguajes NO son


    regulares:

    a. L = {xn+3yn+2zn | n es un número natural}


    b. L = {w ∈ {a, b}*| na(w) < nb(w)}

    También podría gustarte