Proponer una CFG para el lenguaje {a^n b^m c^k | n >= m, k >= 5}

La idea: separar las dos restricciones independientes

Las dos condiciones ($n \geq m$ y $k \geq 5$) son independientes entre si: una afecta a las $a$‘s y $b$‘s, la otra a las $c$‘s. Entonces separamos la gramatica en dos partes con $S \to AB$.

Para $n \geq m$: escribimos $n = m + j$ donde $j \geq 0$. Primero generamos $j$ a’s extras con $A \to aA$, y luego emparejamos $a$‘s con $b$‘s usando $C \to aCb \mid \varepsilon$. Resultado: $a^j a^m b^m = a^{j+m} b^m$.

Para $k \geq 5$: forzamos 5 c’s fijas con $B \to cccccD$, y luego $D$ genera las adicionales con $D \to cD \mid \varepsilon$.

El patron general: para $x \geq y$, empareja $y$ con $y$ y genera el excedente por separado. Para $k \geq$ constante, escribe la constante literalmente y genera el resto con recursion.

$L = \{a^n b^m c^k \mid n \geq m \land k \geq 5\}$.

$$\begin{aligned} S &\to AB \\[4pt] A &\to aA \mid C \\ C &\to aCb \mid \varepsilon \\[4pt] B &\to cccccD \\ D &\to cD \mid \varepsilon \end{aligned}$$

Correccion. $A$ genera $a^j C$ con $j \geq 0$, y $C$ genera $a^m b^m$ con $m \geq 0$. Entonces $A$ genera $a^{j+m} b^m$ donde $n = j + m \geq m$. $B$ genera $c^{5+l}$ con $l \geq 0$, donde $k = 5 + l \geq 5$. La cadena completa es $a^n b^m c^k$ con $n \geq m$ y $k \geq 5$. $\blacksquare$

Gramatica

Solucion

Analisis del lenguaje

El lenguaje es $L = \{a^n b^m c^k \mid n \geq m \land k \geq 5\}$.

Podemos descomponer las restricciones:

1. $n \geq m$: Esto significa $n = m + j$ para algun $j \geq 0$. Necesitamos $m$ pares $ab$ y $j$ $a$‘s adicionales al inicio.
2. $k \geq 5$: Al menos 5 $c$‘s, mas cualquier cantidad adicional.

Gramatica

$$\begin{aligned} S &\to AB \\[4pt] A &\to aA \mid C \\ C &\to aCb \mid \varepsilon \\[4pt] B &\to cccccD \\ D &\to cD \mid \varepsilon \end{aligned}$$

Explicacion

• $S \to AB$ separa la generacion de la parte $a^n b^m$ (con $n \geq m$) de la parte $c^k$ (con $k \geq 5$).
• $A \to aA \mid C$: genera $j$ $a$‘s adicionales ($j \geq 0$) antes de pasar a $C$.
• $C \to aCb \mid \varepsilon$: genera $a^m b^m$ para algun $m \geq 0$, emparejando $a$‘s con $b$‘s.
• $B \to cccccD$: genera las 5 $c$‘s obligatorias.
• $D \to cD \mid \varepsilon$: genera $c$‘s adicionales.

Asi, la cadena generada tiene la forma $a^j a^m b^m c^5 c^l = a^{j+m} b^m c^{5+l}$ donde:

• $n = j + m \geq m$ ya que $j \geq 0$. $\checkmark$
• $k = 5 + l \geq 5$ ya que $l \geq 0$. $\checkmark$

Verificacion con ejemplos

Cadena $ccccc$ ($n=0, m=0, k=5$):

$S \Rightarrow AB \Rightarrow CB \Rightarrow B \Rightarrow cccccD \Rightarrow ccccc$

$\checkmark$ ($0 \geq 0$ y $5 \geq 5$)

Cadena $aabccccc$ ($n=2, m=1, k=5$):

$S \Rightarrow AB \Rightarrow aAB \Rightarrow aCB \Rightarrow aaCbB \Rightarrow aabB \Rightarrow aabcccccD \Rightarrow aabccccc$

$\checkmark$ ($2 \geq 1$ y $5 \geq 5$)

Cadena $aabbcccccc$ ($n=2, m=2, k=6$):

$S \Rightarrow AB \Rightarrow CB \Rightarrow aCbB \Rightarrow aaCbbB \Rightarrow aabbB \Rightarrow aabbcccccD \Rightarrow aabbcccccD \Rightarrow aabbcccccc$

$\checkmark$ ($2 \geq 2$ y $6 \geq 5$)