S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB

Fácil cualquier otro método que no sea tratando de encontrar una cadena que generaría dos analizar los árboles ?

Por favor alguien puede darme una cadena que puede demostrar esto.

para mí, esto se parece a su inequívoca.
Permítanme darles la bienvenida a StackOverflow y recordar tres cosas que solemos hacer aquí: 1) Como de recibir ayuda, trate de darle demasiado respondiendo a las preguntas en su área de especialización 2) Read the FAQs 3) Cuando ve bueno Q&A, a votar hastausing the gray triangles, como la credibilidad del sistema se basa en la reputación de que los usuarios obtienen por compartir sus conocimientos. También recordar a aceptar la respuesta que mejor resuelve el problema, si alguno, by pressing the checkmark sign

OriginalEl autor crowso | 2011-02-02

2 Comentarios

  1. 5

    No existe un método sencillo para probar la existencia de una gramática independiente del contexto ambiguo, de hecho,
    la pregunta es indecidible, por reducción a la Post correspondencia problema.

    sí, pero no puedo escribir en la hoja de respuestas. ¿Qué atributos de la gramática debo mirar a seleccionar correctamente la cadena que da lugar a 2 analizar los árboles?
    Según mi copia de Hopcroft y Ullman, usted debe considerar la cadena «aaabbabbba», y encontrar una derivación a la izquierda, una a la derecha de la derivación, y un árbol de análisis utilizando la gramática especificada. Esperemos que, con la solución del ejercicio 4.8 en la mano, el resto se convertirá en claro!
    hay una manera de llegar con una cadena ?
    No hay atajos, básicamente generar todas las posibles analizar los árboles y buscar dos de ellos que producen la misma cadena. Una gramática ambigua será finalmente detectados como tales en tiempo finito…un inequívoco de la gramática, no tanto! (De lo contrario, el problema sería decidable). Desde Hopcroft y Ullman se llama una cadena específica para mirar, no podía ser algo interesante sobre ella. (No se trata de bailar alrededor de la solución, no he trabajado a través de él.)

    OriginalEl autor Jim Lewis

  2. 17

    Hay una cadena: bbaaba

    S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
    S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba
    
    usted debe tomar esto como respuesta correcta

    OriginalEl autor Shweta

Dejar respuesta

Please enter your comment!
Please enter your name here