Deje $G=(\Sigma,N,R,S)$ ser una gramática independiente del contexto. Para cada regla de producción --> w, podemos decir que su longitud es de $r$ si $|w|=r$. Además de la $n = |N|$, e $k =$ la longitud máxima de una regla de producción de la gramática. Asumimos aquí que $L(G)$ no está vacío. Encontrar un estrecho límite superior (una expresión aritmética f(n,k)) para el menor palabra en L(G). Es decir, encontrar una expresión tal que la menor palabra en L(G) es en la mayoría de f(n,k), pero hay otra gramática independiente del contexto F, tal que la menor palabra en L(F) es exactamente f(n,k). Muchas gracias :)
Respuesta
¿Demasiados anuncios?
fattire
Puntos
716
Intuitivamente, si estamos tratando de hacer que la palabra tan corta como sea posible, puede que quiera deshacerse de los no-terminales tan pronto como sea posible y reemplazarlos por unos terminales como podemos.
Más formalmente, si el idioma $L(G)$ no está vacía, la gramática debe contener al menos una regla de la forma $A\rightarrow w$ $w$ que contiene los no-terminales (de lo contrario nunca sería capaz de deshacerse de todos ellos); vamos a llamar a esta regla terminal . Ahora, considere la posibilidad de la terminal de la regla con $|w|$ tan corto como sea posible. Cada vez que nos encontramos con la no-terminal de la $A$, tendríamos que eventualmente aplicar algún terminal de la regla de deshacerse de él. Sin embargo, esa regla sería el resultado en al menos tantos terminales como aplicar el elegido de inmediato; por lo que podemos aplicar el elegido regla tan pronto como nos sea posible y olvidar todas las otras normas aplicables a $A$ (ya que no se usa nunca).
La gramática puede ser simplificado un poco ahora: Desde $A$ ahora es esencialmente el mismo como $w$, podemos conseguir realmente deshacerse de $A$ completo y reemplazarlo por $w$ en todas las reglas. Así se reduce el conjunto de no terminales por uno y, posiblemente, se amplía la duración de las restantes reglas de producción. Esta expansión es en la mayoría de las $k$-a veces, sin embargo, debido a que cada regla tiene en la mayoría de las $k$ no-terminales en el lado derecho (y, muy importante, este se mantiene fiel después de la expansión demasiado). La nueva gramática ha $(n-1)$ no-terminales y la longitud máxima de la regla de producción en el que dos no exceda $k^2$.
No muy sorprendentemente, se puede repetir el mismo proceso una y otra vez, reducir el número de no-terminales por $1$ y la expansión de la producción de normas en la mayoría de las $k$veces cada vez. Repitiendo $(n-1)$ veces en el total de los rendimientos de una gramática con un no-terminal y reglas de producción de longitud no superior a $f(n,k)=k^n$, lo que nos da la deseada límite superior de la longitud de la menor palabra en $G$.
En fin a ver que es estricto, es suficiente para considerar una simple gramática $G_{n,k}=(\{a\},\{A_1,A_2,\ldots A_n\}, R, A_1)$ con conjunto de reglas $R$: $$\begin{eqnarray*} A_1 & \rightarrow & \overbrace{A_2A_2 \ldots A_2}^{k} \\ A_2 & \rightarrow & A_3A_3 \ldots A_3 \\ & \ldots & \\ A_{n-1} & \rightarrow & A_nA_n \ldots A_n\\ A_n & \rightarrow & \underbrace{aa\ldots a}_{k} \\ \end{eqnarray*}$$
