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.
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.**F**inite**S**tate**A**utomata (**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.**F**inite**S**tate**M**achines (**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 / componentsAll 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.
Representing Finite State MachinesThere 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.
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 machinesThe 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-determinismAll 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 lightDesign 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.”
END OF TOPIC ASSESSMENT |