I am new to DFA and I am trying to understand the following question.

The alphabet is Σ = {0, 1} Construct DFA for L = {0^n: n is either a multiple of 3 or a multiple of 5 }

Question The above language does not say anything about the 1s.

When we write strings in this Language, we get L = {є, 000, 00000, 000000, 000000000, ...} There are no ones in this language.

According to the language description, 0010 would not be a valid string. Right?

So, in the DFA that we construct do we need to show 1s? Can I just leave them out?


Either you can make a 1 transition from every state to a non-final sink state. Or make a note that any character that doesn't match an available transition goes to a non-final sink state.

Depends on what format is usual for the course.

I assume the reason that 1 is also in the alphabet is to trip up people who forget about this sink state.

  • $\begingroup$ hey, thanks. just wanted to confirm that we had to do something about that 1. we can't just leave it out from our DFA and not mention about it since Σ = {0, 1}. (that would become NFA Correct???) $\endgroup$ – rayan Jan 27 at 13:05
  • 1
    $\begingroup$ whether that becomes a NFA depends on the definition of NFA and whether it requires all characters to be represented in in graph. It often doesn't require full representation of the alphabet at each state but same deal really, you can make note of the non-final sink state. $\endgroup$ – ratchet freak Jan 27 at 13:09

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.