Palabras de $\{0,1,2\}$ con restricciones que no sean tan fáciles de acomodar.

Question

Asumimos un ternario alfabeto $V=\{0,1,2\}$ y están buscando una generación de la función que describe el número de palabras de $V^*$ el cumplimiento de ciertas restricciones. Las palabras que estoy interesado en hacer que no contienen pistas de longitud $k+1$ ( $k\geq 1$ ) y contienen la cadena de caracteres $1^k2$, es decir, de una carrera de a $1$ de la longitud de la $k$, seguido por $2$.

Soy consciente de las dos técnicas que son útiles para atacar a preguntas de este tipo.

Smirnow palabras: Uno de ellos se basa en Smirnov palabras, que son palabras sin consecutivos iguales letras. Ver, por ejemplo, ejemplo III.24 en la Analítica de la Combinatoria por P. Flajolet y R. Sedgewick. La Smirnov palabras de tres letras del alfabeto $V$ están representados por la generación de la función $S(z)$ \begin{align*} S(z)=\left(1-\frac{3z}{1+z}\right)^{-1} \end{align*} Ya que estamos buscando palabras con un máximo de pistas de $0,1$ $2$ de la longitud de la $k$ sustituimos \begin{align*} z\rightarrow z+z^2+\cdots+z^k=z\frac{1-z^k}{1-z} \end{align*} Palabras que no contienen pistas de longitud $k+1$ puede por lo tanto obtiene como \begin{align*} \left(1-\frac{3z\frac{1-z^k}{1-z}}{1+z\frac{1-z^k}{1-z}}\right)^{-1}=\frac{1-z^{k+1}}{1-3z+2z^{k+1}} \end{align*}

$$ $$

El Goulden-Jackson Clúster Método muy bien presentado por J. Noonan y D. Zeilberger es predestinated si estamos buscando palabras que no está permitido que contienen las llamadas malas palabras. La aplicación de esta técnica es fácil encontrar una generación de función $T(z)$ que no contienen la palabra mala $1^k2$. De acuerdo a la fórmula de la página $7$ de los referidos de papel obtenemos \begin{align*} T(z)=\frac{1}{1-3z+z^{k+1}} \end{align*} La generación de la función $S(z)$ también puede ser fácilmente obtenida con este método. De nuevo de acuerdo a la fórmula de la página $7$ tenemos \begin{align*} S(z)=\frac{1}{1-3z+3\frac{z^{k+1}(1-z)}{1-z^{k+1}}}=\frac{1-z^{k+1}}{1-3z+2z^{k+1}} \end{align*}

Tengo problemas para derivar una generación de función que sigue el combinado requisitos de conteo de palabras que no contienen palabras con las carreras de la longitud de la $k+1$, pero contienen la subcadena $1^k2$. Alguna idea?

Nota: Esta pregunta corresponde a la segunda parte de esta pregunta.

Answer 1

Afortunadamente con este problema podemos utilizar una descomposición como con las expresiones regulares que se vuelve menos y menos útiles como el la complejidad de la lengua crece.

Primero se introduce el lenguaje de las cadenas de ceros y de dos en dos tener de largo plazo en la mayoría de las $k$ comenzando con un fijo de dígitos

$$H(z) = z\frac{1-z^k}{1-z} \sum_{q\ge 0} \left(z\frac{1-z^k}{1-z} z\frac{1-z^k}{1-z} \right)^q \frac{1-z^{k+1}}{1-z}.$$

Para la principal generadora de la función de inicio de la cadena con una cadena de ceros o de dos en dos o la cadena vacía, siga este por un lazo anclado en bloques de unos y finalmente agregar una posible cadena de unos en la final a obtener

$$G(z) = (1+2H(z)) \sum_{q\ge 0} \left(z\frac{1-z^{k-1}}{1-z} 2 H(z) + z^k (1+v) H(z)\right)^q \frac{1-z^{k+1}}{1-z}.$$

Aquí hemos utilizado la $v$ que marca la transición crítica a $1^k 2.$ Para simplificar este inicio con $H(z)$ que los rendimientos de

$$H(z) = z\frac{1-z^k}{1-z} \frac{1}{1-z^2 (1-z^k)^2/(1-z)^2} \frac{1-z^{k+1}}{1-z} \\ = z \frac{1-z^{k} z^{k+1}+z^{2k+1}} {1-2z+2z^{k+2} z^{2k+2}}.$$

La simplificación en $G(z)$ produce

$$G(z) = \frac{(1+2H(z))(1-z^{k+1})}{1-H(z)(2z-2z^k+z^k(1+v)(1-z))/(1-z)} \frac{1}{1-z} \\ = \frac{(1+2H(z))(1-z^{k+1})}{1-z-H(z)(2z-2z^k+z^k(1+v)(1-z))}.$$

El lector se instó a realizar otras acciones de simplificación en este. Continuando buscamos la generación de la función

$$Q(z) = \left. G(z) - G(z, 0) \right|_{v=1}.$$

Este rendimientos

$$P(z) = \frac{(1+2H(z))(1-z^{k+1})}{1-z-H(z)(2z-2z^{k+1})} - \frac{(1+2H(z))(1-z^{k+1})}{1-z-H(z)(2z-z^k-z^{k+1})}.$$

E. g. obtenemos para $k=3$ el siguiente resultado: $$Q_3(z) = {\frac { \left( {z}^{2}+z+1 \right) {z}^{4} \left( z+1 \right) \left( {z}^{2}+1 \right) }{ \left( {z}^{6}+3\,{z}^ {5}+5\,{z}^{4}+5\,{z}^{3}+3\,{z}^{2}+z-1 \right) \left( 2\, {z}^{3}+2\,{z}^{2}+2\,z-1 \right) }}.$$

Comenzando en $n=1$ este rendimientos de la secuencia

$$0, 0, 0, 1, 5, 21, 80, 287, 993, 3347, 11067, 36055, \\ 116089, 370222, 1171353,\ldots$$

No pondremos $Q_4(z)$ aquí. La secuencia es $$0, 0, 0, 0, 1, 5, 21, 81, 296, 1043, 3585, 12095, \\ 40221, 132225, 430633, 1391623,\ldots$$

El uso de $Q_5(z)$ obtenemos $$0, 0, 0, 0, 0, 1, 5, 21, 81, 297, 1052, 3635, 12333, \\ 41255, 136449, 447147, 1454091,\ldots$$

Estas secuencias han sido verificados con un total de enumeración de rutina que se incluye con el Arce de código para este problema, que ahora presente. El total de la enumeración de rutina es práctico para hasta alrededor de $n=11.$

RL :=
proc(n, k)
 opción de recordar;
 local ind, d, pos, cur, corre, corre, res;

 res := 0;

 para la ind de 3^n 2*3^n-1 hacer
 d := convert(ind, base, 3);

 cur := -1; pos := 1;
 ejecutar := []; pistas := [];


 mientras pos <= n hacer
 si d[pos] <> cur entonces
 si nops(ejecutar) > 0, entonces
 pistas := [op(corre), ejecutar];
fi;

 cur := d[pos];
 ejecutar := [cur];
otra cosa
 ejecutar := [op(ejecutar), cur];
fi;

 pos := pos + 1;
od;

 pistas := [op(corre), ejecutar];

 si max(map(r->nops(r), se ejecuta)) <= k entonces
 pos a nops(carreras) -1 ¿
 ejecutar := ejecuta[pos];

 si ejecuta[1] = 1 y nops(ejecutar) = k
 y corre[pos+1][1] = 2 entonces
break;
fi;
od;

 si pos < nops(corre), a continuación,
 res := res + 1;
fi;
fi;
od;

res;
end;

RNG := (minv, maxv) -> add(z^q, q=minv..maxv);

H :=
proc(k)
RNG(1,k)*
 sum((RNG(1,k)*RNG(1,k))^q, q=0..infinity)
*Generador de números aleatorios(0,k)
end;


H2 := 
proc(k) 
z*(1-z^k-z^(k+1)+z^(2*k+1))
/(1-2*z+2*z^(k+2)-z^(2*k+2));
end;

G := 
proc(k)
(1+2*H(k))
*suma((RNG(1,k-1)*2*H(k)
 + z^k*(1+v)*H(k))^q,
q=0..infinity)
 *Generador de números aleatorios(0, k);
end;

G2 := 
proc(k)
(1+2*H2(k))*(1-z^(k+1))
/(1-z-H2(k)*(2*z 2*z^k+z^k*(1+v)*(1-z)));
end;

Q :=
proc(k)
 subs(v=1, G(k)-subs(v=0, G(k)));
end;

P2 :=
proc(k)
(1+2*H2(k))*(1-z^(k+1))
/(1-z-H2(k)*(2*z 2*z^(k+1)))
 - (1+2*H2(k))*(1-z^(k+1))
/(1-z-H2(k)*(2*z-z^k-z^(k+1)));
end;

V :=
proc(n, k)
 opción de recordar;

 coeftayl(Q2(k), z=0, n);
end;

Adenda. Observar que el segmento inicial de todas estas secuencias de hecho, es el mismo. Podemos manualmente evaluar el caso de $n=p$ donde $k+1\le p\le 2k.$ No es el caso de que el $1^k 2$ bloque se encuentra a la derecha en el comienzo (posición $q=0$). Podemos elegir libremente el las letras a la derecha de la cuadra que da una contribución de $3^{p-k-1}.$ (Tenga en cuenta que este deja de funcionar cuando se $p\gt 2k$ porque prohibido ejecuta puede aparecer a la derecha del bloque.) Si el bloque es en la posición $q$ donde $1\le q\le p-k-1$ debemos de poner un cero o una de dos justo a la izquierda del bloque y se puede elegir libremente el resto de cartas para una contribución de $2\times 3^{p-1} \times 3^{p-(k+1)-q} = 2 \times 3^{p-k-2}.$ La recogida de esto en una fórmula obtenemos

$$3^{p-k-1} + 2 \sum_{q=1}^{p-k-1} 3^{p-1} 3^{p-(k+1)-q} = 3^{p-k-1} + 2 (p-k-1) 3^{p-k-2}.$$

Vemos que esto sólo depende de la diferencia de $m = p-k$ es decir

$$3^{m-1} + 2 (m-1) 3^{m-2} = (2m+1) 3^{m-2}$$

así que, de hecho tenemos el mismo segmento inicial para todos los $k.$ La secuencia aquí es

$$1, 5, 21, 81, 297, 1053, 3645, 12393, 41553, 137781, \\ 452709, 1476225, 4782969,\ldots$$

que es OEIS A081038.

Answer 2

No hay un método general para el cálculo de la generación de la función de cualquier lenguaje regular $L$. En su caso, $L$$V^* - V^*(0^{k+1} + 1^{k+1} + 2^{k+1} + 1^k)V^*$, si he entendido correctamente.

El método general funciona de la siguiente manera.

Paso 1. Calcular el mínimo autómata determinista de $L$. En su caso, este autómata ha $3k+1$ estados, si no me equivoco.

Paso 2. Calcular una inequívoca expresión regular para $L$. Recordemos que una expresión regular $R$ es ambigua si, para cada $u \in L(R)$, sólo hay un $R$-parse de $u$. En otras palabras, un sindicato es ambigua si y sólo si es distinto, un producto de $K = K_0K_1 \cdots K_r$ es ambigua si cada palabra de $K$ tiene una única factorización como $u = u_0u_1 \cdots u_r$, con $u_0 \in K_0$, ..., $u_r \in K_r$ y $K^*$ es ambigua si el monoid $K^*$ es libre de base $K$.

Una forma estándar para obtener una inequívoca expresión regular es el uso de Kleene del algoritmo.

Paso 3. La generación de la función $s(L)$ $L$ ahora pueden ser calculados a partir de la inequívoca expresión regular utilizando las reglas de $s(u) = z^{|u|}$ donde $|u|$ denota la longitud de una palabra $u$, $s(L_0 + L_1) = s(L_0) + s(L_1)$, $s(L_0L_1) = s(L_0)s(L_1)$ y $s(L^*) = (1-s(L))^*$. Por ejemplo, si $L = (a + ba + bba + bbb)^*$ (una inequívoca expresión), se obtiene $s(a) = z$, $s(ba) = z^2$, $s(bba) = s(bbb) = z^3$, y, finalmente, $$ s(L) = \frac{1}{1-(z+z^2+2z^3)} $$ Volviendo a tu caso, me sugieren para tratar los casos de $k=0, 1$ $2$ a mano o con la ayuda de un ordenador y, a continuación, supongo que la fórmula general para cualquier $k$ antes de intentar una más formal de la prueba.

Answer 3

Nota: El instructivo de respuesta de @MarkoRiedel valía la pena un poco de análisis en profundidad. El resultado de este análisis sirve aquí como información complementaria. Tenemos en cuenta su enfoque en algunos detalles, analizar la conexión con Smirnov palabras y encontrar algunas representaciones simplificadas.

La esencia de su respuesta, es una inteligente de dos etapas de la descomposición de la lengua en consideración. Empezamos con una similar de descomposición en un simple contexto respecto a binario palabras.

Binario palabras

No binario vacío de palabras construido a partir de un alfabeto $\{0,2\}$ y que comienzan con la letra $0$ admite siguiente caracterización. Se descompone en bloques, cada bloque de partida con $2$ y seguido por cero o más $0$s. La palabra empieza con una o más $0$s. Aquí está un ejemplo con $|$, lo que indica que el bloque de descomposición.

\begin{align*} 000|2|20|200|20|20|2|2000|200|2|2|2|200 \end{align*}

El lenguaje de $\mathcal{B}_0$ descripción de estas palabras es

\begin{align*} \mathcal{B}_0=00^*\left(20^*\right)^* \end{align*} con estrellas, $^*$ denota cero o más ocurrencias. La correspondiente función es la generación de \begin{align*} B(z)&=\frac{z}{1-z}\sum_{q=0}^{\infty}\left(\frac{z}{1-z}\right)^q\\ &=\frac{z}{1-z}\frac{1}{1-\frac{z}{1-z}}\\ &=\frac{z}{1-2z}\\ &=z+2z^2+4z^3+8z^4+16z^5+32z^6+O(z^7) \end{align*} Ahora vamos a intercambiar el papel de $0$ $2$ para obtener el idioma $\mathcal{B}_2$ de palabras que comienzan con $2$. \begin{align*} 222|0|02|022|02|02|0|0222|022|0|0|0|022 \end{align*}

El lenguaje de $\mathcal{B}_2$ descripción de estas palabras es

\begin{align*} \mathcal{B}_2=22^*\left(02^*\right)^* \end{align*} y la correspondiente generación de la función es la misma que antes \begin{align*} B(z)=\frac{z}{1-2z} \end{align*} Observar que todos los binarios de palabras puede ser descrito como \begin{align*} \varepsilon\cup\mathcal{B}_0\cup\mathcal{B}_2\tag{1} \end{align*} que se compone la palabra vacía o una palabra binaria de partida con $0$ o empezando $2$. La generación de la función, en consecuencia, \begin{align*} 1+\frac{2z}{1-2z}&=\frac{1}{1-2z}\\ &=1+2z+4z^2+8z^3+16z^4+32z^5+O(z^6) \end{align*}

Ahora estamos bien preparados para el primer paso en el enfoque de dos pasos de Marko la respuesta y se derivan $H(z)$.

Binario Smirnov palabras:

Volvemos a usar el alfabeto binario $\{0,2\}$. En este momento estamos buscando palabras que tienen las carreras de la longitud máxima de la $k$. Utilizamos una descomposición similar como se hizo para el idioma $\mathcal{B}_0$ por encima.

Consideramos cero o más bloques, cada bloque de partida con $2$ y seguido por al menos uno o más $0$s. Las palabras que empiezan con al menos un cero y el final con cero o más $2$s. El general de restricción de estas palabras es que la máxima longitud es de $k$. Esto suena complicado, pero cuando nos fijamos en el lenguaje formal de la descripción, vamos a denotar es $\mathcal{H}_0$, no es tan difícil. \begin{align*} \mathcal{H}_0=00^{<k}\left(22^{<k}00^{<k}\right)^*2^{<{k+1}}\tag{2} \end{align*}

El patrón de $00^{<k}$ denota al menos una $0$, seguido por cero hasta el $k-1$ ceros. De esta manera podemos crear las cadenas no vacías de $0$ con la longitud de ejecución $\leq k$.

El patrón de $\left(22^{<k}00^{<k}\right)^*$ indica que el bloque de descomposición.

La correspondiente generación de función $H(z)$ para el idioma $\mathcal{H}_0$ puede ser traducido directamente de (2)
\begin{align*} H(z)&=z\frac{1-z^k}{1-z}\sum_{q=0}^{\infty}\left(z\frac{1-z^k}{1-z}\right)^{2q}\frac{1-z^{k+1}}{1-z}\\ &=z\frac{1-z^k}{1-z}\cdot\frac{1}{1-\left(z\frac{1-z^k}{1-z}\right)^2}\cdot\frac{1-z^{k+1}}{1-z}\\ &=z\frac{1-z^k-z^{k+1}+z^{2k+1}}{1-2z+2z^{k+2}-z^{2k+2}}\tag{3}\\ &=z\frac{1-z^k}{1-2z+z^{k+1}} \end{align*}

Tenga en cuenta que la representación (3) se expresa como $H(z)$ en el Marko de la respuesta. Puede ser más simplificado, ya que el numerador y el denominador de ambos contienen el factor de $1-z^{k+1}$.

Como hicimos en la primera sección, el intercambio de los roles de $0$$2$, definir el idioma \begin{align*} \mathcal{H}_2=22^{<k}\left(00^{<k}22^{<k}\right)^*0^{<{k+1}} \end{align*} con la correspondiente generación de la serie de $H(z)$ \begin{align*} H(z)=z\frac{1-z^k}{1-2z+z^{k+1}} \end{align*}

Si consideramos el lenguaje consistente en la palabra vacía junto con $\mathcal{H}_0$ $\mathcal{H}_2$ \begin{align*} \varepsilon\cup\mathcal{H}_0\cup\mathcal{H}_2\tag{4} \end{align*} obtenemos todos los binarios palabras tener la longitud de ejecución $\leq k$. De hecho, la generación de la función es \begin{align*} 1+2H(z)&=1+2z\frac{1-z^k}{1-2z+z^{k+1}}\\ &=\frac{1-z^{k+1}}{1-2z+z^{k+1}} \end{align*}

El binario Smirnov palabras $B_2(z)$ son las palabras sobre un alfabeto binario sin consecutivos igualdad de letras, es decir, con las carreras de la máxima longitud de $1$. Su generación de función se especifica como (ver la pregunta anterior) \begin{align*} B_2(z)&=\left(1-\frac{2z}{1+z}\right)^{-1}=\frac{1+z}{1-z}\\ &=1+2z+2z^2+2z^3+2z^4+2z^5+O(z^6) \end{align*} La generación de la función para todos los binarios de palabras que tienen las carreras de la longitud de la $\leq k$ es, en consecuencia, \begin{align*} B_2\left(z\frac{1-z^{k}}{1-z}\right)&=\frac{1+z\frac{1-z^{k}}{1-z}}{1-z\frac{1-z^{k}}{1-z}}\\ &=\frac{1-z^{k+1}}{1-2z+z^{k+1}}\\ &=1+2H(z) \end{align*} De ello se sigue, que la descomposición (4) es, de hecho, el conjunto de todos los binarios de palabras que tienen la longitud de ejecución $\leq k$.

Vamos a echar un breve vistazo a los binarios de palabras con el máximo de ejecución de las longitudes $k=2,3,4$. \begin{align*} B_2\left(z\frac{1-z^{3}}{1-z}\right)&=1+2z+4z^2+6z^3+10z^4+16z^5+O(z^6)\\ B_2\left(z\frac{1-z^{4}}{1-z}\right)&=1+2z+4z^2+8z^3+14z^4+26z^5+O(z^6)\\ B_2\left(z\frac{1-z^{5}}{1-z}\right)&=1+2z+4z^2+8z^3+16z^4+30z^5+O(z^6)\\ \end{align*}

Tenga en cuenta que el factor de $1+2H(z)$ también es parte de la generación de la función $G(z)$ en Marko Riedels respuesta, que ahora vamos a derivar. La idea es usar el $1+2H(z)$, es decir, la lengua de todos los binarios de palabras con la máxima longitud de $k$ como bloques de construcción a la hora de generar ternario palabras con la máxima longitud de $k$.

Ternario Smirnov palabras:

Recordar que estamos buscando ternario palabras sobre el alfabeto $\{0,1,2\}$ tener la máxima longitud de $\leq k$ y cada aparición de $1^k$ tiene que ser seguido por la letra"$2$. Comenzamos por crear todos los ternario palabras que tener la máxima longitud de $\leq k$. La descomposición en $\mathcal{H}_0$$\mathcal{H}_2$, a continuación, nos permite seleccionar con precisión las palabras con las $1^k2$ y evitar palabras con $1^k0$.

Consideramos los siguientes idiomas \begin{align*} \left(\varepsilon+\mathcal{H}_0+\mathcal{H}_2\right)\left(11^{<k}\left(\mathcal{H}_0+\mathcal{H}_2\right)\right)^*1^{<k+1}\tag{5} \end{align*} comenzando con un binario, posiblemente cadena vacía construida desde el alfabeto $\{0,2\}$, seguido por cero o más bloques cada bloque de inicio con al menos un $1$, seguido por una cadena no vacía construida desde el alfabeto $\{0,2\}$. Una palabra puede terminar con cero o más $1$s y la longitud de cada letra es $\leq k$. La correspondiente función es la generación de \begin{align*} G(z)&=\left(1+2H(z)\right)\sum_{q=0}^\infty\left(z\frac{1-z^k}{1-z}2H(z)\right)^q\frac{1-z^{k+1}}{1-z}\tag{6}\\ &=\left(1+2H(z)\right)\frac{1}{1-z\frac{1-z^k}{1-z}2H(z)}\frac{1-z^{k+1}}{1-z}\\ &=\frac{1-z^{k+1}}{1-2z+z^{k+1}}\frac{1}{1-z\frac{1-z^k}{1-z}2z\frac{1-z^k}{1-2z+z^{k+1}}}\frac{1-z^{k+1}}{1-z}\\ &=\frac{1-z^{k+1}}{1-3z+2z^{k+1}} \end{align*}

Tenga en cuenta que la representación (6) se expresa como $G(z)$ en el Marko de la respuesta con el marcador de $v=1$. Otra vez podemos derivar una conexión con Smirnov palabras.

El ternario Smirnov palabras $B_3(z)$ son las palabras de más de una de tres letras en el alfabeto sin consecutivos igualdad de letras, es decir, con las carreras de la máxima longitud de $1$. Su generación de función se especifica como (ver la pregunta anterior) \begin{align*} B_3(z)&=\left(1-\frac{3z}{1+z}\right)^{-1}=\frac{1+z}{1-2z}\\ &=1+3z+6z^2+12z^3+24z^4+48z^5+O(z^6) \end{align*} La generación de la función para todos los ternario palabras que tienen las carreras de la longitud de la $\leq k$ es, en consecuencia, \begin{align*} B_3\left(z\frac{1-z^{k}}{1-z}\right)&=\frac{1+z\frac{1-z^{k}}{1-z}}{1-2z\frac{1-z^{k}}{1-z}}\\ &=\frac{1-z^{k+1}}{1-3z+2z^{k+1}}\\ &=G(z) \end{align*} De ello se sigue, que la descomposición (5) es, de hecho, el conjunto de todos los ternario palabras que tienen la longitud de ejecución $\leq k$.

Vamos a echar un breve vistazo a la ternario palabras con el máximo de ejecución de las longitudes $k=2,3,4$. \begin{align*} B_3\left(z\frac{1-z^{3}}{1-z}\right)&=1+3z+9z^2+24z^3+66z^4+180z^5+O(z^6)\\ B_3\left(z\frac{1-z^{4}}{1-z}\right)&=1+3z+9z^2+27z^3+78z^4+228z^5+O(z^6)\\ B_3\left(z\frac{1-z^{5}}{1-z}\right)&=1+3z+9z^2+27z^3+81z^4+240z^5+O(z^6)\\ \end{align*}

Paso Final: Las palabras, con el patrón de $1^k2$

El último paso es aislar las palabras de (5), los cuales contienen $1^k2$ y no de otras carreras de la $1$ de la longitud de la $k$. Debido a la inteligente descomposición se puede identificar fácilmente el idioma. Empezando por el idioma en (5) obtenemos \begin{align*} \left(\varepsilon\right.&\left.+\mathcal{H}_0+\mathcal{H}_2\right)\left(11^{<k}\left(\mathcal{H}_0+\mathcal{H}_2\right)\right)^*1^{<k+1}\\ &=\left(\varepsilon+\mathcal{H}_0+\mathcal{H}_2\right)\left(11^{<k-1}\left(\mathcal{H}_0+\mathcal{H}_2\right) +1^k\left(\mathcal{H}_0+\mathcal{H}_2\right)\right)^*\left(1^{<k}+1^k\right)\tag{7} \end{align*} A partir de la representación (7) vemos que tenemos que saltar las cuerdas $1^k\mathcal{H}_0$ en el bloque y el final de la cadena de $1^k$. Nosotros para obtener el idioma deseado \begin{align*} \left(\varepsilon+\mathcal{H}_0+\mathcal{H}_2\right)\left(11^{<k-1}\left(\mathcal{H}_0+\mathcal{H}_2\right) +1^k\mathcal{H}_2\right)^*1^{<k} \end{align*} La correspondiente generación de función $A_k(z)$ es \begin{align*} A_k(z)&=(1+2H(z))\sum_{q=0}^\infty\left(z\frac{1-z^{k-1}}{1-z}2H(z)+z^kH(z)\right)^q\frac{1-z^k}{1-z}\\ &=(1+2H(z)) \frac{1}{1-z\frac{1-z^{k-1}}{1-z}2H(z)+z^kH(z)}\cdot\frac{1-z^k}{1-z}\\ &=\frac{1-z^{k+1}}{1-2z+z^{k+1}}\cdot \frac{1}{1-z\frac{1-z^{k-1}}{1-z}2z\frac{1-z^k}{1-2z+z^{k+1}}-z^kz\frac{1-z^k}{1-2z+z^{k+1}}}\cdot\frac{1-z^k}{1-z}\\ &=\frac{\left(1-z^k\right)\left(1-z^{k+1}\right)}{1-3z+2z^{k+1}+2z^{k+2}-z^{2k+1}-z^{2k+2}} \end{align*}

La generación de esta función es un poco diferente a $Q(z)$ declaró por Marko. Una razón para ello es la diferente condición de parada de palabras, ya que aquí también podemos evitar la cadena de $1^k$ al final de las palabras.

Finalmente tomamos un breve vistazo a la ternario palabras con el máximo de ejecución de las longitudes $k=2,3,4$, conteniendo $1^k2$, pero en ninguna otra cadena con $1^k$.

\begin{align*} A_2(x)&=\frac{(1-z^2)(1-z^3)}{1-3z+2z^3+2z^4-z^5-z^6}\\ &=1+3z+8z^2+21z^3+55z^4+145z^5+O(z^6)\\ A_3(x)&=\frac{(1-z^3)(1-z^4)}{1-3z+2z^4+2z^5-z^7-z^8}\\ &=1+3z+9z^2+26z^3+75z^4+217z^5+O(z^6)\\ A_4(x)&=\frac{(1-z^4)(1-z^5)}{1-3z+2z^5+2z^6-z^9-z^10}\\ &=1+3z+8z^2+27z^3+80z^4+237z^5+O(z^6)\\ \end{align*}

Los coeficientes son verificados con el código fragmentos en R.