1
$\begingroup$

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 ?

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ and how will you check that ? $\endgroup$ – James Yang Aug 21 '14 at 11:05
  • 3
    $\begingroup$ @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. $\endgroup$ – Yoav bar sinai Aug 21 '14 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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