<p>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. </p>

<p>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.</p>

<p>I also agree that this probably belongs in the CS area rather than theoretical CS.</p>

<p>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$.</p>

<p>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.</p>

<p>Construct the a <strong>non</strong>-deterministic FSA $D&#39;$ 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:</p>

<p>$\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.</p>

<p>$\langle[x],a,1,[])\rangle$ where $a$ is <em>not</em> 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.</p>

<p>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 $[]$:</p>

<p>$\langle[x], \epsilon, 0, [\epsilon]\rangle$</p>

<p>Convert that NFSA to a DFSA and you are done.</p>

CC BY-SA 3.0
2012-04-30T12:19:03.200Z
Thank you very much. This is definitely an easier way to look at the problem. My main concern, which I should have clarified in advance, is the size of the resulting DFA. Since converting an NFA (especially the one in question) might be costly in terms of size, I'm trying to directly build a DFA, and for it to be as small as possible it seems that the structure of V must be taken full advantage of. Converting an NFA and then simplifying it, the problem of structure still remains.
ezer
CC BY-SA 3.0
2012-04-30T16:29:31.730Z
Size can be addressed -- for example represent multiple states in some very efficient fashion using bit-packing or small numbers.  But I'm still curious why it is an issue? Is this going on some minuscule device and/or V is very large?  Again, a more complete description of your specs -- including environment, amount of data, size of V, space available, speed requirements, etc -- would help us answer. And this definitely belongs in the CS area, not Theoretical CS -- any moderators listening in?
David Lewis
CC BY-SA 3.0
2012-05-04T00:32:29.613Z
Sorry for the late response. By "size" of the DFA I mean the number of states in it. Many such DFAs are going to be created once, then intersected repeatedly in different variations. The resulting intersected DFA will be run (many times) through algorithms with runtime up to quartic in the number of states. That is why a large DFA will be very costly in the long run. The solution I'm looking for would not depend on the size of the subsets of V (since arcs should be merged) and use as few states as possible. Would you recommend reposting the question in the CS area?
ezer
CC BY-SA 3.0
2012-05-04T02:40:09.843Z
@ezer -- thanks for the new information. Sounds like a substantially more complex project, with this is only a part.  Are you sure you are not suboptimizing by picking out this one subproblem for independent solution? By "intersected DFA will be run through algorithms" do you mean it will be executed, or used to build other automata or objects? As for minimizing states, you can always do that algorithmically with the DFA you get from my procedure (which, by the way, has mistakes). Another approach might be to base the whole thing on regular expressions. Tough to tell.
David Lewis
CC BY-SA 3.0
2012-05-04T02:50:04.340Z
@ezer -- as for posting on CS rather than TCS -- might make sense, but I'm not sure. I'm relatively new in both, but it does sound like an implementation problem as much as a theoretical one.  You might look around for similar stuff to see if yours fits. OTOH, your whole project might be too big and complex for SE altogether, more of a consulting job.  I don't know if it's kosher to say this here, but if you want to talk about consulting, I'd be interested.
David Lewis
CC BY-SA 3.0
2012-05-04T14:43:40.573Z
Most of the project is already written, where some algorithms were tested on manually prepared DFAs. Regular expressions are not appropriate for this task. I'm getting closer to solving the problem, but if that doesn't work, I will certainly use a version based on your solution (though it has some mistakes), whether by algorithmically eliminating states or not. So thanks again. I would consider reposting it there if I fail.
ezer
CC BY-SA 3.0
2012-05-04T21:09:25.297Z
OK, I wasn't thinking of programming, just about the kind of theoretical and algorithmic issues you asked about here. Good luck.
David Lewis
CC BY-SA 3.0
2012-04-29T22:49:46.110Z
2012-04-29T23:02:59.480Z
2012-04-29T23:02:59.480Z
David Lewis
<p>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$.</p>

<p>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$.</p>

<p>The algorithm should return the weighted DFA as a 4-tuple $&lt;Q,\delta ,q_0 , F&gt;$:</p>

<p>$Q=\{q_{0},q_{1}\}$</p>

<p>$\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$</p>

<p>$q_{0}=q_{0}$</p>

<p>$F=\{q_{0},q_{1}\}$</p>

<p>The algorithm must return the DFA as a 4-tuple as described. My main concern is the <strong>size</strong> 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.</p>

<p>The problem arises in the general case, where the inclusion relation
between subsets is unknown.</p>

<p>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.</p>

<p>When the sequence is longer, there is a chance for more complex inclusion
relations between its subsets.</p>

<p>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.</p>

<p>Any insight, reference or suggestion on how to tackle this problem
would be appreciated.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-29T16:51:45.560Z
In what form do you want the DFSA -- a state/input/output graph?  Or would an algorithm in a programming language do? If the latter, then why pose this as a DFSA? Do you have a system that  executes DFSAs, and if so, what model does it expect?  Is the need for a "pre-compiled" DFSA motivated by performance considerations, that is, there's a ton of data to process and/or it needs to be done quickly, perhaps in real time?.  In any case, it will help a lot to explain the context of the problem in more detail. There could be complex optimization issues, but without the context, it's hard to say.
David Lewis
CC BY-SA 3.0
2012-04-29T18:46:36.320Z
Thanks for your input. I've added an example DFA which is expected by the system, and a statement that "I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations." These would certainly be in interest after I manage to better understand the problem and the solution.
ezer
CC BY-SA 3.0
2012-04-29T21:13:40.663Z
As far as feasibility, one can construct an NFA from your regular expression (/[ab][bcd][de]/ in your example) and just count the number of times it hits the 'accept' state.  In general, you pay an exponential increase in size when transitioning from an NFA to a DFA but I'm not sure about your specific case.  If this question is only asking for an algorithm to count the number of occurrences of a regular expression in a string, then perhaps this question is best suited to the CS SE.  If this question is really asking for a polynomial sized DFA, then you should make that clear.
user834
CC BY-SA 3.0
2012-04-30T12:27:45.170Z
I am indeed in need for a small as possible DFA. I have added a clarification.
ezer
<fl.formal-languages><automata-theory>
Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet
ezer
# Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet

(Asked by: username_0 on 2012-04-29)

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=\{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.

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: In what form do you want the DFSA -- a state/input/output graph?  Or would an algorithm in a programming language do? If the latter, then why pose this as a DFSA? Do you have a system that  executes DFSAs, and if so, what model does it expect?  Is the need for a "pre-compiled" DFSA motivated by performance considerations, that is, there's a ton of data to process and/or it needs to be done quickly, perhaps in real time?.  In any case, it will help a lot to explain the context of the problem in more detail. There could be complex optimization issues, but without the context, it's hard to say.  
> **username_0**: Thanks for your input. I've added an example DFA which is expected by the system, and a statement that "I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations." These would certainly be in interest after I manage to better understand the problem and the solution.  
> **username_2**: As far as feasibility, one can construct an NFA from your regular expression (/[ab][bcd][de]/ in your example) and just count the number of times it hits the 'accept' state.  In general, you pay an exponential increase in size when transitioning from an NFA to a DFA but I'm not sure about your specific case.  If this question is only asking for an algorithm to count the number of occurrences of a regular expression in a string, then perhaps this question is best suited to the CS SE.  If this question is really asking for a polynomial sized DFA, then you should make that clear.  
> **username_0**: I am indeed in need for a small as possible DFA. I have added a clarification.  

---

## 1 answers

### Answer by username_1 on 2012-04-29. Score: 4

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.

> **Comments:**
> **username_0**: Thank you very much. This is definitely an easier way to look at the problem. My main concern, which I should have clarified in advance, is the size of the resulting DFA. Since converting an NFA (especially the one in question) might be costly in terms of size, I'm trying to directly build a DFA, and for it to be as small as possible it seems that the structure of V must be taken full advantage of. Converting an NFA and then simplifying it, the problem of structure still remains.  
> **username_1**: Size can be addressed -- for example represent multiple states in some very efficient fashion using bit-packing or small numbers.  But I'm still curious why it is an issue? Is this going on some minuscule device and/or V is very large?  Again, a more complete description of your specs -- including environment, amount of data, size of V, space available, speed requirements, etc -- would help us answer. And this definitely belongs in the CS area, not Theoretical CS -- any moderators listening in?  
> **username_0**: Sorry for the late response. By "size" of the DFA I mean the number of states in it. Many such DFAs are going to be created once, then intersected repeatedly in different variations. The resulting intersected DFA will be run (many times) through algorithms with runtime up to quartic in the number of states. That is why a large DFA will be very costly in the long run. The solution I'm looking for would not depend on the size of the subsets of V (since arcs should be merged) and use as few states as possible. Would you recommend reposting the question in the CS area?  
> **username_1**: @ezer -- thanks for the new information. Sounds like a substantially more complex project, with this is only a part.  Are you sure you are not suboptimizing by picking out this one subproblem for independent solution? By "intersected DFA will be run through algorithms" do you mean it will be executed, or used to build other automata or objects? As for minimizing states, you can always do that algorithmically with the DFA you get from my procedure (which, by the way, has mistakes). Another approach might be to base the whole thing on regular expressions. Tough to tell.  
> **username_1**: @ezer -- as for posting on CS rather than TCS -- might make sense, but I'm not sure. I'm relatively new in both, but it does sound like an implementation problem as much as a theoretical one.  You might look around for similar stuff to see if yours fits. OTOH, your whole project might be too big and complex for SE altogether, more of a consulting job.  I don't know if it's kosher to say this here, but if you want to talk about consulting, I'd be interested.  
> **username_0**: Most of the project is already written, where some algorithms were tested on manually prepared DFAs. Regular expressions are not appropriate for this task. I'm getting closer to solving the problem, but if that doesn't work, I will certainly use a version based on your solution (though it has some mistakes), whether by algorithmically eliminating states or not. So thanks again. I would consider reposting it there if I fail.  
> **username_1**: OK, I wasn't thinking of programming, just about the kind of theoretical and algorithmic issues you asked about here. Good luck.  

---

