Demuestre que el siguiente problema es decidible: Dada una gramática libre de contexto $G$ , lo hace $G$ generar cualquier cadena de longitud impar, no vacía?
La respuesta sería sí, pero ¿mostrar cómo el problema es decidible? No estoy seguro, creo que debería enumerar una serie de pasos que implican múltiples FSMs pero siento que debería tener una idea de cómo otros resolverían este problema primero. Supongo que hay una gran variedad de formas posibles de demostrar la decidibilidad.
El conjunto de cadenas de longitud impar es un lenguaje regular, digamos $R$ . Ahora bien, si $L$ es el lenguaje generado por su gramática, su pregunta equivale a preguntar si $L \cap R$ es no vacía. Esta pregunta es decidible . De hecho, $L \cap R$ es libre de contexto (y existe un algoritmo para generar una gramática para él) y se puede decidir si un lenguaje libre de contexto está vacío o no.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
