Verdadero o falso: una gramatica en CNF no puede generar cadenas de longitud impar

Respuesta rapida: FALSO

El contraejemplo mas simple posible: la gramatica en CNF con solo $S \to a$ genera la cadena "$a$", que tiene longitud 1 (impar).

La confusion viene de pensar que como $A \to BC$ siempre duplica no terminales, solo se pueden producir cantidades pares. Pero eso ignora que cada no terminal eventualmente se convierte en exactamente un terminal via $A \to a$. La mecanica real es: empezas con 1 no terminal ($S$), cada regla $A \to BC$ suma 1 no terminal mas, y al final cada no terminal se vuelve 1 terminal. Asi que si aplicas $A \to BC$ exactamente $n-1$ veces, terminas con $n$ terminales, y $n$ puede ser cualquier entero positivo.

En resumen: una CNF genera cadenas de cualquier longitud $n \geq 1$, tanto par como impar.

FALSO.

Contraejemplo. Sea $G = (\{S\}, \{a\}, P, S)$ en CNF con $P = \{S \to a\}$.

$S \Rightarrow a$

$|a| = 1 \quad (\text{impar})$

Contraejemplo general. Sea $G' = (\{S, A, B\}, \{a, b\}, P', S)$ en CNF con:

$S \to AB \mid a, \quad A \to a, \quad B \to AB \mid b$

Derivacion de longitud 3 (impar):

$S \Rightarrow AB \Rightarrow aB \Rightarrow aAB \Rightarrow aaB \Rightarrow aab$

$|aab| = 3 \quad (\text{impar})$

Argumento general. Para generar $w$ con $|w| = n$ en CNF se requieren exactamente $n - 1$ producciones $A \to BC$ y $n$ producciones $A \to a$, totalizando $2n - 1$ pasos. Como $n$ puede ser cualquier entero $\geq 1$, se generan cadenas de longitud tanto par como impar. $\blacksquare$

Gramatica

Solucion

La afirmacion es FALSA.

Una gramatica en forma normal de Chomsky (CNF) si puede generar cadenas de longitud impar.

Recordatorio: Forma Normal de Chomsky

En CNF, todas las producciones tienen una de las siguientes formas:

1. $A \to BC$ (dos no terminales)
2. $A \to a$ (un terminal)
3. $S \to \varepsilon$ (solo si $S$ no aparece en el lado derecho de ninguna produccion)

Contraejemplo

Considere la gramatica en CNF $G = (\{S\}, \{a\}, P, S)$ con:

$S \to a$

Esta gramatica genera el lenguaje $L(G) = \{a\}$, que contiene unicamente la cadena $a$ de longitud 1 (impar).

Otro contraejemplo mas elaborado

Considere la gramatica en CNF $G' = (\{S, A, B\}, \{a, b\}, P, S)$ con:

$$\begin{aligned} S &\to AB \mid a \\ A &\to a \\ B &\to AB \mid b \end{aligned}$$

Esta gramatica genera cadenas como:

• $a$ (longitud 1, impar): $S \Rightarrow a$
• $ab$ (longitud 2, par): $S \Rightarrow AB \Rightarrow aB \Rightarrow ab$
• $aab$ (longitud 3, impar): $S \Rightarrow AB \Rightarrow aB \Rightarrow aAB \Rightarrow aab$

Analisis general

En CNF, cada produccion de la forma $A \to BC$ reemplaza un no terminal por dos no terminales (incremento neto de 1 no terminal), y cada produccion $A \to a$ reemplaza un no terminal por un terminal. Partiendo de $S$, se puede generar cualquier numero de no terminales antes de convertirlos todos a terminales, lo cual permite generar cadenas de cualquier longitud $n \geq 1$.

De hecho, para generar una cadena de longitud $n$ en CNF se requieren exactamente $n - 1$ aplicaciones de producciones $A \to BC$ y $n$ aplicaciones de producciones $A \to a$, para un total de $2n - 1$ pasos de derivacion.