3-1-3 Finite Machines

A Finite State Machine accepts input and processes output.

Examples:

• Traffic Light Control Systems
• Specifiying Computer Language
• Programs for Spell Checking
• Networking Protocols

State Transition Diagrams is used to show a FSM as a picture. Like this:

Finite State Automata (FSA) has a finishing state and only produces yes or no outputs based on the final state.

State 2 is a yes and any other state is a no.

FSM's with outputs:

• Mealy Machine - output on transitions (arrow)

0|A     Input = 0     Output = A

• Moore Machine - output on states (nodes)

C is an output on state 1.

There are two ways to show transitions and states in a FSM.

•  Transition Table - shows transitions and states in table format 



 

• Transition Function - shows transitions and states as a series of functions.

(Input symbol, Current state) -> (Output symbol, Next state)

Deterministic FSA - one and only transition for each input.
Non-Deterministic FSA - multiple transitions for an input.
Halting state - a state with no outputs.
Trigger - input which triggers an action.