45.4k views
4 votes
In this assignment, you will need to implement a finite state machine that recognizes binary sequences that have remainder 1 if divided by 5. The string is not available all at once, it is fed in bit by bit, from the left most to the right. You can use a "#" symbol to indicate the end of the input. You should allow a user to type in the binary sequence through the terminal. Output "Yes" or something like that if a sequence satisfies our requirement. You can write it in whatever language you like. I/O exception handling is not required. Sample input/output: InputOutput 1011 Yes 101 NO Submission: 1. Your source codes. 2. Screen shots of some typical input.

User Mangini
by
7.6k points

1 Answer

4 votes

To implement a finite state machine that recognizes binary sequences with a remainder of 1 when divided by 5, you can follow these steps:


1. Start with an initial state called "S0". This state represents the starting point of the machine.
2. Define two more states, "S1" and "S2". These states will represent the possible remainder values when dividing the binary sequence by 5.
3. For each bit of the binary sequence, starting from the leftmost bit, follow these rules:
- If the current state is "S0" and the bit is 0, stay in the same state ("S0").
- If the current state is "S0" and the bit is 1, transition to state "S1".
- If the current state is "S1" and the bit is 0, transition to state "S2".
- If the current state is "S1" and the bit is 1, stay in the same state ("S1").
- If the current state is "S2" and the bit is 0, stay in the same state ("S2").
- If the current state is "S2" and the bit is 1, transition to state "S0".
4. Repeat step 3 for each bit of the binary sequence until the end of the input is reached (indicated by a "#" symbol).
5. After processing the entire binary sequence, if the final state is "S1", output "Yes" to indicate that the binary sequence has a remainder of 1 when divided by 5. Otherwise, output "No" to indicate that it does not satisfy the requirement.

User Yosi Dahari
by
7.9k points