computer science - palindromo - ¿Cómo puedo determinar si un idioma es libre de contexto o no?
gramatica libre de contexto java (3)
Necesita una gramática para que el idioma determine si está libre de contexto. Una gramática es libre de contexto si todas sus producciones tienen forma "(no terminal) -> secuencia de terminales y no terminales".
¿Cómo puedo saber si los idiomas son libres de contexto o no?
Primero, debe intentar construir una gramática libre de contexto que forme el lenguaje del sujeto. Una gramática está libre de contexto si los lados izquierdos de todas las producciones contienen exactamente un símbolo no terminal. Por definición, si existe uno, entonces el lenguaje está libre de contexto.
Una construcción equivalente sería un autómata pushdown . Es lo mismo que DFA, pero con una pila disponible. Puede ser más fácil de construir que una gramática.
Sin embargo, si no construyes una gramática o un autómata, no significa que un idioma no esté libre de contexto; tal vez, solo eres tú quien no puede construir una gramática lo suficientemente complicada (por ejemplo, una vez pasé unas 7 horas para construir una gramática para un lenguaje complicado).
Si comienza a dudar si el idioma está libre de contexto, debe usar el llamado "lema de bombeo para los idiomas libres de contexto" . Describe una propiedad de todos los idiomas libres de contexto, y si su idioma la viola, entonces definitivamente no es libre de contexto (consulte las notas de uso en Wikipedia).
Este lema es un corolario del lema de Ogden . Entonces, Ogden''s es más poderoso, y si no aplicó el lema de bombeo, podría probar Ogden''s (se usa de la misma manera).
Editar
Como se sugiere en los comentarios para demostrar que un lenguaje no es CFG, creo que es mediante el uso de un lema de ogdens. La mala interpretación inherente contenida en mi respuesta anterior debe ser justificada :) Retener la respuesta anterior para los acechadores.
Vieja respuesta
¡Mirando la gramática y las reglas utilizadas! Como se ve en la imagen (cortesía de wikipedia, jerarquía chomsky). Solo los idiomas regulares no son libres de contexto. Implicar cualquier cosa que use cosas de la forma A-> aB o A-> Ba solo no está libre de contexto.
Las definiciones de Editar A-> aB y A-> Ba tienen la intención de expresar gramáticas recursivas izquierda y derecha y no deben tomarse literalmente.