Demostrar que derivar una cadena de longitud 2k en CNF requiere 4k - 1 pasos

En una gramatica en Forma Normal de Chomsky (CNF) solo hay dos tipos de reglas: las que parten un no terminal en dos ($A \to BC$) y las que convierten un no terminal en un terminal ($A \to a$). Piensa en ello como un arbol binario: cada regla binaria crea una rama y cada regla terminal produce una hoja. Si quieres obtener una cadena de longitud $2k$, necesitas exactamente $2k$ hojas (terminales) y por lo tanto $2k - 1$ ramificaciones (reglas binarias), porque un arbol binario completo con $m$ hojas siempre tiene $m - 1$ nodos internos.

Entonces el total de pasos es simplemente la suma: $(2k - 1)$ pasos para ramificar $+$ $2k$ pasos para convertir cada hoja en un terminal $= 4k - 1$ pasos. Es un conteo directo que viene de la estructura rigida de CNF, donde no hay atajos ni alternativas: cada terminal requiere exactamente una regla terminal, y llegar a tener $2k$ no terminales listos requiere exactamente $2k - 1$ reglas binarias.

Como caso concreto, para una cadena de longitud 2 ($k=1$): necesitas 1 regla binaria ($S \to BC$) y 2 reglas terminales ($B \to a$, $C \to b$), dando $4(1) - 1 = 3$ pasos.

Lema. En una gramatica en CNF, derivar una cadena de longitud $n \geq 1$ requiere exactamente $2n - 1$ pasos.

Demostracion por induccion fuerte sobre $n$:

Base ($n = 1$): $A \Rightarrow a$ en $2(1) - 1 = 1$ paso. $\checkmark$

Paso inductivo ($n \geq 2$): La primera produccion es $A \Rightarrow BC$. Sea $B \xRightarrow{*} x_1$ con $|x_1| = n_1 \geq 1$ y $C \xRightarrow{*} x_2$ con $|x_2| = n_2 \geq 1$, donde $n_1 + n_2 = n$. Por H.I.:

$\text{Pasos} = 1 + (2n_1 - 1) + (2n_2 - 1) = 2(n_1 + n_2) - 1 = 2n - 1 \quad \checkmark$

Corolario. Para $n = 2k$ con $k \geq 1$:

$2(2k) - 1 = 4k - 1 \quad \blacksquare$

Gramatica

Solucion

Recordatorio: Forma Normal de Chomsky

En CNF, las producciones son de dos tipos:

1. Tipo binario: $A \to BC$ (dos no terminales)
2. Tipo terminal: $A \to a$ (un terminal)

A continuacion, una gramatica de ejemplo en CNF:

Proposicion

Para derivar una cadena de longitud $2k$ (con $k \geq 1$) en una gramatica en CNF, se requieren exactamente $4k - 1$ pasos.

Demostracion

Conteo de producciones tipo binario ($A \to BC$):

Partimos de una forma sentencial con 1 no terminal ($S$). Cada aplicacion de una produccion $A \to BC$ reemplaza un no terminal por dos no terminales, incrementando el numero de no terminales en 1.

Para terminar con $2k$ terminales, necesitamos $2k$ no terminales en la forma sentencial justo antes de aplicar las producciones terminales (cada no terminal se reemplazara por exactamente un terminal). Partiendo de 1 no terminal, necesitamos incrementar a $2k$, lo que requiere:

$2k - 1 \text{ aplicaciones de producciones tipo binario}$

Conteo de producciones tipo terminal ($A \to a$):

Cada una de las $2k$ posiciones terminales de la cadena se obtiene aplicando exactamente una produccion terminal. Por lo tanto necesitamos:

$2k \text{ aplicaciones de producciones tipo terminal}$

Total de pasos:

$$\text{Total} = (2k - 1) + 2k = 4k - 1$$

Visualizacion del conteo de pasos

Observa como se acumulan los pasos binarios y terminales para distintos valores de $k$:

Demostracion formal por induccion

Caso base ($k = 1$, cadena de longitud 2):

Se necesitan $4(1) - 1 = 3$ pasos:

1. $S \Rightarrow BC$ (produccion binaria)
2. $BC \Rightarrow aB$ (produccion terminal en $B$ o $C$, por ejemplo $B \to a$, elijamos $BC \Rightarrow aC$)
3. $aC \Rightarrow ab$ (produccion terminal, $C \to b$)

Total: 3 pasos. $\checkmark$

Hipotesis inductiva: Supongamos que para derivar cualquier cadena de longitud $2j$ con $1 \leq j < k$, se requieren exactamente $4j - 1$ pasos.

Paso inductivo (cadena de longitud $2k$):

La primera derivacion debe ser $S \Rightarrow BC$ (produccion binaria, 1 paso).

Sea $x = x_1 x_2$ la cadena generada, donde $B \xRightarrow{*} x_1$ y $C \xRightarrow{*} x_2$ con $|x_1| = 2i$ y $|x_2| = 2j$ donde $i + j = k$, $i \geq 1$ y $j \geq 1$.

Observacion: en CNF, todo no terminal genera cadenas de longitud par (ya que cada no terminal se expande en dos, y solo las hojas producen terminales; el arbol de derivacion es un arbol binario completo, que siempre tiene un numero par de hojas cuando no hay produccion $S \to \varepsilon$). Para longitudes impares, necesitariamos la produccion $S \to \varepsilon$ que solo genera $\varepsilon$, lo cual no aplica aqui.

Nota: En realidad, un no terminal en CNF puede generar cadenas de cualquier longitud $\geq 1$. El argumento correcto es:

Por hipotesis inductiva (generalizada a cualquier no terminal, no solo $S$):

• $B$ deriva $x_1$ de longitud $|x_1|$ en exactamente $2|x_1| - 1$ pasos
• $C$ deriva $x_2$ de longitud $|x_2|$ en exactamente $2|x_2| - 1$ pasos

Resultado general: Para derivar una cadena de longitud $n \geq 1$ en CNF se necesitan exactamente $2n - 1$ pasos. Esto es porque necesitamos $n - 1$ producciones binarias y $n$ producciones terminales, totalizando $2n - 1$.

Aplicando a $n = 2k$:

$2(2k) - 1 = 4k - 1$

Demostracion directa del resultado general

Lema: En una gramatica en CNF, para derivar una cadena de longitud $n \geq 1$ se requieren exactamente $2n - 1$ pasos.

Demostracion por induccion fuerte sobre $n$:

Caso base ($n = 1$): La unica forma de generar una cadena de longitud 1 es con una sola produccion terminal $A \to a$. Esto toma $2(1) - 1 = 1$ paso. $\checkmark$

Paso inductivo ($n \geq 2$): La primera produccion aplicada debe ser de tipo binario: $A \to BC$ (1 paso). Luego $B \xRightarrow{*} x_1$ con $|x_1| = n_1 \geq 1$ y $C \xRightarrow{*} x_2$ con $|x_2| = n_2 \geq 1$ donde $n_1 + n_2 = n$.

Por hipotesis inductiva, $B$ requiere $2n_1 - 1$ pasos y $C$ requiere $2n_2 - 1$ pasos.

$\text{Total} = 1 + (2n_1 - 1) + (2n_2 - 1) = 2(n_1 + n_2) - 1 = 2n - 1$

$\checkmark$

Corolario: Para $n = 2k$, se requieren $2(2k) - 1 = 4k - 1$ pasos. $\blacksquare$