Lenguajes con gramática libre de contexto que sólo tienen un símbolo no terminal

Question

Como se ve en esta pregunta la clase de lenguajes que puede ser generada por una gramática libre de contexto que sólo tiene un símbolo no terminal (es decir, el símbolo de inicio) es una subclase propia de la clase de lenguajes libres de contexto (en particular, no contiene ni está contenida en la clase de lenguajes regulares).

Me gustaría saber si existe un nombre de uso común para esta subclase y, lo que es más importante, si es decidible si un lenguaje $L$ generado por una gramática libre de contexto $G$ pertenece a esta clase o no (tal vez bajo algunas suposiciones sobre $G$ ).

Cualquier referencia a temas relacionados sería muy apreciada. Gracias.

Answer 1

No es una respuesta real, sino una modesta indicación.

En el contexto de la llamada "complejidad descripcional" de los modelos formales, el número de no terminales necesarios para especificar un lenguaje libre de contexto se denomina la complejidad no terminal . Hay un artículo de Dassow y Stiebe, Complejidad no terminal de algunas operaciones en lenguajes libres de contexto que, por ejemplo, muestra que el lenguaje $a\{a,b\}^*a\{a,b\}^*$ tiene complejidad dos, es decir, no pertenece a su clase. Por lo demás, el documento está más interesado en ejemplos de complejidad $n$ .

Como sabes, los lenguajes libres de contexto pueden describirse mediante sistemas de ecuaciones lingüísticas. Así que su familia deben ser los lenguajes que tienen una única ecuación (en lugar de un sistema). Por ejemplo, el lenguaje Dyck (unilateral) es $L = aLbL \cup \{\lambda\}$ .