¿Existe un algoritmo / procedimiento sistemático para probar si un lenguaje no tiene contexto?
En otras palabras, dado un idioma especificado en forma algebraica (piense en algo como ), pruebe si el idioma está libre de contexto o no . Imagine que estamos escribiendo un servicio web para ayudar a los estudiantes con todas sus tareas; usted especifica el idioma y el servicio web genera "sin contexto" o "sin contexto". ¿Hay algún buen enfoque para automatizar esto?
Por supuesto, existen técnicas para la prueba manual, como el lema de bombeo, el lema de Ogden, el lema de Parikh, el lema de Interchange, y más aquí . Sin embargo, cada uno requiere información manual en algún momento, por lo que no está claro cómo convertirlos en algo algorítmico.
Veo que Kaveh ha escrito en otra parte que el conjunto de lenguajes no libres de contexto no es recursivamente enumerable, por lo que parece que no hay esperanza de que ningún algoritmo funcione en todos los lenguajes posibles. Por lo tanto, supongo que el servicio web necesitaría poder mostrar "sin contexto", "sin contexto" o "No puedo decirlo". ¿Hay algún algoritmo que a menudo pueda proporcionar una respuesta que no sea "No puedo decir", en muchos de los idiomas que es probable que uno vea en los libros de texto? ¿Cómo construirías un servicio web así?
Para hacer esta pregunta bien planteada, debemos decidir cómo el usuario especificará el idioma. Estoy abierto a sugerencias, pero estoy pensando en algo como esto:
donde es una expresión de palabras y es un sistema de desigualdades lineales sobre las variables de longitud, con las siguientes definiciones:S
Cada uno de es una expresión de palabras. (Representan variables que pueden contener cualquier palabra en .)Σ ∗
Cada uno de es una expresión de palabras. (Implícitamente, , por lo que representan un solo símbolo en el alfabeto subyacente).Σ = { a , b , c , ... } a , b , c , ...
Cada uno de es una expresión de palabra, si es una variable de longitud.η
La concatenación de expresiones de palabras es una expresión de palabras.
Cada uno de es una variable de longitud. (Representan variables que pueden contener cualquier número natural).
Cada uno de es una variable de longitud. (Estos representan la longitud de una palabra correspondiente).
Esto parece lo suficientemente amplio como para manejar muchos de los casos que vemos en los ejercicios de libros de texto. Por supuesto, si lo desea, puede sustituir cualquier otro método textual para especificar un idioma en forma algebraica.
Respuestas:
Según el teorema de Rice , ver si el lenguaje aceptado por una máquina de Turing tiene alguna propiedad no trivial (aquí: estar libre de contexto) no es decidible. Por lo tanto, tendría que restringir el poder de su maquinaria de reconocimiento (o descripción) para que Turing no esté completa y espere una respuesta.
Para algunas descripciones de lenguaje, la respuesta es trivial: si es por expresiones regulares, es regular, por lo tanto, libre de contexto. Si es por gramáticas libres de contexto, lo mismo.
fuente
Cualquier idioma es aceptado por un Push Down Automata, es un CFL. Aquí hay un desglose detallado para determinar si un idioma es CFL o no. verificar si el idioma es CFL o no
fuente
Pruebe el software JFLAP si solo desea verificar un CFG. Incluso puede pedirle a los desarrolladores de JFLAP que le den el código o algoritmo para el software. puede obtener JFLAP desde aquí http://www.jflap.org/jflaptmp/ es gratis, sin embargo, requiere JDK o JRE o algo así. O tal vez pueda probar otros softwares similares y sus desarrolladores.
fuente