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.
What do the states represent? What are the meaning of the transitions
$\begingroup$
$\endgroup$
1
-
$\begingroup$ This automaton implements the answer given for your earlier question How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?! $\endgroup$– Hendrik JanFeb 14 at 18:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
-
$\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$– PatrickFeb 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