Fácil parcial-2

Verdadero o falso: producciones de una CFG pertenecen a N x (N U Sigma)+

Fuente: Parcial 2 — ST0270-1587 (2024-2)

cfgverdadero-falsoproduccionesdefinicion-formal

Enunciado

Decida si la siguiente afirmacion es verdadera o falsa. Si considera que es verdadera, de un ejemplo; en caso contrario, de un contraejemplo.

Afirmacion: En una gramatica libre de contexto $G = (N, \Sigma, P, S)$ se tiene que $P \subseteq N \times (N \cup \Sigma)^+$ .

Solución rápida — la idea clave sin formalismo

Respuesta rapida: FALSO

La afirmacion dice que las producciones pertenecen a $N \times (N \cup \Sigma)^+$ . El problema esta en el " $+$ ": eso significa cadenas de longitud al menos 1, lo cual excluye la cadena vacia $\varepsilon$ .

Pero las CFG permiten producciones epsilon como $A \to \varepsilon$ . Entonces la definicion correcta usa $(N \cup \Sigma)^*$ (con estrella, no con $+$ ), porque la estrella de Kleene si incluye la cadena vacia.

Un contraejemplo inmediato: la gramatica $S \to aSa \mid \varepsilon$ es una CFG valida. La produccion $S \to \varepsilon$ tiene lado derecho $\varepsilon$ , que no pertenece a $(N \cup \Sigma)^+$ . Eso refuta la afirmacion.

Solución formal — lista para entregar en un parcial

FALSO.

Contraejemplo. Sea $G = (\{S\}, \{a\}, P, S)$ con $P = \{S \to aSa,\; S \to \varepsilon\}$ .

$G$ es una gramatica libre de contexto valida. Sin embargo:

$S \to \varepsilon \in P \implies \varepsilon \in \text{rango de } P$

$\varepsilon \notin (N \cup \Sigma)^+ \quad \text{pues } |\varepsilon| = 0 < 1$

$\therefore\; P \not\subseteq N \times (N \cup \Sigma)^+$

La definicion correcta es $P \subseteq N \times (N \cup \Sigma)^*$ . $\blacksquare$

Gramatica

Explicación completa — paso a paso, con visualizaciones

Solucion

La afirmacion es FALSA.

La afirmacion dice que $P \subseteq N \times (N \cup \Sigma)^+$ , es decir, que el lado derecho de toda produccion pertenece a $(N \cup \Sigma)^+$ , lo cual excluye la cadena vacia $\varepsilon$ .

Sin embargo, en las gramaticas libres de contexto es valido tener producciones de la forma $A \to \varepsilon$ (llamadas producciones epsilon o producciones nulas). La definicion correcta es:

$P \subseteq N \times (N \cup \Sigma)^*$

donde $(N \cup \Sigma)^*$ incluye la cadena vacia.

Contraejemplo

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

$S \to aSa \mid \varepsilon$

Esta es una gramatica libre de contexto valida que genera el lenguaje $L = \{a^n a^n \mid n \geq 0\} = \{(aa)^n \mid n \geq 0\}$ . La produccion $S \to \varepsilon$ tiene lado derecho $\varepsilon$ , y $\varepsilon \notin (N \cup \Sigma)^+$ ya que $(N \cup \Sigma)^+$ solo contiene cadenas de longitud al menos 1.

Por lo tanto, $P \not\subseteq N \times (N \cup \Sigma)^+$ .

Nota

Si bien la forma normal de Chomsky restringe las producciones epsilon (solo permite $S \to \varepsilon$ si $S$ no aparece en el lado derecho de ninguna produccion), la definicion general de CFG permite producciones epsilon para cualquier no terminal.