Finite State Automata

A abstract machine that have:

• Finite set of states
• Finite set of transitions between states triggered by inputs
• Output haves are determined by states and transitions They are modelled by State Diagram or State Table

FSM Design Steps

1. Draw a State Diagram
2. Derive a State Table from state diagram
3. Assign a flip-flop value configuration to each state (At least ${\log }_2(\text{\# of states})$ flip flops)
4. Redraw State Table with Flip-Flop
5. Derive Combinational Circuit for output and each flip flop input
   • State logic: Figure out next state
   • Output logic: Figure next output

Examples

• Sequence Recognizer FSM Example

Types

Circuit State

• Moore Machine
• Mealy Machine

Determinism

• Deterministic Finite State Automaton
• Non-Deterministic Finite State Automaton