Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 ?

share|improve this question
1  
Do you mean "for each $n$, there is at least one string of length $n$ accepted by the DFA"? –  J.-E. Pin Aug 21 at 10:31
    
Yes, for all positive integer $n$ –  James Yang Aug 21 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 at 16:39

1 Answer 1

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^*$.

share|improve this answer
    
and how will you check that ? –  James Yang Aug 21 at 11:05
3  
@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 at 11:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.