s5cs29 finite state machines

This page is mainly about s5cs29 finite state machines

Computers really aren't complicated. They just make lots of simple decisions really quickly. Creating models of computation lies in the theoretical world of the Finite State Machine ...

We are learning ...

What Finite State Machines are

How to represent Finite State Machines as transition tables

How to draw Finite State Machines from transition tables

So that we can ...

Construct simple Finite State Machines without output (technically Finite State Automata)

Construct simple Finite State Machines with output on the transitions - Mealy Machines

Construct simple Finite State Machines with output on the state - Moore machines

Finite State Machines (FSM) are computational models which have a finite (countable) number of states with triggers that change the current state of the machine. You should see parallels between state machines and everyday life (unless you are a computer, in which case, this makes no sense).

Activity 1

Applications first, please!

Before we look at the theory of finite state machines, let's look at some simple, real work applications. I'm not going to give you any hints about the symbols or techniques used to draw these diagrams - I just want you to try to work it out yourself at this stage.

Task 1.1 It's just like the real thing!

Spelling checker

The following trio of diagrams represent homonym checkers - they check the spellings of words that sound the same but mean something different. Can you see how they work? What 'words' will they accept / recognise?

HE(A)RD

GYM/JIM

OAR/OR/ORE

In your notebooks : Look carefully at the diagrams and try to 'spell' each of the homonyms, then draw diagrams for three more sets of homonyms listed on this resource. Can you explain what the 'triangle' and the 'double circle' mean?

Treasure hunt

Download the Treasure Hunt and complete the challenge!

Traffic lights (Technically outside the specification)

Look carefully at the following animation. Can you see how each state of the traffic light is represented by a circle in the diagram and how the 'timer' triggers the light to swap between the states? Notice that, like this animation, the sequence carries on for ever and ever and ever ...

A traffic light controller

This is an alternative version of a traffic light controller where the 'states' of the light indicate the current action which can be performed when the lights are in that state and each state holds it's value whilst in that state.

An alternative traffic light representation

In your notebooks : Copy down the second diagram in your notebooks and try to explain this in your own words.

Ball point pen / light bulb / digital watch (A Level Only)

All these devices have two states with a 'trigger' which flips them between the states. Look ...

Ball point pen

Digital watch

Light bulb. Notice the 'null' output, λ

In your notebooks : Can you think of one more example yourself and draw a diagram like this for it?

Candy bar machine (A Level Only)

And finally, the most complex example (but still not that hard) - the 20p candy bar machine!

Candy bar machine

In your notebooks : Click on the image to enlarge it and print yourself a copy out for your notebooks. This 'machine' only vends one candy bar (worth 20p) and accepts 5p, 10p and 20p coins. I *think* there are 14 different combinations of 5p, 10p and 20p which will get you a candy bar, some giving change and some not. Can you identify all 14 combinations and write them down in your notebooks?

OUTCOME : Lots of examples of Finite State Machines which model real world systems.

Activity 2

Representing FSMs

OK - let's get more formal! There are three 'types' of FSM. You've actually seen all three types in the previous activity, but you might not have realised it.

Finite State Automata (FSA) - they produce no output and do have accepting / goal states. They are often known as recognisers or validators because they are commonly used to validate strings.

Finite State Machines (FSM) - they do produce output but have no accepting state. They are often known as translators because they transform inputs into outputs. There are two types of these ...

- Output generated on the state : Moore machines

- Output generated on the transition : Mealy machines

I would probably copy this diagram into you notebooks if I were you...

Definitions / components

All Finite State Machines have similar components ...

A set of states (or conditions) in which the machine can exist at any one time, usually represented by circles, usually labelled S0, S1, S2, etc;

A single state designated as the 'start' state, labelled with an arrow;

Transitions either from the state to itself (a 'self-transition') or from one state to another;

An 'alphabet' of symbols which they recognise as input, shown as a set (we've met those) between 'curly braces' { };

A 'language' of words composed of valid combinations of the symbols from the alphabet;

Generally represent equivalent regular expressions (which we haven't met, yet).

Additionally, Finite State Automata have one or more 'goal' states which allow the machine will 'accept' or 'recognise' valid words in the language. The word will only be accepted if the machine is sitting in the 'goal' state when the characters in the word are exhausted;

Additionally, Mealy and Moore machines generate 'output' which may, or may not, be within the same alphabet as the input symbols. They do not have 'goal' states, they do not accept or reject inputs (though they will fail if there is no valid input available from the current state), nor can they be non-deterministic (see extension). They are designed to behave as transducers, converting input into output. Mealy machines generate outputs which are dependant on their current state and the input whereas Moore machines (not on the specification, remember) have outputs which are only dependant on their state.

Task 2.1 Better take some notes then!

We've just met lots of key ideas here - it would be pertinent for you to reflect and take some notes on what you have just read. Ask questions, listen to advice. Granted, some of this might not make sense yet (especially the stuff about alphabets, languages and regular expressions) but, when you progress onto A Level, you'll meet these terms again, so, better to be forewarned and forearmed...

It might help to do some research on the web, I find that Google Images is a good place to start (other search engines are available). Remember that Mealy Machines are on the A Level Specification only and Moore Machines are outside the specification at A Level.

OUTCOME : Notes on different types and features of Finite State Machines.

Representing Finite State Machines

There are three equivalent ways of representing a finite state machine ...

State transition diagram

State transition table

Transition function

Representing FSMs

The only thing you will need for the next activity is a piece of software called JFLAP which is available to download from the JFLAP website. You have to register first, but that's free anyway. The JFLAP software is a

.jar

file - you should be able to double click it to open it as long as you have the Java Runtime Environment (JRE) installed.

Task 2.2 Finite state machines in JFLAP

For each of the following exercises, present your work using a combination of screenshots and written explanations. Construct the machines with JFLAP and run them with suitable inputs. Your teacher will show you how.

Finite State Automata

Question 1

Design and build (using JFLAP) a Finite State Automata to represent a machine which merely accepts a single £1 coin (two states). Extend this machine so that it will accept either a single £1 coin or two 50p coins (three states). Run the machine with suitable inputs to test that it works.

Question 2

Draw State Transition Diagrams for the following 5 Finite State Automata, where the input alphabet is {0,1} and accept valid words in a language that...

have exactly two '1's in them (three states);

have at least two '1's in them, but could have more (three states);

begin with, and end with, a ‘1’ and have at least one ‘0’ in them (four states);

contain an even number of 1’s but any number of '0's (even parity checker, two states);

contain an odd number of 1’s and any number of 0’s (odd parity checker, two states);

For each machine, run suitable inputs through it to prove that it operates correctly.

Mealy Machines (A Level Only)

Question 3

What is the output from the Mealy machine shown below when the input is

? Assume that the bits are submitted to the FSM in the order of most significant bit through to least significant bit (i.e. from left to right).

You could try making the machine using JFLAP and running the input through it to help you decide.

Question 4

What is the output from the FSM shown below when the input is

00101100

? Assume that the bits are submitted to the FSM in the order of most significant bit through to least significant bit.

Again, you could try making the machine using JFLAP to test its operation.

Question 5

The table shows the transition table for a finite state machine with outputs, The alphabet is {0, 1}. I've used this example to show you an alternative method of representing the State Transition Table.

Draw the equivalent state transition diagram.

Represent the machine as a transition function as well.

Run the machine with the input 01001001100 and show it's output.

Question 6

Look carefully at the following Mealy Machine. What process does it model?

Notice the 'null' output (using a λ)

You could try making the machine in JFLAP and using it to help you to decide what it does. If you do, run the machine with the following separate inputs ...

Does that help? (Hint: Think logic gates)

They're hiding in the extension activity!

OUTCOME : Plenty of FSAs and FSMs (but only Mealy Machines)

Extension Activities

In classic Computing Café style, here is stuff about things that are not on the specification but that I still think are useful to know. If you think you might get confused, tune out now ...

Moore machines

The diagram below shows a Moore machine. In a Moore machine, the output is solely determined by the state the machine is currently in and has no dependence on the input. The input alphabet for this Moore machine is {a, b} and the output alphabet is {A, B}.

What output will be generated by the following input strings:

aaaba

bbaa

ababab

This FSM has been represented using a Moore machine. Represent it as a Mealy machine (this is hard), assuming that the output from the initial state in the Moore machine is not needed (i.e. your Mealy machine will give the same output as this Moore machine except it will have one less ‘A’ at the start of the output it generates).

Non-determinism

All of the Finite State Automata that we have seen so far have been deterministic. An FSM is deterministic if there is only one possible transition from any state for any given trigger. If there is a choice of transition for any given trigger on any given state then that state is deemed to be non-deterministic because it is not possible to determine which 'route' the FSA will take. For instance...

Note : Non-determinism cannot exist in FSMs with outputs (Mealy and Moore Machines). Why might this be so?

If you really fancy a challenge, try this! The diagram below shows a non-deterministic FSA that has an input alphabet of {0,1} and accepts input strings that have either a 000 or a 111 in them.

Eeek!

Why is this Finite State Machine non-deterministic? Which state gives rise to the non-determinism?

Download the resources sheet and use this to convert this non-deterministic finite state automata (NFA) to a deterministic finite state automata (DFA).

A complicated traffic light

Design a finite state machine to model the following situation ...

“A main road is crossed by a small farm road. There is a detector D which senses if there is a car or tractor on the farm road. If there is no car or tractor on the farm road then the traffic lights will always stay at green on the main road. If there is a vehicle detected on the farm road, the main road lights go from green to amber to red and then the farm road lights will go to green. The farm road lights stay green until either a) no more cars are on the farm road or b) a set time interval has passed. After one of these conditions has been met then the farm road lights will go from green to amber to red and the main road lights will go back to green.”

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT

Last modified: February 14th, 2024

Login

s5cs29 finite state machines