I was provided with the solution to the language being represented. An example of accepted input would be [001][101]. The DFA that would recognize this language is below. enter image description here

What do the states represent? What are the meaning of the transitions


1 Answer 1


First look at the second component only. This represents a finite state automaton for strings that have a binary value that is a multiple of five. The states are the value of the string up to now, mod 5. We move from state $x$ with bit $d$ to state $2{\cdot}x+d\pmod 5$. This ensures that $b$ is indeed a multiple of five.

enter image description here

A similar automaton for strings that are a multiple of $3$ see Algorithms computing if a number is a multiple of 3.

The first component is performing a kind of long division, dividing $b$ by $5$ to obtain $a$. Whenever $2{\cdot}x+d \ge 5$ the first component is $1$, otherwise it is $0$.

  • $\begingroup$ I understand the automaton where we check if the second component is divisible by 5. I also understand where the first component is what you just explained. However, I fail to see where they combine to form the fsm I posted, as the transitions are inconsistent with the approach you outlined with the second component. For example, on the second component in your FSM you transition TO a state on a 1 (from final state ). While in the FSM I posted the final state receives a transition on a 1. @HendrikJan I am assuming that the states corresponds with each other $\endgroup$
    – Patrick
    Feb 14 at 23:22
  • $\begingroup$ @Patrick Right! All arrows in the other direction?? Curious, I did not note this when posting the picture. From your earlier question I assumed it was most significant bit at the left. Just test an asymmetric example. Thus 100011$_2$=32+2+1=35 is a multiple of five, whereas 110001$_2$=32+16+1=49 is not. $\endgroup$ Feb 15 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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