S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB
¿Algún otro método fácil que no sea tratar de encontrar una cadena que genere dos árboles de análisis sintáctico?¿cómo puedo demostrar que esta gramática es ambigua?
¿Puede alguien por favor dame una cadena que puede probar esto.
No hay un método fácil para probar una gramática sin contexto ambigua, de hecho, the question is undecidable, por reducción al Post correspondence problem.
, sí, pero no puedo escribir eso en la hoja de respuestas . ¿A qué atributos de la gramática debo mirar para seleccionar correctamente la secuencia que da lugar a 2 árboles de análisis sintáctico? – crowso
@user: según mi copia de Hopcroft y Ullman, debe considerar la cadena "aaabbabbba", y encontrar una derivación izquierda, una derivación derecha y un árbol de análisis sintáctico utilizando la gramática que ha especificado. Con suerte, con la solución para ejercitar 4.8 en la mano, ¡el resto se aclarará! –
¿hay alguna manera de encontrar una cuerda? – crowso
Hay una cadena sin embargo: bbaaba
S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba
@crowso debes elegir esto como la respuesta correcta – Yugi
para mí esto se parece a su ambigüedad. – crowso
Permítanme darle la bienvenida a StackOverflow y recordarles tres cosas que solemos hacer aquí: 1) A medida que reciba ayuda, trate de darle también ** respondiendo preguntas ** en su área de experiencia 2) ['Lea las preguntas frecuentes'] (http://tinyurl.com/2vycnvr) 3) Cuando vea buenas preguntas y respuestas, vote por ellas ['usando los triángulos grises'] (http://i.imgur.com/kygEP.png), ya que la credibilidad de la El sistema se basa en la reputación que obtienen los usuarios al compartir sus conocimientos. También recuerde aceptar la respuesta que mejor resuelva su problema, si hay alguno, ['presionando el signo de la marca de verificación '] (http://i.imgur.com/uqJeW.png) –