Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet

Question

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.

Answer 1

I'm still not sure why you want it in strict quadruple form, with a set of structure-less states. That's a model that mainly intended for doing the abstract mathematics surrounding state-transition systems, but famously ill-suited to actual computation unless you are looking for the extreme speed offered by "pre-compiling" into deterministic form, at the expense of storage space.

User834 is correct that this is a fairly simple sub-problem of regular expression matching, with the added feature of counting matches, so you may take my solution in that vein. I'm not a RE maven, but I think there is a way to get match counting out of REs in most implementations. So that's an approach you might consider for practical implementation without all the trouble of constructing your own FSAs.

I also agree that this probably belongs in the CS area rather than theoretical CS.

If I read your problem correctly, it amounts to taking a set of strings $V$ and looking for every occurrence of a string in $V$ as a maximal substring (prefix, suffix or interior) of $x$, the input to the DFSA we'll call $D$. That count is the "penalty" for $x$. Here's one way to do it, though following your prescription not to worry about performance, takes no advantage of any structure or redundancy in $V$.

In your example, $V=\{abd, abe, acd, ace, add, ade, b...\}$. Pre-multiply all the sets $V_i$ into strings of $V$ in tree form, with elements of $V_i$ all on level $i$, each descended directly from each element of $V_{i-1}$. Level $0$ is an abstract root, say $\epsilon$. For your example, descended from $\epsilon$ are $a$ and $b$, the elements of $V_1$. On level 2, descended from each of $a$ and $b$ are the members of $V_2$: $b$, $c$ and $d$. So there are 6 nodes on level 2 altogether, the 3 members of $V_2$ repeated twice. And so on to the leaves. Each path from $\epsilon$ to a leaf of the tree represents one "penalty string" in V. You did not make clear what happens if a string appears more than once in $V$. If you don't want it to count for multiple penalties, then you should prune duplicate strings out of the tree by some suitable algorithm.

Construct the a non-deterministic FSA $D'$ as follows. States of $Q$ are pointers to nodes of the tree. Each state thus represents a complete string in $V$ or a prefix of such a string, to be represented here by $[x]$ (though that $x$ isn't unique to a node -- I assume there is a pointer to the actual node of the tree). The transition function $\delta$ contains three kinds of edges:

$\langle[x],a,0,[xa])\rangle$ where $a$ is a direct descendant of $[x]$, and $[xa]$ is that descendant node. Note that we output 0 at this point because we aren't sure we've reached the maximal match.

$\langle[x],a,1,[])\rangle$ where $a$ is not a direct descendant of $[x]$ in the tree, and $[]$ is a dead state. We output $1$ here because $[x]$ is matched but it is maximal, since $[xa]$ is not matched.

If we were dealing with prefixes only and not interior and suffix matches, we'd be done and this would be a deterministic automaton. To account for non-prefixes, we need to non-deterministically circle back to $[\epsilon]$, the start state, at every stage with an edge like this for every state $[x]$ except $[\epsilon]$ and $[]$:

$\langle[x], \epsilon, 0, [\epsilon]\rangle$

Convert that NFSA to a DFSA and you are done.