# Does a DFA on {0,1} accept any string whose length is composite/prime?

My attempt is this: This is similar to proving whether a language {w^p|p is prime} is regular or not.(For the prime case) Suppose on the contrary that this language L is regular. Let p be its pumping length and t be a prime greater than p. (Note that t exists since the number of primes is inﬁnite.) Then, wt ∈ L, and by the pumping lemma, we can write wt as wt = xyz for some x,y,z, such that |y|> 0, |xy|≤p, and for each i≥0, xy^iz ∈L. By setting i = t + 1, the pumping lemma implies that xy^(t+1)z is in L. On the other hand, xy^(t+1)z = w^(t+t|y|), which implies that xy^(t+1)z does not belong to L, as t + t|y| = t(1 +|y|) is not a prime.Thus, a contradiction occurs, so that L is not regular. Hence we can say that the DFA may not accept any string of length prime. Please tell me where i am wrong.

• I don't understand the question you are trying to answer. Some DFAs only accept strings whose length is composite, some accept only strings whose length is prime, some accept stings of both time, and some neither. All of these possibilities are realized by finite languages, e.g. $\{aa\},\{aaaa\},\{aa,aaaa\},\emptyset$. Commented Nov 5, 2016 at 14:01
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Commented Nov 5, 2016 at 14:22
• It's hard to tell what your question is. Are you looking for an algorithm? Are you trying to prove or disprove a statement? If so, what is the precise statement that you are trying to prove/disprove? I recommend you avoid using the word "any" when talking about mathematics, as it can be ambiguous whether "any" means "for all" or "there exists".
– D.W.
Commented Nov 5, 2016 at 14:23
• Help us out here. Why do you think you're wrong? Commented Nov 5, 2016 at 17:52
• All i wanted to know is whether my approach was correct or not. And the question should have been only for prime.sorry for that Commented Nov 6, 2016 at 2:52