The supremum bit density will either be achieved by a finite word $v$ in the language, or by the limiting bit density of some sequence $u v w, u v^2 w, u v^3 w, \ldots$ of words in the language, which equals the bit density of $v$. In both cases, we have that $|v| \leq n$ without loss of generality, where $n$ is the number of states in the finite automaton.
Below I give you a polytime algorithm to find $v$. To make the algorithm simpler, I assume the automaton is deterministic. This isn't really essential.
Algorithm: Find $v$.
Let {1,2,...,n} be the set of states.
Let delta be the transition functor.
Let 1 be the initial state.
Let F be the set of accepting states.
Let X be the set of states reachable from the initial state.
Let Y be the set of states that can reach an accepting state.
Let A be an (n+1)-by-(n+1)-by-(n+1) array of strings or NULL.
Set A[i,i,0] = "" for all i in {1,2,...,n}.
Set A[i,j,0] = NULL for all i != j in {1,2,...,n}.
For k in {1,2,...,n} do:
For i in {1,2,...,n} do:
For j in {1,2,...,n} do:
Let W0 = "0" ++ A[delta(i,0), j, k-1] (or NULL, if A[delta(i,0), j, k-1] is NULL).
Let W1 = "1" ++ A[delta(i,1), j, k-1] (or NULL, if A[delta(i,0), j, k-1] is NULL).
If density(W0) > density(W1) then: (let density(NULL) = -1 by convention)
Set A[i,j,k] = W0.
Else:
Set A[i,j,k] = W1.
Return highest density non-NULL word
in { A[1,j,k] : j in F, k in {1, ..., n} }
or in { A[j,j,k] : j in X intersect Y, k in {1, ..., n} }.
The idea behind the algorithm is that A[i,j,k]
stores the highest density path from state i
to state j
with length k
. We build up this table from k=0
to k=n
, and then pick the highest density v
that matches our criteria (either it is a word in the language, or it is a loop in some word in the language).