Demostrar que una gramatica genera cadenas con igual numero de a's y b's

La intuicion: cada no terminal lleva una “deuda” de simbolos

Piensa en $S$ como “equilibrado” (mismas $a$‘s que $b$‘s), en $A$ como “debe una $a$ de mas” (siempre genera una $a$ extra), y en $B$ como “debe una $b$ de mas”. Las producciones mantienen esa invariante: $S \to aB$ toma el equilibrio de $S$, agrega una $a$, y compensa con $B$ que aporta una $b$ extra. Lo mismo con $S \to bA$.

Para la parte (a), basta derivar algo simple: $S \Rightarrow aB \Rightarrow ab$. Ahi $n_a = n_b = 1$.

La demostracion formal es por induccion sobre pasos de derivacion, probando tres cosas a la vez: que $S$ produce igualdad, que $A$ produce una $a$ de mas, y que $B$ produce una $b$ de mas. Cada produccion se reduce a un caso mas chico donde aplica la hipotesis inductiva, y las cuentas de $a$‘s y $b$‘s cierran en cada caso.

(a) $S \Rightarrow aB \Rightarrow ab$. Se tiene $n_a(ab) = 1 = n_b(ab)$. $\checkmark$

(b) Se demuestran simultaneamente por induccion sobre $k$ (pasos de derivacion):

• $P_S$: $S \xRightarrow{k} x \implies n_a(x) = n_b(x)$
• $P_A$: $A \xRightarrow{k} x \implies n_a(x) = n_b(x) + 1$
• $P_B$: $B \xRightarrow{k} x \implies n_b(x) = n_a(x) + 1$

Base ($k = 1$): $A \Rightarrow a$: $n_a = 1 = 0 + 1 = n_b + 1$. $\checkmark$
$B \Rightarrow b$: $n_b = 1 = 0 + 1 = n_a + 1$. $\checkmark$
$S$ no tiene derivacion terminal en 1 paso.

H.I.: Las tres afirmaciones valen para derivaciones en $< k$ pasos.

Paso inductivo ($k$ pasos):

$S \Rightarrow aB \xRightarrow{k-1} ax'$: Por $P_B$, $n_b(x') = n_a(x') + 1$. Entonces $n_a(ax') = n_a(x') + 1 = n_b(x') = n_b(ax')$. $\checkmark$

$S \Rightarrow bA \xRightarrow{k-1} bx'$: Por $P_A$, $n_a(x') = n_b(x') + 1$. Entonces $n_b(bx') = n_b(x') + 1 = n_a(x') = n_a(bx')$. $\checkmark$

$A \Rightarrow aS \xRightarrow{k-1} ax'$: Por $P_S$, $n_a(x') = n_b(x')$. Entonces $n_a(ax') = n_a(x') + 1 = n_b(x') + 1 = n_b(ax') + 1$. $\checkmark$

$A \Rightarrow bAA \xRightarrow{k-1} bx_1 x_2$: Por $P_A$, $n_a(x_i) = n_b(x_i) + 1$ para $i = 1, 2$. Entonces:

$n_a(bx_1 x_2) = n_a(x_1) + n_a(x_2) = n_b(x_1) + 1 + n_b(x_2) + 1 = n_b(x_1) + n_b(x_2) + 2$

$= (n_b(bx_1 x_2) - 1) + 2 = n_b(bx_1 x_2) + 1 \quad \checkmark$

$B \Rightarrow bS \xRightarrow{k-1} bx'$: Simetrico a $A \Rightarrow aS$. $\checkmark$

$B \Rightarrow aBB \xRightarrow{k-1} ax_1 x_2$: Simetrico a $A \Rightarrow bAA$. $\checkmark$

Por induccion, $P_S$ queda demostrado. $\blacksquare$

Gramatica

Gramatica

Parte (a): Ejemplo

Derivemos la cadena $abba$ a partir de $S$:

$S \Rightarrow aB \Rightarrow a(bS) \Rightarrow ab(aB) \Rightarrow aba(b) = abab$

Verifiquemos: $n_a(abab) = 2$ y $n_b(abab) = 2$. Efectivamente $n_a = n_b$. $\checkmark$

Otro ejemplo mas simple:

$S \Rightarrow aB \Rightarrow ab$

Aqui $n_a(ab) = 1$ y $n_b(ab) = 1$. $\checkmark$

Parte (b): Demostracion

Demostraremos tres afirmaciones simultaneamente por induccion sobre el numero de pasos de derivacion:

• P(S): Si $S \xRightarrow{*} x$, entonces $n_a(x) = n_b(x)$.
• P(A): Si $A \xRightarrow{*} x$, entonces $n_a(x) = n_b(x) + 1$.
• P(B): Si $B \xRightarrow{*} x$, entonces $n_b(x) = n_a(x) + 1$.

Caso base (derivacion en 1 paso)

• Para $A$: La unica derivacion en un paso es $A \Rightarrow a$. Tenemos $n_a(a) = 1$ y $n_b(a) = 0$, luego $n_a(a) = n_b(a) + 1 = 0 + 1 = 1$. $\checkmark$
• Para $B$: La unica derivacion en un paso es $B \Rightarrow b$. Tenemos $n_b(b) = 1$ y $n_a(b) = 0$, luego $n_b(b) = n_a(b) + 1 = 0 + 1 = 1$. $\checkmark$
• Para $S$: No hay derivacion de $S$ en un solo paso que produzca una cadena terminal.

Hipotesis inductiva

Supongamos que para toda derivacion en menos de $k$ pasos, las tres afirmaciones se cumplen.

Paso inductivo

Consideramos una derivacion en $k$ pasos.

Caso $S \xRightarrow{k} x$:

El primer paso debe ser $S \Rightarrow aB$ o $S \Rightarrow bA$.

• Si $S \Rightarrow aB \xRightarrow{k-1} ax'$ donde $B \xRightarrow{k-1} x'$ (menos de $k$ pasos). Por hipotesis inductiva P(B): $n_b(x') = n_a(x') + 1$. Entonces para $x = ax'$:

  $n_a(x) = n_a(x') + 1 = n_b(x') - 1 + 1 = n_b(x') = n_b(x)$

  Luego $n_a(x) = n_b(x)$. $\checkmark$

• Si $S \Rightarrow bA \xRightarrow{k-1} bx'$ donde $A \xRightarrow{k-1} x'$. Por hipotesis inductiva P(A): $n_a(x') = n_b(x') + 1$. Entonces para $x = bx'$:

  $n_b(x) = n_b(x') + 1 = n_a(x') - 1 + 1 = n_a(x') = n_a(x)$

  Luego $n_a(x) = n_b(x)$. $\checkmark$

Caso $A \xRightarrow{k} x$:

El primer paso es $A \Rightarrow aS$, $A \Rightarrow bAA$ o $A \Rightarrow a$.

• Si $A \Rightarrow aS \xRightarrow{k-1} ax'$ donde $S \xRightarrow{k-1} x'$. Por hipotesis inductiva P(S): $n_a(x') = n_b(x')$. Entonces:

  $n_a(x) = n_a(x') + 1 = n_b(x') + 1 = n_b(x) + 1$

  $\checkmark$

• Si $A \Rightarrow bAA \xRightarrow{k-1} bx_1 x_2$ donde $A \xRightarrow{*} x_1$ y $A \xRightarrow{*} x_2$, ambos en menos de $k$ pasos. Por hipotesis inductiva P(A): $n_a(x_1) = n_b(x_1) + 1$ y $n_a(x_2) = n_b(x_2) + 1$. Entonces:

  $n_a(x) = n_a(x_1) + n_a(x_2) = (n_b(x_1) + 1) + (n_b(x_2) + 1) = n_b(x_1) + n_b(x_2) + 2$

  $n_b(x) = n_b(x_1) + n_b(x_2) + 1$

  Por lo tanto: $n_a(x) = n_b(x) + 1$. $\checkmark$

Caso $B \xRightarrow{k} x$:

Simetrico al caso de $A$.

• Si $B \Rightarrow bS \xRightarrow{k-1} bx'$ donde $S \xRightarrow{k-1} x'$. Por P(S): $n_a(x') = n_b(x')$. Entonces:

  $n_b(x) = n_b(x') + 1 = n_a(x') + 1 = n_a(x) + 1$

  $\checkmark$

• Si $B \Rightarrow aBB \xRightarrow{k-1} ax_1 x_2$ donde $B \xRightarrow{*} x_1$ y $B \xRightarrow{*} x_2$. Por P(B): $n_b(x_1) = n_a(x_1) + 1$ y $n_b(x_2) = n_a(x_2) + 1$. Entonces:

  $n_b(x) = n_b(x_1) + n_b(x_2) = (n_a(x_1) + 1) + (n_a(x_2) + 1) = n_a(x_1) + n_a(x_2) + 2$

  $n_a(x) = n_a(x_1) + n_a(x_2) + 1$

  Por lo tanto: $n_b(x) = n_a(x) + 1$. $\checkmark$

Conclusion

Por induccion, queda demostrado que si $S \xRightarrow{*} x$, entonces $n_a(x) = n_b(x)$. $\blacksquare$