En un alfabeto $\{0, 1\}$, ¿cuál es la función generadora para el conjunto de cadenas que no contienen $00100$ como una subcadena? He probado el conjunto de cadenas que no contienen $00100$ en términos de encadenamientos de otros sistemas de escritura (aquí es donde me sale pegado) y luego usar el lema del producto. ¿Cualquier sugerencia sobre cómo puedo escribirlo?
Respuestas
¿Demasiados anuncios?He encontrado una alternativa y sorprendentemente simple patrón de sus secuencias, que permite calcular la función de generación de una forma mucho más sencilla.
Considerar todos los bloques que terminan con $1$. Hay dos tipos de bloques: $A$ es $1$ o $01$, e $B$$000^*1$, es decir, al menos dos ceros seguidos por $1$ ($^*$ significa repetir cero o más veces).
Ahora, cada secuencia de $0$'s y $1's$ puede ser construido como $\{A;B\}^*0^*$. Que se nos repita los bloques que termina en $1$ y añadir cualquier número de $0$'s al final. La secuencia resultante no contenga $X=00100$ si se cumplen dos condiciones: no tenemos dos bloques consecutivos $B$, es decir, $BB$ está prohibido, y si terminamos el repetitivos parte con $B$ a continuación, el cero-cola no puede contener más de una $0$.
En general,
$$A^*(BAA^*)^*\{B;B0;0^*\}$$
Las funciones de generación (tenga en cuenta que si $Z$ tiene la generación de la función$z(x)$, $Z^*$ tiene la generación de la función $\frac{1}{1-z(x)}$):
$$A=\{1;01\}:a(x)=x+x^2$$
$$B=000^*1:b(x)=\frac{x^3}{1-x}$$
Y por el producto de lema, para $A^*(BAA^*)^*\{B;B0;0^*\}$ hemos
$$f(x)=\frac{1}{1-x-x^2}\frac{1}{1-\frac{x^4(1+x)}{(1-x)}\cdot\frac{1}{1-x-x^2}}\cdot\left(\frac{x^3}{1-x}+\frac{x^4}{1-x}+\frac{1}{1-x}\right)=$$
$$=\frac{1+x^3+x^4}{1-2x+x^3-x^4-x^5}.$$
Nota, que $f(x)=1+2x+4x^2+8x^3+16x^4+31x^5+60x^6+116x^7+225x^8+437x^9+849x^{10}+\ldots$, y, de hecho, debemos tener $n_l$ secuencias de longitud $l$ donde $n_l=2^l$ $l\le 4$, $n_l=2^l-(l-4)2^{l-5}$ para $5\le l\le 7$, $n_l=2^l-(l-4)2^{l-5}+\sum_{k=1}^{l-7}k2^{k-1}$ para $8\le l\le 10$, etc.
Vadim
Puntos
3528
Para generar todas las secuencias utilice el siguiente patrón (una explicación de la siguiente manera):
$$B^*E=\{1;01;000^*1\{1;01\}\}^*\{0^*;000^*\{1;10\}\}$$
donde $^*$ significa repetir el patrón anterior, el número o $\{\}$-expresión de cero o más veces. Así, por ejemplo, $000^*$ significa que repita $0$ al menos dos veces, y $\{\}^*$ significa repetir el patrón dentro de los corchetes cero o más veces.
Las funciones de generación son:
$$\Phi_B(x)=x+x^2+(x^4+x^5+\ldots)+(x^5+x^6+\ldots)=x+x^2+x^4+\frac{2x^5}{1-x}$$ $$\Phi_E(x)=(1+x+x^2+\ldots)+(x^3+x^4+\ldots)+(x^4+x^5+\ldots)=1+x+x^2+2x^3+\frac{3x^4}{1-x}$$
Ya podemos repetir $B$ cualquier número de veces, la generación de la función que se busca es la
$$\Phi(x)=\sum_{k=0}^{\infty}\Phi_B^k(x)\cdot\Phi_E(x)=\frac{\Phi_E(x)}{1-\Phi_B(x)}=\frac{1+x^3+x^4}{1-2x+x^3-x^4-x^5}$$
Edit: Un simple no-explicación técnica del patrón.
Supongamos que queremos representar cualquier posible secuencia que no contienen la cadena de $X=00100$ como una repetición de algunos patrón de $B$. Luego lo que a la larga genera por $B$, se debe asegurar que: a) no contener $X$, b) $X$ no puede ser generado por el final de esta larga y el comienzo de la siguiente subsequence generado por $B$, y también, por supuesto, necesitamos c) que cada secuencia puede ser generado como la repetición de $B$.
Supongamos que $B$ puede empezar con cualquier secuencia de $0$'s y $1$'s. En este caso, para satisfacer b), $B$ no puede terminar con $0$ o $001$. Si termina con cualquier otra cosa, estamos seguros, para iniciar otra a $B$ con lo que queremos.
¿Cuál es el opuesto de no acabar en $0$ o $001$? El opuesto de esto es que el $B$ termina en $11$ o $101$ O es sólo una secuencia $1$ o $01$ (estos son todo subsecuencias generado por $B$).
Por lo tanto, si $B$ genera uno de los siguientes: $1$, $01$ o $\ldots11$, $\ldots101$, a continuación, se cumple b): se puede iniciar otra larga generado por $B$ sin tener miedo de que va a chocar con la anterior. Esto es lo que yo llamo el "seguro" de estado a continuación.
Ahora, necesitamos $B^*$ a generar todas las secuencias que no contengan $X$. Los dos primeros a $1$ $01$ están muy bien y que cubren todas las secuencias de partida, ya sea con $1$ o $01$: $1B^*$ y $01B^*$. ¿Qué es la izquierda: subsecuencias de partida con $00$. Echemos un vistazo a la primera $1$ después $00$. Por lo tanto, tenemos $000^*1$. Debe ser seguido por otro $1$ o $01$. Y, por lo tanto, va a terminar con $11$ o $101$, lo que pondrá fin a la larga generado por $B$.
En general, $B$ es uno de los siguientes: $1$, $01$, $000^*11$ o $000^*101$. Esto va a generar todas las posibles subsecuencias de un lugar "seguro" a otro, y dos de estas secuencias nunca chocan.
Ahora, para finalizar la secuencia, podemos comenzar a generar un subsequence de acuerdo a $B$, pero detener en cualquier punto. Este parcial subsequence $E$ $0^*$ o $000^*1$ o $000^*10$.
Inicial, más explicación formal.
Considere la posibilidad de generar la secuencia de izquierda a derecha. Si queremos representar la secuencia como $B^*$ donde $B$ es un patrón común, a continuación, $B$ debe satisfacer dos criterios: todas las secuencias generadas por $B$ son correctos (no contienen la prohibición de la cadena) y no termina de un $B$ más que el comienzo de otro, genera la prohibición de la cadena.
Vamos a considerar en 5 estados: $s,s0,s00,s001,s0010$. El estado $s$ es la "seguridad" del estado, cuando cada secuencia correcta, a partir de este punto, con lo que tenemos hasta ahora, no genera el prohibido cadena. Obviamente, queremos que cualquier secuencia generada por $B$ para terminar en la caja de seguridad del estado, de modo que lo que se genera después de que el punto de no chocar con lo que ya tenemos. Los estados $s0$ $s00$ significa que hemos añadido uno y más de una $0$ a la seguridad del estado, respectivamente. Por último, los estados $s001$ $s0010$ significa que hemos añadido a $1$ $10$ para el estado $s00$, respectivamente.
Aquí está el diagrama de todos los posibles movimientos de la caja de seguridad del estado. Una vez que alcanzamos el estado de seguridad de nuevo, con esto termina nuestro modelo:
$$\begin{array}{} s & +0\rightarrow & s0 & +0\rightarrow & s00 & +0\rightarrow & s00 & & & & \\ & & & & & +1\rightarrow & s001 & +0\rightarrow & s0010 & +1\rightarrow & s \\ & & & & & & & +1\rightarrow & s & & \\ & & & +1\rightarrow & s & & & & & & \\ & +1\rightarrow & s & & & & & & & & \end{array}$$
Por lo tanto, $B=\{1;01;000^*1\{1;01\}\}$. Ahora, desde la secuencia final en el estado que no es seguro, tenemos que añadir el patrón de $E$ que es cualquier secuencia de acuerdo con el diagrama de arriba, que no termina en la caja de seguridad del estado, es decir,$E=\{0^*;000^*\{1;10\}\}$.
