3-1-3- Finite State Machines

accepts an input and processes an output. They are used extensivley in computer science applications such as:

• Traffic light control systems
• Specifying a computer language
• Programs for spell checking
• Networking protocols

State Transition Diagrams:A State Transition Diagram is used to show an FSM as a picture.

Finite State Automata:A type of FSM that has a finishing state and produces only a YES or NO output based on the final state.

e.g. State 2 = YES, other state = NO

(in example: input 0101; output NO--- input 110; output YES)

FSM With Outputs:

Mealy Machines- the outputs are on the transitions/ arrows (L=Lines)

Moore Machines- the outputs are on the circles/states (O=Circles)

Mealy Machine
example: O|A- input is 0, output is A.
(input=110, output=BBA)

Moore Machine:example: C is the output on state 1.

(input=110, output=CBCA)

Transition Table:

Shows the states and transitions in an FSM in a table format:

Current State | S1   S1   S2   S2   S3   S3

            Input  | 0      1     0      1    0      1 

    Next State | S2   S3   S3   S3   S1   S1

          Output | A    B     C     B     C     B

                                                                Transition FunctionShows the states and transitions as a series of functions.

(input symbol, current state) (output symbol, current state)

(0, S1) -> (A, S2)

(1, S1) -> (B, S3)
etc.

Deterministic and Non-Deterministic FSA

Deterministic- only one transition arrow for each input.

Non-deterministic- has multiple transitions for one input. So there is more than one possible route around the state transition diagram.

TERMINOLOGY:

Halting State - a state with no output.

Trigger - an input which triggers an action.