SHARE
black pug background
Advertisement

A Labelled Transition System (LTS) is representation of some computational process. It’s an easy way to picture a computer program, algorithm or process.

These diagrams are especially useful if you are trying to solve riddles and brain-teaser games. They enable you to see all possible moves, and things that you might have missed on your first attempts to beat the game.

Parts of A Labelled Transition System

A labelled transition system is made up of 3 important parts.

  1. The state (usually a circle or elliptical shape containing information)
  2. The actions (the arrows from each shape; they usually have something next to them to tell you what is happening)
  3. The information (what goes in the state, or by the actions)

To get from one state to another state, and action must be performed. Take a look at the lamp example next to further understand.

Labelled Transition System Examples

How A Lamp Works

The lamp has 3 states:

  1. An On state
  2. An Off state
  3. A Broken state

There are also 3 actions:

  1. Pull the switch
  2. Break the lamp
  3. Reset the lamp

You can see all of these depicted in the diagram below.

labelled transition system for an electric lamp
Here you can see the function of an electric lamp!

As the lamp process “executes”, you can follow the arrows to see what the next choice is.

If you start at the On position, you have two choices:

  1. Break the lamp
  2. Pull the cord

Both choices lead to the lamp being in the Off state. Breaking the lamp will also lead to failure when you try to pull the switch again while you are in the broken state.

Solving The “Man, Cabbage, Goat and Wolf Game”

You’ve probably played this game at some point in your life. If you haven’t then play the video below to see how it is solved.

The game is rather simple.

[embedyt] http://www.youtube.com/watch?v=uGdCFOWtLpI[/embedyt]

The aim is to get the everyone to the other side without anything being eaten.

The game is easy enough for most people, however, labelled transition systems make solving these problems easier-ish. Although the image below might look pretty hectic, it is in fact very simple.

labelled transition system example for man cabbage wolf game
Don’t be afraid of this diagram, it’s really simple.

The capital letters denote the position of each thing relative to the colon (:). The colon is the river. The letter next to each arrow tells you which thing is moving.

LTS States

Start at the “MWGC:” point right at the top. This is the start state. In this state the Man, Wolf, Goat and Cabbage are all on the left side of the river (:). So they’re all safe, for now.

The purple circles are the dangerous states:

  1. The Goat eats the Cabbage
  2. The Wolf eats the Goat

If any of these states are reached then you will lose the game!

LTS Actions

There are 4 possible actions:

  1. m (man crosses river)
  2. w (wolf crosses river accompanied by the man)
  3. g (goat crosses river accompanied by the man)
  4. c (cabbage crosses river accompanied by the man)

wolf eating cabbage
This wolf doesn’t want your cabbage!

Go down from state “MWGC:” to state “WC:MG”. The can see that the “g” action was performed. This means the goat and man crossed the river, leaving the wolf behind with the cabbage. Wolves don’t eat cabbage.

As you work all the way down the LTS example, you see that eventually everyone gets to the other-side safely. You can also see the shortest solution too.Goat, Man, Wolf, Goat, Cabbage, Man then Goat!

Being able to see every possible situation gives you a competitive advantage in any game! Next we’ll see how we can use LTS to solve the Die Hard water jug game.

Solving The “Die Hard” Water Jugs Riddle

To save a bomb going off in the middle of a city, Bruce Willis and Samuel L Jackson had to solve a riddle.

die hard water jug riddle

Watch The Jugs Riddle Scene

[embedyt]https://youtu.be/BVtQNK_ZUJg[/embedyt]

How To Solve The Riddle With LTS

Imagine that Jug A is 5 gallons, and Jub B is 3 gallons. Then there are 6 possible moves.

Either you can fill the jug, empty the jug on the floor or empty one jug into another.

LTS Actions

From the LTS diagram we have see all of the actions of this puzzle. There are also conditional statements. You obviously can’t empty an empty jug.

  1. Fill Jug A 
  2. Fill Jug B
  3. Empty Jug A
  4. Empty Jug B
  5. Pour A into B
  6. Pour B into A

Now the trick is in the “emptying the jug on the floor”:“emptyA” and “emptyB”.

If we draw out the LTS diagram then we get a simple 7-step solution. The ordered pairs (x,y) denote the amount of water in each jug. Jug A on the left, and Jub B on the right.

And finally, the bomb is turned off!

How To Solve the Puzzle
  1. Fill Jug A
  2. Pour A into B
  3. Empty B
  4. Pour A into B
  5. Fill A
  6. Pour A into B
  7. Empty B

Anyway, that’s all for now. Leave a comment in the box below if you have any questions or feedback.

Until next time, Josh.

Advertisement