patternModerate
Length of strings accepted by DFA
Viewed 0 times
lengthdfastringsaccepted
Problem
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)$?
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)$?
Solution
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.
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.
Context
StackExchange Computer Science Q#118813, answer score: 10
Revisions (0)
No revisions yet.