computing maximal bit density over a FSM let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("Hamming weight") divided by the word length.


  what is an algorithm to compute $\max_{x \in L} f(x)$?


there is a simple randomized/ estimation algorithm that computes $f(x)$ over random words; am looking for a deterministic one. note that $f(x)$ evaluated on the shortest word in $L$ is not necessarily the same as the global minimum. am also interested in other generalizations of $f(x)$ that are based on similar "simple word metrics".

bkg: this question arose in studying &amp; idea in attacking an old open number theoretic problem.
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