Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
EDIT: Added Lemma 2 which covers all cases asked about.
Lemma 1.  Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof.  Here's the algorithm.  Fix an input DFA $M$ and integer $n$.
For each $k\in\{0,1,\ldots, n\}$ in increasing order, do the following:

Construct a new DFA $M_k$ with a state $(s, i, j)$ for each state $s$ in $M$ and $i, j \ge 0$ with $i+j\le n$.  The new DFA $M_k$ simulates $M$, but uses the indices $i$ and $j$ to count, respectively, the number of 0's and 1's seen so far.  Make $(s, 0, 0)$ the start state, where $s$ is the start state of $M$. Make each state $(s, i, j)$ an accepting state of $M_k$ if $s$ is an accepting state of $M$ and $i+j=n$ and $j=k$. So $$L(M_k) = \{w \in L(M) : w \text{ has length $n$ and $k$ ones}\}.$$  Note that $M_k$ is a directed acyclic graph whose size is polynomial in $n$ and the size of $M$.

Enumerate the words accepted by $M_k$ as follows.  First delete all dead states (states not reachable from the start state, or from which no accept state can be reached).  Find the lexicographically first path in the language of $M_k$ by starting at the start state, then traversing from each node to the next, taking a 0-edge if possible and otherwise a 1-edge.  Stop upon reaching a start state, and output the path found.  Next, repeat the following: let $p$ be the path just enumerated.  Find the path $p'$ following $p$ in lexicographic order as follows.  Take the last 0-edge $(u, w)$ on $p$ such that there is a 1-edge out of $u$, and replace that 0-edge edge and the remaining suffix of $p$ by the 1-edge (say, $(u, w')$) out of $u$ and the lexicographically first path from $w'$ to an accept state (computed as described above, taking 0-edges when possible).  If there is no such edge $(u, w)$, stop.


Note that there are no dead states, so the algorithm can always find $p'$ as described above.
By inspection the time for Step 1 is polynomial in $n$ and the size of $M$, and each path enumerated in Step 2 is enumerated in time polynomial in $n$ and the size of $M$.  The words in $L(M)$ of length $n$ are enumerated in order of increasing number of 1's (i.e., increasing value of $k$.)  $~~\Box$
Lemma 2.  Given an instance of the &quot;weighted&quot; variant in the post, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing weight, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof. By a construction similar to Step 1 of the algorithm in the proof of Lemma 1, the problem reduces to the following problem.  Given an edge-weighted DAG $G=(V,E)$ and two nodes $s$ and $t$, enumerate all paths from $s$ to $t$, in order of increasing path weight, taking time polynomial in the size of the DAG between enumerated paths.
Here is an algorithm for that problem.  (Note: the data maintained by the algorithm will be become exponentially large, but this will be okay each additional path will still be enumerated in polynomial time.)
Observation 1.
Let $P_v$ denote the paths from $s$ to $v$.  For $v\ne s$,
$$P_v = \bigcup_{u:(u,v)\in E}\{ p \circ (u, v) : p \in P_u \},$$
where $\circ$ denotes concatenation.  Consider $P_v$ ordered by increasing path weight.  In this order, consider only the paths that end in a given edge $(u, v)\in E$.  Let these paths be
$$p_1 \circ (u, v),~p_2 \circ (u, v), ~\ldots, ~p_\ell \circ (u, v).$$
Then $p_1, p_2, \ldots, p_\ell$ are the paths in $P_u$, ordered by increasing path weight.
For each vertex $v$ and index $i$, let $P_v(i)$ denote the $i$th in $P_v$, ordered by path weight. We will build an enumerator of $P_v$ that enumerates the $s$-$v$ paths in order $P_v(1), P_v(2), \ldots$, that is, by increasing path weight.  At any given time, each enumerator $P_v$ will have so far enumerated $P_v(1), P_v(2), \ldots, P_v(i_v)$ for some $i_v$. It will support two operations:

Increment. Enumerate the next path $P_v(i_v+1)$ in the sequence and increase $i_v$ by one.

Query. Given an index $i\le i_v$, return the cost of the $i$th path in the sequence, i.e., the cost of $P_v(i)$.


The overall algorithm will simply repeatedly increment the enumerator for $P_t$ to enumerate all its paths in order.  It remains to describe how to implement the enumerator $P_v$ for any given $v\ne s$ to support the two operations above.
$P_v$ will record (in an array), for each path $P_v(i)$ that it has already enumerated (i.e., $i\le i_v$), the cost of that path.  This will let it perform the query operation in constant time.
To support the increment operation, following Observation 1, $P_v$ will maintain, for each edge $(u, v)$ into $v$, the index $j_{uv}$ such that the most recent path that ends in edge $(u, v)$ that it has enumerated is $P_u(j_{uv})\circ (u, v)$.  (Hence, $\sum_u j_{uv}$ equals $i_v$, the number of paths that $P_v$ has enumerated so far.)
By Observation 1, the next path $P_v(i_v+1)$ in the sequence is the cheapest of the following paths:
$$P_u(j_{uv}+1) \circ (u, v) \text{ such that } (u,v) \in E.$$
The enumerator will find this path by calling each enumerator $P_u$ for $(u, v)\in E$, to find the cost of $P_u(j_{uv}+1)$.  Having found the best path, say $P_{u'}\circ (u', v)$, it will increment $j_{u'v}$, and in the case that $j_{u'v} = i_{u'}$ (the best path uses the most recent path enumerated by $P_{u'}$), it will increment $P_{u'}$ (have it enumerate its next path), ensuring that $i_{u'}$ is at least $j_{u'v}+1$.  This way, each cost query to $P_v$ can be done in constant time.
Note that any given call to $P_t$ results in each enumerator $P_u$ being incremented at most once total, even though increments can propagate and  several enumerators $P_v$ could in principle ask $P_u$ to increment.  This is because, during any given call to $P_t$, for a given enumerator $P_u$, we can assume by induction (on distance to $t$) that each of its &quot;parents&quot; $P_v$ (with $(u,v)\in E$) is incremented at most once during the call to $P_t$.  So, once $P_u$ is incremented once during the call, its $i_u$ has increased by one, which is the most that any parent could need.
(Alternatively, we could proceed in rounds $r=1,2,\ldots$, and in round $r$ have every enumerator $P_u$ increment by one, producing $P_u(r)$.  Because $P_v(i) = P_u(i') \circ (u, v)$ where $(u,v)\in E$ and $i' \le i$, this would suffice.  It would still be polynomial time, but not as efficient.)  $~~\Box$
EDIT 2: Code for the algorithm (on DAGs) in the proof is here.