Problem: Given a DFA $D$, find all possible lengths of strings accepted by the $D$.
It makes sense that these lengths can be represented as $a_i+kb_i$. What might be the algorithm to find all such pairs $(a_i, b_i)$?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
Take your DFA and change each of its input symbols into a single symbol, say $a$. Now of course your automaton no longer is deterministic, but lengths are preserved. Then make the automaton deterministic again. The form of the new DFA is that of a initial linear path leading to a loop. This is because of the single letter restriction.
The accepting states in the initial linear path are the finite component of the language, of lengths that do not repeat. The accepting states in the loop represent the $a_i$ for your construction. The length of the loop is the single $b$ in the $a_i+kb$ representation.
answered Dec 23, 2019 at 17:37
-
$\begingroup$ Heh, that's a cute construction. Probably easier to implement than my answer, although mine can also give you the possible numbers of occurrences of each symbol as a semilinear set instead of just the length of the entire string. $\endgroup$ Dec 23, 2019 at 17:50
-
1$\begingroup$ @AaronRotenberg Thanks. Yes, the semiring approach is very versatile, and I love the way Kleene's algorithm and Warshall-Floyd can be seen as the same tool. (To be honest, I was first thinking that way, $R^k_{ij}$, with regular expressions over $\{a\}$.) $\endgroup$ Dec 23, 2019 at 18:03
-
$\begingroup$ Systems of semiring equations are a tool in the same class as linear programming. It's a giant sledgehammer and you have to resist the urge to hit everything with it. 😃 $\endgroup$ Dec 23, 2019 at 18:33
$\begingroup$
$\endgroup$
The set of possible lengths of strings accepted by a DFA is always a semilinear set. The semilinear sets form a Kleene algebra, and determining the possible lengths accepted by a DFA (or NFA) is a classic semiring graph problem which can be solved by applying Kleene's algorithm with the algebra of semilinear sets swapped out in place of the algebra of regular expressions.
Essentially, you pretend you are computing the regular expression accepted by the NFA, but for each $R_{ij}^k$, instead of storing an entire regular expression, you only store a representation of the semilinear set of possible lengths of the regular expression.
See Stephen Dolan's "Fun With Semirings" for other interesting things you can do by treating the edge labels of a graph as elements of a semiring.
