Gramatica G_n: escribir G_3 y demostrar que genera cadenas de longitud par

Para la parte (a), escribir $G_3$ es directo: el simbolo inicial $S$ produce $A_1 A_2 A_3$, y cada $A_i$ genera pares $a_i b_i$ anidados. Es decir, $A_1 \to a_1 A_1 b_1 \mid a_1 b_1$, y lo mismo para $A_2$ y $A_3$ con sus respectivos simbolos. Cada $A_i$ genera cadenas de la forma $a_i^j b_i^j$ con $j \geq 1$.

Para la parte (b), la idea clave es que cada $A_i$ siempre genera un numero par de simbolos. Esto se ve facil: en el caso base $A_i \to a_i b_i$ produce 2 simbolos, y en el caso recursivo $A_i \to a_i A_i b_i$ agrega exactamente 2 simbolos mas (uno por cada lado). Si lo que habia adentro era par, sumarle 2 sigue siendo par. Como la cadena completa es la concatenacion de $n$ bloques, cada uno de longitud par, la longitud total es una suma de numeros pares, que tambien es par.

En resumen: cada bloque $A_i$ contribuye con $2j_i$ simbolos, y la cadena tiene longitud $2(j_1 + j_2 + \cdots + j_n)$, que siempre es par.

(a) $G_3 = (\{S, A_1, A_2, A_3\},\ \{a_1, b_1, a_2, b_2, a_3, b_3\},\ P,\ S)$ con:

$$\begin{aligned} S &\to A_1 A_2 A_3 \\ A_1 &\to a_1 A_1 b_1 \mid a_1 b_1 \\ A_2 &\to a_2 A_2 b_2 \mid a_2 b_2 \\ A_3 &\to a_3 A_3 b_3 \mid a_3 b_3 \end{aligned}$$

(b) Lema. $\forall\, 1 \leq i \leq n$: si $A_i \xRightarrow{*} w$ entonces $|w|$ es par y $|w| \geq 2$.

Induccion sobre el numero de pasos de derivacion:

Base (1 paso): $A_i \Rightarrow a_i b_i$, $|a_i b_i| = 2$. $\checkmark$

Paso inductivo: $A_i \Rightarrow a_i A_i b_i \xRightarrow{*} a_i w' b_i$ con $|w'| = 2p$ por H.I.

$|a_i w' b_i| = 1 + 2p + 1 = 2(p+1) \quad \checkmark$

Teorema. Toda cadena $w \in L(G_n)$ tiene longitud par.

$S \Rightarrow A_1 \cdots A_n \xRightarrow{*} w_1 \cdots w_n = w$ con $A_i \xRightarrow{*} w_i$, $|w_i| = 2p_i$ por el Lema.

$|w| = \sum_{i=1}^{n} |w_i| = \sum_{i=1}^{n} 2p_i = 2\sum_{i=1}^{n} p_i \quad \blacksquare$

Gramatica

Parte (a): Escribir $G_3$

Para $n = 3$, la gramatica $G_3 = (\{S, A_1, A_2, A_3\}, \{a_1, b_1, a_2, b_2, a_3, b_3\}, P, S)$ tiene las producciones:

$$\begin{aligned} S &\to A_1 A_2 A_3 \\[4pt] A_1 &\to a_1 A_1 b_1 \mid a_1 b_1 \\ A_2 &\to a_2 A_2 b_2 \mid a_2 b_2 \\ A_3 &\to a_3 A_3 b_3 \mid a_3 b_3 \end{aligned}$$

Ejemplos de cadenas generadas

• $a_1 b_1 a_2 b_2 a_3 b_3$ (longitud 6): cada $A_i \Rightarrow a_i b_i$
• $a_1 a_1 b_1 b_1 a_2 b_2 a_3 a_3 b_3 b_3$ (longitud 10): $A_1$ genera 2 pares, $A_2$ genera 1 par, $A_3$ genera 2 pares

Lenguaje generado

$L(G_3) = \{a_1^{j_1} b_1^{j_1} a_2^{j_2} b_2^{j_2} a_3^{j_3} b_3^{j_3} \mid j_1, j_2, j_3 \geq 1\}$

Parte (b): Demostrar que cualquier cadena de $G_n$ tiene longitud par

Lema previo

Lema: Para todo $1 \leq i \leq n$, si $A_i \xRightarrow{*} w$, entonces $|w|$ es par y $|w| \geq 2$.

Demostracion por induccion sobre el numero de pasos de derivacion:

Caso base (1 paso): $A_i \Rightarrow a_i b_i$. Tenemos $|a_i b_i| = 2$, que es par. $\checkmark$

Paso inductivo: Sea $A_i \Rightarrow a_i A_i b_i \xRightarrow{*} a_i w' b_i$ donde $A_i \xRightarrow{*} w'$ en menos pasos. Por hipotesis inductiva, $|w'|$ es par, digamos $|w'| = 2p$ con $p \geq 1$. Entonces:

$|a_i w' b_i| = 1 + |w'| + 1 = 2 + 2p = 2(p + 1)$

que es par. $\checkmark$

Demostracion principal

Sea $w$ una cadena generada por $G_n$. Entonces:

$S \Rightarrow A_1 A_2 \cdots A_n \xRightarrow{*} w_1 w_2 \cdots w_n = w$

donde $A_i \xRightarrow{*} w_i$ para cada $1 \leq i \leq n$.

Por el lema anterior, $|w_i|$ es par para todo $i$. Sea $|w_i| = 2p_i$ con $p_i \geq 1$.

Entonces:

$|w| = |w_1| + |w_2| + \cdots + |w_n| = 2p_1 + 2p_2 + \cdots + 2p_n = 2(p_1 + p_2 + \cdots + p_n)$

que es par (suma de numeros pares es par).

Por lo tanto, cualquier cadena de $G_n$ tiene longitud par. $\blacksquare$

Nota adicional

De hecho, la longitud minima de una cadena de $G_n$ es $2n$ (cuando cada $A_i$ genera el par minimo $a_i b_i$), y toda cadena tiene longitud de la forma $2(p_1 + p_2 + \cdots + p_n)$ con $p_i \geq 1$, es decir, longitud $\geq 2n$ y siempre par.