Un lenguaje libre de contexto (CFL) es un lenguaje generado por alguna gramática libre de contexto (CFG).
Un lenguaje regular (también llamado lenguaje racional) es un lenguaje formal que puede expresarse mediante una expresión regular.
Pregunta: Supongamos que $L_1$ es un lenguaje libre de contexto y $L_2$ es un lenguaje normal. ¿Existe algún algoritmo para decidir que $L_1 \cap L_2$ ¿está vacío o no?
La respuesta es sí. Dada una gramática libre de contexto que genera un lenguaje $L_1$ y una lengua regular $L_2$ dado por algún autómata finito, se puede construir efectivamente una gramática libre de contexto que genere el lenguaje $L_1 \cap L_2$ . Ahora, dada una gramática libre de contexto, se puede decidir si el lenguaje que genera 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.
