Función generadora del conjunto de $w$ -palabras libres.

Question

Supongamos que $X$ es un alfabeto y $w \in X^n$ es una palabra sobre ella. Considere un conjunto $P$ de $w$ -palabras libres sobre $X$ (una palabra se llama $w$ -libre si no contiene $w$ como subpalabra). Quiero escribir una función generadora para $P$ (por la longitud). Estoy tratando de escribir algún tipo de relación de recurrencia considerando el conjunto $Q$ de palabras $u$ en $X$ tal que $u$ termina con $w$ y $u$ no contiene $w$ como subpalabra en cualquier otra posición. Pero está claro que si tomamos una palabra $a \in P$ no implica que $aw \in P$ por lo que dicha relación de recurrencia depende en gran medida de $w$ . ¿Puede sugerir, por favor, si existe una forma de derivar la función generadora? Cualquier referencia será también apreciada.

Answer 1

Te recomiendo que mires el método de cluster de Goulden-Jackson. Ver, por ejemplo, esta respuesta que contiene referencias.