Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ denote the DFA that accepts the given $n$th regex.

Clearly we can model $A_n$ with a DFA that is one big loop with every state being accepted except for the second and "second from last" state.

Let $N \subset\Bbb{N}$ be a finite set. Consider the product DFA: $A = \prod_{n \in N} A_n$.

Given that I made these DFA's incredibly simple - they're just one big loop - is it feasible that there exists a formula for a really tight estimate the length of the minimum word accepted by $A$?

Has anyone researched this ? I googled but all I could find was minimum word length in a PDA.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.