¿Cómo encuentro la función generadora para el conjunto $$ L de cadenas sobre $\{ 0 , 1 , 2\} $ que no contienen "$12$" como una subcadena?

Question

¿Cómo encuentro la función generadora para el conjunto $L$ de cadenas sobre $\{0, 1, 2\}$ que no contienen "$12$" como subcadena?

Estoy trabajando en encontrar la función generadora para el conjunto $L$ de cadenas compuestas por los caracteres $\{0, 1, 2\}$ que no incluyen la subcadena "$12$". Sea $a_{l, m, n}$ el número de cadenas en $L$ donde $l$ es la cantidad de $0$'s, $m$ es la cantidad de $1$'s, y $n$ es la cantidad de $2$'s. Necesito determinar la función generadora:

$$ G(x, y, z) = \sum_{l, m, n} a_{\ell, m, n} x^l y^m z^n.$$

Aquí está mi enfoque:

Caso $1$: Para las cadenas que empiezan con $0$, el resto de la cadena puede ser cualquier cadena válida, así que tenemos $$G_0(x, y, z) = x G(x, y, z).$$

Caso $2$: Para las cadenas que empiezan con $1$, entonces el siguiente caracter no puede ser un $2$, así que tenemos

$$G_1(x, y, z) = y(G_0(x, y, z) + G_1(x, y, z)).$$

Caso $3$: Para las cadenas que empiezan con $2$, el resto de la cadena puede ser cualquier cadena válida, así que tenemos

$$G_2(x, y, z) = zG(x, y, z).$$

Creo que así es cómo debería hacerse, terminamos combinando todos los casos. Sin embargo, estoy atascado aquí, ¿podría alguien proporcionar una explicación detallada o derivación de esta función generadora?

Answer 1

Para que tu análisis funcione, debemos contar la cadena vacía como una cadena válida.

Entonces, con tu notación, el resultado de tu análisis es (corrigiendo las cadenas que comienzan con "1": estas son o bien 1, o 10 ..., o 11 ...):

$$ \begin{eqnarray} G_0 &=&xG\\ G_1&=&y(1+G_0+G_1)\\ G_2&=&zG. \end{eqnarray} $$

Por lo tanto $$ \begin{eqnarray} G_0 &=&xG\\ (1-y)G_1&=&y(1+xG)\\ G_2&=&zG. \end{eqnarray} $$

Ahora, cada cadena válida es o bien vacía, o comienza con un 0 o un 1 o un 2. Por lo tanto $$ \begin{eqnarray} G&=&1+G_0+G_1+G_2\\ &=&1+xG+(1-y)^{-1}y(1+xG)+zG \end{eqnarray} $$ lo cual da $$ G(1-x-z-(1-y)^{-1}yx)=(1-y)^{-1}y+1=(1-y)^{-1} $$ o $$ \begin{eqnarray} G&=&(1-y)^{-1}(1-x-z-(1-y)^{-1}yx)^{-1}\\ &=&(1-x-y-z+yz)^{-1} \end{eqnarray} $$ si no he cometido ningún error tonto.