Come calcolare il numero di stringhe non valide dato un sistema di vincoli su alfabeto, lista nera e lunghezza della stringa

Question

Se ho il seguente sistema, mi chiedo come calcolare il numero di stringhe valide che contiene.

Il sistema è qualcosa di simile, che può avere variazioni arbitrarie.

• È costituito solo da un alfabeto $ Sigma $.
• Non può scrivere parole in un elenco di parole nella lista nera $ rho $.
• Non può avere più di $ n $ caratteri dello stesso tipo di fila.
• Ogni parola $ omega $ Genera non è più di $ m $ in lunghezza.

Quindi, ad esempio, potremmo avere questo sistema:

• $ Sigma = (a, b, c, d, e, f, g, h) $
• $ l = texttt {len} ( sigma) $
• $ rho = ( texttt {Bed}, texttt {fad}, texttt {papà}, texttt {bead}, texttt {deed}, texttt {fade}) $
• $ n = 3 $ (quindi non posso abbinare /aaaa|bbbb|cccc|dddd|eeee|ffff|gggg|hhhh/)
• $ m = 20 $

Supponiamo che abbiamo un generatore di numeri casuali, che utilizza un algoritmo Radix per convertirlo in una stringa usando i caratteri nell'alfabeto $ Sigma $. Il fatto è che questo generatore di numeri casuali potrebbe generare stringhe come le seguenti, che dobbiamo solo cadere e dimenticare, quindi provare a generarne un altro fino a quando non ne otteniamo uno che corrisponde ai vincoli. Non sono a conoscenza di un modo migliore per farlo, ma questo è al punto. Quindi potrebbe generare questi, che lo sono non valido.

afbcdeabeadbeaaaadaf
[bead and aaaa]
bedddddagheadfffeeee
[bed and dddd]

Quindi la domanda è: come faccio a calcolare quante stringhe non sono valide? So come calcolare le possibili stringhe dati i vincoli, cioè semplicemente:

$$ z = l^m = 8^{20} $$

Non so come calcolare il numero di stringhe che non sono valide, però, in modo generale (Quindi posso cambiare il valore di $ m $, $ n $, $ Sigma $, o $ rho $). Chiedendomi come formulare questo problema matematicamente o algoritmicamente in modo da poter capire che "ci sono X numero di stringhe non valide", e così posso calcolare:

$$ y = z - x $$

Per ottenere la quantità totale di possibili stringhe dati i vincoli.