For a given finite alphabet $\Sigma$, my goal is to write an algorithm that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets ($V_{i}\subseteq\Sigma$), and returns a weighted deterministic finite-state automaton with the following property: for every input string $s$, the automaton penalizes each substring $s_{1}s_{2}\dots s_{n}$ of $s$ if $s_{i}\in V_{i}$ for every $1\le i\le n$.
For example, if $\Sigma=\{a,b\}$, $V=V_{1}V_{2}=\{b\}\{b\}$, the returned automaton would penalize the string $s=bbbb$ $3$ times, i.e. when accepting the string and summing over the weighted arcs, the result would be $3$.
The algorithm should return the weighted DFA as a 4-tuple $<Q,\delta ,q_0 , F>$:
$Q=\{q_{0},q_{1}\}$
$\delta=\{(q_{0},a,0,q_{0}),(q_{0},b,0,q_{1}),(q_{1},b,1,q_{1}),(q_{1},a,0,q_{0})\}\subseteq Q\times\Sigma\times\{0,1]\times Q$
$q_{0}=q_{0}$
$F=\{q_{0},q_{1}\}$
The algorithm must return the DFA as a 4-tuple as described. My main concern is the size of the resulting DFA. Therefore, the structure of $V$ should be taken advantage of. Capitalizing on subset relations, it is possible to eliminate states from the resulting automaton. For example, when all subsets are pairwise disjoint, the automaton would have $n$ states.
The problem arises in the general case, where the inclusion relation between subsets is unknown.
For example, if $\Sigma=\{a,b,c,d,e\}$ and $V=\{a,b\}\{b,c,d\}\{d,e\}$, the string $abde$ should be penalized twice (both $abd$ and $bde$ are penalized), where $acde$ should be penalized only once ($acd$ is penalized, but not $cde$). This happens since there is a chain of non-empty intersections between subsets $(V_{1}\cap V_{2},V_{2}\cap V_{3}\not=\emptyset)$, so having accepted a penalized substring, some paths taken must be remembered in order to know how to move on. Paths in the required automaton would have to be splitted accordingly. In this case the resulting automaton could be minimally built with 5 states.
When the sequence is longer, there is a chance for more complex inclusion relations between its subsets.
I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations. As stated, my main concern is the size of the DFA.
Any insight, reference or suggestion on how to tackle this problem would be appreciated.
More specifically, I'm now trying to figure out how to capitalize on inclusion relations between subsets in order to eliminate states (in advance) when building the DFA.
EDIT: Added a paragraph and a final comment about using the structure of V to minimize the DFA, emphasis on my need of a smallest DFA as possible.