# Deciding if a finite automata accepts strings of any length

Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not.

What I doing was, I have algorithm to count the number of all strings of some fixed length $n$. Now let there are $k$ states. Suppose we got a positive result (i.e the number of strings is $> 0$) for all $n$ up to $k$. Then check $k+1$: if it gives a positive result then we can say, at least one state is visited twice by that path of length $k+1$. That means we'll get $x$ such that all of $k+1+nx$ for all $n\geq 0$ will get accepted if $x=1$ then done. If not then check again $k+2$ again we'll get a $y$ like that. So for all $n>k$ we're getting APs of lengths which are acceptable but then can we say after some finite state we can say all numbers are accepted ?

• Do you mean "for each $n$, there is at least one string of length $n$ accepted by the DFA"? – J.-E. Pin Aug 21 '14 at 10:31
• Yes, for all positive integer $n$ – James Yang Aug 21 '14 at 10:32
• Please edit the question to use clearer wording (such as that suggested by J.E. Pin), as I too found it ambiguous. – D.W. Aug 21 '14 at 16:39

Let $L$ the language accepted by your DFA. The question amounts to ask whether $\{ |u| \mid u \in L \} = \mathbb{N}$. To check this, just identify all letters to a single letter, say $a$, in your DFA. You will get a NFA on the alphabet $\{a\}$. It now remains to check whether this NFA accepts $a^*$.
• @JamesYang, you can effectively construct a regular expression or a finite automaton for the symmetric difference of $a^*$ and the language of the NFA. This regular language is empty if and only if the NFA accepts $a^*$. Verifying emptiness may be done (for example) by a search in the configuration graph of the corresponding automaton. – Yoav bar sinai Aug 21 '14 at 11:43