Lecture Notes: Finite State Machines

Introduction to Finite State Machines (FSM)

• Also known as finite automata.
• Divided into two broad categories:
  • Finite Automata with Output
    • Mealy Machine
    • Moore Machine
  • Finite Automata without Output
    • Deterministic Finite Automata (DFA)
    • Non-deterministic Finite Automata (NFA)
    • Epsilon Non-deterministic Finite Automata (Epsilon NFA)

Focus on Deterministic Finite Automata (DFA)

• DFA stands for Deterministic Finite Automata.

Key Properties of Finite State Machines

1. Simplest model of computation.
2. Limited memory.

Structure of DFA

• States: Represented by circles (e.g., A, B, C, D).
• Transitions: Directed edges (arrows) between states, labeled with inputs (0 or 1).
  • Example transitions:
    • State A to B on input 1.
    • State A to C on input 0.
    • State C to D on input 1.
• Initial State: Indicated by an arrow coming from nowhere pointing to the state (e.g., A).
• Final State: Represented by a double circle (e.g., D).

Formal Definition of DFA

• Defined using five tuples: (Q, Σ, Q₀, F, δ)
  • Q: Set of all states
    • Example: {A, B, C, D}
  • Σ: Set of inputs
    • Example: {0, 1}
  • Q₀: Initial state
    • Example: A
  • F: Set of final states
    • Example: {D}
  • δ (Delta): Transition function mapping from Q × Σ to Q.

Transition Function Table

• For inputs 0 and 1 with states A, B, C, D:

Overview of Transitions

• From State A:
  • Input 0 ➔ State C
  • Input 1 ➔ State B
• From State B:
  • Input 0 ➔ State D
  • Input 1 ➔ State A
• From State C:
  • Input 0 ➔ State A
  • Input 1 ➔ State D
• From State D:
  • Input 0 ➔ State B
  • Input 1 ➔ State C

Conclusion

• Understanding the structure and function of DFA is crucial for studying computation.
• Further examples will be explored in upcoming lectures.