July 10, 2012

Puzzle: Finite State Machine

I loved solving problems on Finite State Machines back in college days. Recently, I came across a good problem and thought it would be expedient to share it for you as well!

Q. The ACME Company has recently received an order from a Mr. Wiley E. Coyote for their all-digital Perfectly Perplexing Padlock. The P3 has two buttons ("0" and "1") that when pressed cause the FSM controlling the lock to advance to a new state. In addition to advancing the FSM, each button press is encoded on the B signal (B=0 for button "0", B=1 for button "1"). The padlock unlocks when the FSM sets the UNLOCK output signal to 1, which it does whenever the last N button presses correspond to the N-digit combination.
  1. Unfortunately the design notes for the P3 are incomplete. Using the specification above and clues gleaned from the partially completed diagrams below fill in the information that is missing from the state transition diagram with its accompanying truth table. When done :
    • Each state in the transition diagram should be assigned a 2-bit state name S1S0 (note that in this design the state name is not derived from the combination that opens the lock),
    • The arcs leaving each state should be mutually exclusive and collectively exhaustive,
    • The value for UNLOCK should be specified for each state, and
    • The truth table should be completed.
    •  What is the combination for the lock?


     
    Source: MIT Course Ware 

6 comments:

  1. Palindrome, it was a nice problem. Is the combination to the lock 100?

    ReplyDelete
    Replies
    1. Yes! That is the correct answer. Thanks for posting.

      Delete
  2. I am not getting this truth table. seems some inconsistency to me. Because if my current state is 11 then whatever I press as input my unlock should be set. Now due to requirement of mutually exclusive there should be 2 states as Unlock=1 but it is in direct clash with row 3 of truth table.

    ReplyDelete
    Replies
    1. Hi Ravi. The unlock state here is "11". So there ought to be two states corresponding to "11", which is the case in the truth table. The state "01" is the one at the left bottom. Please let me know if this still confuses you.

      Thanks!

      Delete
    2. I was thinking that unlock output n truth table corresponds to next state but I think it is according to present state.

      Delete
    3. In normal TT convention, the output value should show the next states value.

      Delete