### CS29 : I want Moore 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
• To 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).

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.

 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 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, 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 { };
• 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
Click to enlarge

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 machinesFor 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 AutomataQuestion 1Design 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 2Draw State Transition Diagrams for the following 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 3What is the output from the Mealy machine shown below when the input is `001011`? 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 4What 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 5The 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 6Look 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 ...`00``01``10``11`Does that help?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.

• Why is this Finite State Machine non-deterministic? Which state gives rise to the non-determinism?
• Download the resources sheet Converting NFA to DFA.docx 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 ...