# Explain meaning of states and transitions for DFA that accepts two binary words (a,b) with b = 5a

I was provided with the solution to the language being represented. An example of accepted input would be . The DFA that would recognize this language is below. What do the states represent? What are the meaning of the transitions

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. 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$$.
• @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. Feb 15 at 9:59