Disenar una CFG para el lenguaje L = {0^n 1^m 2^k | n < k o m < k}

La estrategia: descomponer el OR en union de gramaticas

Cuando ves una condicion con “o” ($n < k$ o $m < k$), piensa en union: disenar una gramatica para cada condicion por separado y luego unirlas con $S \to S_1 \mid S_2$.

Para $L_1$ (donde $n < k$): la idea es emparejar 0’s con 2’s usando $0\,S_1\,2$, luego forzar al menos un 2 extra (eso garantiza $n < k$), y generar los 1’s libremente en el medio. Para $L_2$ (donde $m < k$): lo mismo pero emparejando 1’s con 2’s, y generando los 0’s libremente al inicio.

El patron clave es: para forzar $x < y$, empareja $x$ con $y$ uno a uno y despues agrega al menos un $y$ extra. Eso convierte una desigualdad estricta en algo que una CFG puede manejar.

$L = L_1 \cup L_2$ donde $L_1 = \{0^n 1^m 2^k \mid n < k\}$, $L_2 = \{0^n 1^m 2^k \mid m < k\}$.

$$\begin{aligned} S &\to S_1 \mid S_2 \\[6pt] S_1 &\to 0\,S_1\,2 \mid A_1\,2 \\ A_1 &\to 1\,A_1 \mid B_1 \\ B_1 &\to 2\,B_1 \mid \varepsilon \\[6pt] S_2 &\to C_2\,D_2 \\ C_2 &\to 0\,C_2 \mid \varepsilon \\ D_2 &\to 1\,D_2\,2 \mid E_2\,2 \\ E_2 &\to 2\,E_2 \mid \varepsilon \end{aligned}$$

Verificacion: $S_1$ genera $0^n 1^m 2^{n+j+1}$ con $j \geq 0$, luego $k = n+j+1 > n$. $S_2$ genera $0^n 1^m 2^{m+j+1}$ con $j \geq 0$, luego $k = m+j+1 > m$. $\blacksquare$

Gramatica

Solucion

Analisis del lenguaje

El lenguaje es $L = \{0^n 1^m 2^k \mid n < k \lor m < k\}$.

Podemos descomponerlo como la union de dos lenguajes:

• $L_1 = \{0^n 1^m 2^k \mid n < k\}$
• $L_2 = \{0^n 1^m 2^k \mid m < k\}$

Entonces $L = L_1 \cup L_2$.

Gramatica para $L_1$: $n < k$

La condicion $n < k$ significa $k = n + j$ con $j \geq 1$. Necesitamos emparejar $n$ ceros con $n$ doses, agregar al menos un $2$ extra, y generar cualquier cantidad de $1$‘s en el medio:

$$\begin{aligned} S_1 &\to 0\,S_1\,2 \mid A_1\,2 \\ A_1 &\to 1\,A_1 \mid B_1 \\ B_1 &\to 2\,B_1 \mid \varepsilon \end{aligned}$$

Explicacion:

• $S_1 \to 0\,S_1\,2$ empareja ceros con doses ($n$ veces)
• $S_1 \to A_1\,2$ agrega al menos un $2$ adicional ($j \geq 1$)
• $A_1$ genera cualquier cantidad de $1$‘s
• $B_1$ genera doses adicionales

Gramatica para $L_2$: $m < k$

Analogamente, $m < k$ significa $k = m + j$ con $j \geq 1$:

$$\begin{aligned} S_2 &\to C_2\,D_2 \\ C_2 &\to 0\,C_2 \mid \varepsilon \\ D_2 &\to 1\,D_2\,2 \mid E_2\,2 \\ E_2 &\to 2\,E_2 \mid \varepsilon \end{aligned}$$

Explicacion:

• $C_2$ genera cualquier cantidad de $0$‘s
• $D_2 \to 1\,D_2\,2$ empareja unos con doses ($m$ veces)
• $D_2 \to E_2\,2$ agrega al menos un $2$ adicional
• $E_2$ genera doses adicionales

Gramatica completa para $L = L_1 \cup L_2$

$$\begin{aligned} S &\to S_1 \mid S_2 \\[6pt] S_1 &\to 0\,S_1\,2 \mid A_1\,2 \\ A_1 &\to 1\,A_1 \mid B_1 \\ B_1 &\to 2\,B_1 \mid \varepsilon \\[6pt] S_2 &\to C_2\,D_2 \\ C_2 &\to 0\,C_2 \mid \varepsilon \\ D_2 &\to 1\,D_2\,2 \mid E_2\,2 \\ E_2 &\to 2\,E_2 \mid \varepsilon \end{aligned}$$

Verificacion con ejemplos

Cadena $2 \in L$ (con $n=0, m=0, k=1$): $n < k$ se cumple ($0 < 1$).

$S \Rightarrow S_1 \Rightarrow A_1\,2 \Rightarrow B_1\,2 \Rightarrow 2$

$\checkmark$

Cadena $112 \in L$ (con $n=0, m=2, k=1$): $m < k$ no se cumple, pero $n < k$ si ($0 < 1$).

$S \Rightarrow S_1 \Rightarrow A_1\,2 \Rightarrow 1\,A_1\,2 \Rightarrow 11\,A_1\,2 \Rightarrow 11\,B_1\,2 \Rightarrow 112$

$\checkmark$

Cadena $01222 \in L$ (con $n=1, m=0, k=3$): $n < k$ se cumple ($1 < 3$).

$S \Rightarrow S_1 \Rightarrow 0\,S_1\,2 \Rightarrow 0\,A_1\,2\,2 \Rightarrow 0\,B_1\,2\,2 \Rightarrow 0\,2\,B_1\,2\,2 \Rightarrow 01222$

$\checkmark$

Bono: Demostracion de correccion (bosquejo)

Debemos mostrar que $L(G) \subseteq L$.

Para cadenas generadas por $S_1$: Por induccion sobre la derivacion, $S_1$ genera cadenas de la forma $0^n w 2^n$ donde $w$ se genera a partir de $A_1\,2$. Dado que $A_1$ produce $1^m$ seguido de lo que produce $B_1$ (que genera $2^j$ con $j \geq 0$), y el $2$ adicional garantiza al menos un $2$ extra, la cadena final es $0^n 1^m 2^{n+j+1}$ con $j \geq 0$. Como $k = n + j + 1 > n$, se cumple $n < k$.

Para cadenas generadas por $S_2$: Analogamente, $C_2$ genera $0^n$, y $D_2$ genera cadenas emparejando $1$‘s con $2$‘s mas al menos un $2$ extra, resultando en $0^n 1^m 2^{m+j+1}$ con $k = m + j + 1 > m$, luego $m < k$.

En ambos casos, $n < k$ o $m < k$, por lo que toda cadena generada pertenece a $L$. $\blacksquare$