Una manera eficaz de determinar si dos de contexto libre gramáticas son equivalentes?

Question

Me pregunto si hay una manera eficaz de comprobar si dos de contexto libre gramáticas son equivalentes, además de trabajar fuera "casos de prueba" con la mano (es decir, tratando de ver si ambas gramáticas pueden generar las mismas cosas, y sólo las mismas cosas, por ensayo y error).

Gracias!

Answer 1

No la hay. De hecho, ni siquiera hay una forma ineficiente!

Es decir, el problema de determinar si dos CFGs representan el mismo lenguaje es indecidible. De hecho, aún más la afirmación es verdadera: el problema de determinar si un determinado CFG acepta todas las cadenas sobre el alfabeto es indecidible.

La prueba de esto puede encontrarse en el capítulo 5 de Sipser la Introducción a la Teoría de la Computación. La idea básica es que, para cualquier máquina de Turing $M$, se puede obtener una gramática independiente del contexto que acepta todas las cadenas que no codifican para una prueba de que $M$ se detiene (en algunas codificación específica que es más complicado de lo que yo realmente quiero entrar en aquí). Para determinar si esta gramática acepta todas las cadenas es equivalente a resolver la suspensión problema para $M$.

Answer 2

Este documento proporciona una respuesta "Comparación de Contexto Libre de Gramáticas Basadas en el Análisis de Datos de Prueba Generados", http://link.springer.com/chapter/10.1007%2F978-3-642-28830-2_18. Los autores proponen para generar sub-frases de la gramática y el uso de un analizador generado a partir de la otra para analizarlos. Un análisis estadístico y visualización ayuda a interpretar los resultados.

Citando el resumen:

Existen un número de la ingeniería de software escenarios que esencialmente implican la equivalencia o correspondencia afirmaciones de algunos del contexto libre de las gramáticas en los escenarios. Por ejemplo, cuando la aplicación de la gramática transformaciones durante el desarrollo de analizador -, como por la causa de desambiguación o de la gramática de cumplimiento de clase-a uno le gustaría para preservar el lenguaje generado. Aunque la equivalencia es generalmente indecidible de contexto libre de gramáticas, hemos desarrollado un método automatizado que es útil en la práctica en la revelación de las pruebas de nonequivalence de gramáticas y el descubrimiento de la correspondencia asignaciones para gramática nonterminals. Nuestro enfoque se basa en la sistemática de los datos de prueba generación y análisis. Hablamos de dos estudios que muestran cómo los enfoque se utiliza en la comparación de las gramáticas de Java de código abierto como analizadores así como las gramáticas de los trabajos de curso para la construcción de un compilador clase.