0

Design a DFA for the set of strings in $\{a\}$* such that it's length is divisible by 3 or 5.

The point that I am not understanding is, how many states do we need? Since we can't possibly represent all possible states such that the length of the string is divisible by 3 or 5.

      Q |    a
        ___________
 ->   0 |    1
      1 |    2
      2 |    3
    F 3 |    4
      4 |    5
    F 5 |    6
    F 6 |    7
      7 |    8
      8 |    9
    F 9 |    10
    F 10|    11
      .     
      .

The left column represents the current state, the right column represents what state to go to next if another a is added to the string. The F's represent the accepted states.

How do I find a finite set $Q$ that represents all possible sets, and a finite subset $F \subset Q$ that represents all accepted states?

bof
  • 78,265
JLL
  • 979

1 Answers1

1

HINT: Continue your table past $a^{15}$, maybe even to $a^{30}$, and pay careful attention to patterns. Or think about what it means for $n$ to be the least common multiple of $3$ and $5$. That’s not as much work as it may seem, but as a possibly quicker alternative you could start by looking at the problem of designing a DFA that accepts $a^n$ when $n$ is a multiple of $2$ or $3$; you should spot the pattern much quicker in this case, and thinking about the least common multiple of $2$ and $3$ is again useful.

Brian M. Scott
  • 616,228