Question

You would like to design a finite state machine that accepts non-negative numbers written in ternary notation (i.e., using digits 0, 1, 2), which leave a remainder of 7 when divided by 13. the number is to be fed most-significant-digit first. what can you say about this machine's state-diagram?

(a) cannot have a finite-state suffice
(b) 14 states and 21 edges suffice
(c) 7 states and 21 edges suffice
(d) 13 states and 39 edges suffice
(e) 20 states and 27 edges suffice
(f) at least 21 states are needed

Answer 1

To design a finite state machine that accepts non-negative numbers in ternary notation that leave a remainder of 7 when divided by 13, we need 7 states and 21 edges.

Step-by-step explanation:

The given problem is to design a finite state machine that accepts non-negative numbers written in ternary notation which leave a remainder of 7 when divided by 13. The machine should be designed to accept numbers with the most significant digit first.

Since the ternary notation uses digits 0, 1, and 2, we can represent the remainders as 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. From these remainders, we need to find a pattern that satisfies the conditions given in the problem.

By analyzing the remainders, we can see that there are only 7 unique remainders for non-negative numbers in ternary notation that leave a remainder of 7 when divided by 13. Therefore, the correct answer is (c) 7 states and 21 edges suffice.