¿Todo lenguaje libre de contexto es equivalente a uno cuya gramática sólo tiene un símbolo no terminal?

Question

Un lenguaje libre de contexto se genera mediante una gramática libre de contexto, que puede expresarse en la forma Backus-Naur, por ejemplo. Creo que si sólo permitimos un símbolo no terminal en la gramática, los lenguajes resultantes deben ser más simples, posiblemente incluso regulares. Todavía no veo cómo demostrar esto, así que puedes ayudarme:

¿Todo lenguaje libre de contexto es equivalente a uno cuya gramática sólo tiene un símbolo no terminal?

Answer 1

Considere el lenguaje $L = 0 \cup 1^* = \{0\} \cup \{\varepsilon,1,11,111,\ldots\}$ . Esto es obviamente libre de contexto, incluso regular. Sin embargo, no puede ser generada por una gramática con un solo símbolo no terminal. Supongamos que $G$ sería una gramática de este tipo y su único símbolo no terminal es $S$ . Desde $G$ sólo tiene un número finito de producciones hay alguna $n$ tal que $1^n \in L$ no puede generarse en un solo paso, es decir, tiene una derivación $S \Rightarrow^* xSy \Rightarrow^* 1^n$ donde $x,y$ no están ambos vacíos. Entonces $x$ y $y$ no puede contener el símbolo $0$ . Todas las ocurrencias de $S$ en $x$ y $y$ puede ser sustituido por $1$ como $S \Rightarrow 1$ , por lo que podemos derivar una palabra $1^aS1^b$ donde $a,b$ no son ambos cero. Sin embargo, también tenemos una producción $S \rightarrow 0$ para que $G$ también genera la palabra $1^a01^b$ que no está en $L$ ; contradicción.