Turing’s World Ch8 Exercise2

Exercise 2 (Lights out) Imagine that you have three light switches, numbered 1,2, and 3, controlling two lights in a hallway, one at the north end, the other at the south end. The way the switches work is as follows:

  1. Switch 1 turns the north light on or off, depending on whether it is currently off or on.
  2. Switch 2 switches both of the lights, changing them from on to off or off to on.
  3. Switch 3 turns the south light on or off.

Design a one-way finite state machine that checks to see if both the lights are off. That is, it should accept a string of 1’s, 2’s, and 3’s if and only if the string represents a sequence of switch flips that results in both the lights being off (assuming they were off to start with). For example, it should accept the string 213 since this turns on both the lights and then turns off the north light and then the south light. By contrast, it should reject the string 23213 since this sequence of flips leaves the north light on.

Current State Symbol Read Action Next State
0 1 MOVE RIGHT 1
0 2 MOVE RIGHT 3
0 3 MOVE RIGHT 2
1 1 MOVE RIGHT 0
1 2 MOVE RIGHT 2
1 3 MOVE RIGHT 3
2 1 MOVE RIGHT 3
2 2 MOVE RIGHT 1
2 3 MOVE RIGHT 0
3 1 MOVE RIGHT 2
3 2 MOVE RIGHT 0
3 3 MOVE RIGHT 1

State 0 is the accepting state.

State 0: all off
State 1: North light on
State 2: South light on
State 3: Both North and South lights on

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: