How Does a Traffic Light Know What Comes Next?

Two roads, one controller

Watch the junction for a whole round, then answer these.

• a.A driver on the main road sees three colors. How many different steps does the controller go through in one round?
• b.While the main road’s light is red, what is the side road’s light doing?

A button for people on foot

On a road with no junction, people who want to cross press a button on the pole. This crossing is a first try. The cars keep green for as long as nobody presses. Press the button, and the cars get yellow, then red, and walkers get their green figure. Then the red figure flashes (don’t start to cross now), and the cars get green again.

Each step the controller can be in is called a state. The junction has four states. Things that happen to it, such as “the time is up” or “someone pressed the button”, are events. An event moves the controller from one state to another: a transition. A machine with a fixed number of states that moves between them on events is a finite state machine (FSM). (Grade 12’s The Limits of Computing studies them; you need none of it here.)

An FSM can be drawn as a state diagram: a circle for each state, an arrow for each transition, labeled with its event. Or it can be written as a transition table: a row for each state, a column for each event, and in each cell the next state. Both say exactly the same thing.

That is the whole junction: four states and four arrows. Each state also has its seconds: the page uses 8 for main green, 6 for side green and 3 for each yellow. Real lights hold green much longer.

What the light remembers

Whatever an FSM needs to remember must be one of its states: it has no other memory. That tells us how to fix the crossing.

The cars must get at least 8 seconds of green. So “cars green” becomes two states: fresh (less than 8 seconds of green) and go (8 seconds or more). A press in go turns the cars yellow at once. A press in fresh must not, but it mustn’t be forgotten either, so it moves to a third green state, waiting, which lights the WAIT lamp on the button box. When the 8 seconds are up, waiting goes to yellow.

Here is the fixed crossing’s table. A dash means the event changes nothing.

With blocks

The junction’s controller is one variable, state, and a choice: which state comes after this one? This program says each state and then moves to the next, six times.

In Python (from Grade 8)

The same controller in Python is a function that answers one question: given a state, what comes next? A second function gives each state’s seconds, so the program can print a timetable.

def next_light(state):    if state == 'main green':        return 'main yellow'    elif state == 'main yellow':        return 'side green'    elif state == 'side green':        return 'side yellow'    else:        return 'main green' def seconds(state):    if state == 'main green':        return 8    elif state == 'side green':        return 6    else:        return 3 state = 'main green'clock = 0for change in range(9):    print('at', clock, 's:', state)    clock = clock + seconds(state)    state = next_light(state)

at 0 s: main greenat 8 s: main yellowat 11 s: side greenat 17 s: side yellowat 20 s: main greenat 28 s: main yellowat 31 s: side greenat 37 s: side yellowat 40 s: main green

Every 20 seconds the same four states come round again. That repeat is called the light’s cycle.

The crossing’s table as a function

The crossing has two events, so its function takes the state and what happened. Each if is one cell of the table; anything else falls through to the last line and stays. The loop at the bottom prints the function as a table.

def next_state(state, event):    if state == 'fresh' and event == 'time':        return 'go'    if state == 'fresh' and event == 'button':        return 'waiting'    if state == 'go' and event == 'button':        return 'stopping'    if state == 'waiting' and event == 'time':        return 'stopping'    if state == 'stopping' and event == 'time':        return 'walk'    if state == 'walk' and event == 'time':        return 'hurry'    if state == 'hurry' and event == 'time':        return 'fresh'    return state       # anything else: stay states = ['fresh', 'go', 'waiting', 'stopping', 'walk', 'hurry']for state in states:    print(state, ': time →', next_state(state, 'time'),          ', button →', next_state(state, 'button'))

fresh : time → go , button → waitinggo : time → go , button → stoppingwaiting : time → stopping , button → waitingstopping : time → walk , button → stoppingwalk : time → hurry , button → walkhurry : time → fresh , button → hurry

Now let your function run the lights. The widget asks your next_state about every state and event (twelve questions), makes its table from the answers, and runs the crossing on it.

On the micro:bit board

A real crossing’s controller is a small computer like the board in Grade 8. The same next_state runs it here. The display is the lights: on the left, the cars’ three lamps (red at the top, then yellow, then green); on the right, the walkers’ red figure at the top and green figure at the bottom; the dot in the middle is WAIT. A lit lamp is bright, a lamp that is off glows dimly. Button A is the walkers’ button.

The loop finds out whether an event has happened, asks next_state where to go, and shows that state’s picture. waited is how many milliseconds the light has been in this state. (On the way to waiting, began is left alone: the 8 seconds count from when the cars got green.)

In the widget you found the first try’s bug by luck. A program can find it for sure, by trying everything that could happen. This one makes every list of 10 events, time or button in each place: 2 × 2 × … × 2 = 1,024 lists. It runs each through a machine and keeps the shortest green the cars ever got. (A time event in go is skipped: no time runs out there.)

def first_try(state, event):    if state == 'go' and event == 'button':        return 'stopping'    if state == 'stopping' and event == 'time':        return 'walk'    if state == 'walk' and event == 'time':        return 'hurry'    if state == 'hurry' and event == 'time':        return 'go'    return state def next_state(state, event):    if state == 'fresh' and event == 'time':        return 'go'    if state == 'fresh' and event == 'button':        return 'waiting'    if state == 'go' and event == 'button':        return 'stopping'    if state == 'waiting' and event == 'time':        return 'stopping'    if state == 'stopping' and event == 'time':        return 'walk'    if state == 'walk' and event == 'time':        return 'hurry'    if state == 'hurry' and event == 'time':        return 'fresh'    return state def seconds(state):          # 0: no time limit    if state == 'fresh' or state == 'waiting':        return 8    if state == 'stopping':        return 3    if state == 'walk':        return 6    if state == 'hurry':        return 4    return 0 def cars_green(state):    return state == 'fresh' or state == 'go' or state == 'waiting' def check(machine, start):    shortest = 1000    used = []    for n in range(2 ** 10):           # every list of 10 events        state = start        green = 0        for k in range(10):            if n // 2 ** k % 2 == 0:                event = 'time'            else:                event = 'button'            if event == 'time' and seconds(state) == 0:                continue               # no time runs out here            if [state, event] not in used:                used.append([state, event])            new = machine(state, event)            if event == 'time' and cars_green(state):                green = green + seconds(state)            if cars_green(state) and not cars_green(new):                shortest = min(shortest, green)            if cars_green(new) and not cars_green(state):                green = 0            state = new    print(2 ** 10, 'lists of events,', len(used), 'different situations')    print('shortest green for the cars:', shortest, 's') check(first_try, 'go')check(next_state, 'fresh')

1024 lists of events, 7 different situationsshortest green for the cars: 0 s1024 lists of events, 11 different situationsshortest green for the cars: 8 s

(n // 2 ** k % 2 is digit number k of n in binary, counted from the right and from 0, as in Grade 6’s Zeros and Ones: as n counts from 0 to 1,023, its ten binary digits run through every mix of time and button.)

• The first try failed: in some list of events the cars got 0 seconds of green. Nobody had to think of “press just as it turns green”.
• The fix passed: in all 1,024 lists, the cars always got at least 8 seconds.
• And look at the situations. 1,024 different histories, but the light only ever met 11 different situations: a state and an event. That is the fixed crossing’s whole table: 6 states × 2 events, less the one that can’t happen (time running out in go). However long the light runs, for years, it will never meet a twelfth.

That is the power of a state machine. A light that remembered everything since it was switched on would face a new situation every moment, and nobody could test them all. A state machine faces only the cells of its table, so engineers can check every one and be sure: the cars always get their green, and walkers never get the green figure while cars have green. That is why traffic lights, lifts, railway signals and washing machines are run by state machines.

An all-red state. Add a state called all red (2 seconds, both roads red) between main yellow and side green, and another between side yellow and main green. How many states does the junction have now? Change next_light and seconds and check the timetable.

A beep for people who can’t see the lights. Many crossings beep quickly while people may cross. On the board, add import music and, while the state is walk, music.pitch(1500, 40) each time round the loop.

Remember a press during hurry. In the fixed crossing, a press while the red figure flashes is forgotten: the person must press again. Which new state would remember it, and which arrows does it need?

★ The crossing in blocks

Finish the first-try crossing. It asks for four events, typed as time or button, and must say the state it ends in. One rule is there already (go + button → stopping). Add the other three, then press Test.

★★ Any machine from a table (Python, from Grade 8)

A table can be data instead of ifs: a list of rows, each [state, event, next state]. A pair with no row means stay. Write run_table(table, start, events) that starts in start, takes the events one by one, and gives back the state it ends in.

def run_table(table, start, events):    # table: a list of rows [state, event, next state]    return start gate = [['locked', 'ticket', 'unlocked'], ['unlocked', 'push', 'locked']]print(run_table(gate, 'locked', ['push', 'ticket']))

★★★ The forgotten states (Python, from Grade 8)

When a table is changed by hand, a state can end up with no arrow leading to it, so the machine can never be in it. Write never_reached(table, start) that gives back the names in the table (in either place in a row) that the machine can never reach from start, in alphabetical order (sorted() does that). The rows are as in ★★.

def never_reached(table, start):    return [] night = [['main green', 'time', 'main yellow'], ['main yellow', 'time', 'side green'],         ['side green', 'time', 'side yellow'], ['side yellow', 'time', 'main green'],         ['night', 'time', 'night']]print(never_reached(night, 'main green'))

• Grade 8, Physical Computing: buttons, was_pressed() and a loop that runs for ever.
• Grade 7, True or False: Logic: and in rules like “state is go and the button is pressed”.
• Grade 8, Functions: functions that give back an answer, like next_state.
• Grade 12, The Limits of Computing: state machines that read text, and what they can never do.
• Can a robot get out of any maze? Another machine that follows a short list of rules, with surprising results.
• How does a heater, or a drone, hold steady? Another controller on the micro:bit, this one correcting a little at a time.