computing maximal bit density over a FSM
First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00  where there is no max.  (The sup may not be attained.)  

Second, by "FSM" I assume you mean finite automaton.

Then I claim that either the maximum bit density is achieved by a word of length &lt; n, the number of states, or it is given by the maximum bit density over a loop of size at most n.
This means there are only finitely many cases to check, for each DFA.  Probably with a bit more work, one can get a polynomial-time algorithm out of it.

To see the claim, first note that if we compute the bit density of the sequence of words
$(u v^i w)_{i \geq 0}$ then this sequence is either (a) strictly increasing, (b) strictly decreasing, or (c) constant.  If the maximum bit density is attained and occurs at a shortest word x of length $&gt;= n$, by the pumping lemma we can write $x = uvw$ where $|uv| \leq n$.  In each case we get a contradiction.  In (a) there are words with higher bit density, like $uv^2w$; in (b) there is a word with higher bit density, namely $uw$, and in (c) there is a shorter word with the same bit density.  

The remaining case is that the maximum density is not attained.  A slightly more complicated argument, almost exactly the same as in my paper with Schaeffer, then proves the claim about the loops.

The Critical Exponent is Computable for Automatic Sequences. 
Luke Schaeffer, Jeffrey Shallit 
Int. J. Found. Comput. Sci. Vol. 23 No. 8 Pg. 1611-1626
Year: 2012