Suppose the alphabet is $ {a, b } $and you have a forbidden word $ aa $, Suppose we try to generate a word of length 3. The first two letters are evenly distributed $ ab, ba, bb $, Therefore, the first letter has the following distribution: $ a $ with probability $ 1/3 $. $ b $ with probability $ 2/3 $, In contrast, the allowed words

$$

aba, abb, bab, bba, bbb.

$$

So the first letter should have the distribution $ a $ with probability $ 2/5 $. $ b $ with probability $ 3/5 $,

Here is an algorithm that works. Create a DFA (or UFA) for your language. For every state $ q $With dynamic programming, you can count how many words are long $ m $ are accepted when the machine is restarted $ q $, Let us denote this $ c (q, m) $,

The correct distribution of the first letter $ sigma_1 $ from a word of length $ n $ is in the language

$$

Pr ( sigma_1 = sigma) = frac {c ( delta (q_0, sigma), n-1)} {c (q_0, n)}.

$$

Quite generally in the face of the first $ ell $ letters $ sigma_1 ldots sigma_ ell $The following letter has the distribution

$$

Pr ( sigma_ { ell + 1} = sigma mid sigma_1 ldots sigma_ ell) = frac {c ( delta (q_0, sigma_1 ldots sigma_ ell sigma), n – ell-1)} {c ( delta (q_0, sigma_1 ldots sigma_ ell), n- ell)}.

$$

If you ignore the cost of arithmetic, you can roughly implement this scheme $ O (| Q | n) $, Where $ Q $ is the set of states or in $ O (| Sigma | n ^ 2) $, (The former assuming that $ | Q | = Omega (| Sigma |) $.)

As an example, consider the above counter example. We construct a two-state DFA (we can omit the sink state to get a UFA) $ q_0, q_1 $, The transition function is $ Delta (q_0, a) = q_1 $. $ Delta (q_0, b) = q_0 $. $ Delta (q_1, b) = q_0 $, The relevant values of $ c $ are

$$

begin {array} {c | cc}

n & c (q_0, n) & c (q_1, n) \ hline

0 & 1 & 1 \

1 & 2 & 1 \

2 & 3 & 2 \

3 & 5 & 3

end {array}

$$

These are calculated by the repetitions $ c (q_0, n) = c (q_0, n-1) + c (q_1, n-1) $ and $ c (q_1, n) = c (q_0, n-1) $with basic housing $ c (q, 0) = 1 $,

Since $ Delta (q_0, a) = q_1 $ and $ Delta (q_0, b) = q_0 $we see that (eg $ n = 3 $) $ Pr ( sigma_1 = a) = c (q_1,2) / c (q_0,3) = 2/5 $ and $ Pr ( sigma_1 = b) = c (q_0,2) / c (q_0,3) = 3/5 $,