Notes on Finite State Machines and DFAs

Key Terms

• Machine and Automaton: Used interchangeably; plural of automaton is automata.
• Finite State Machine (FSM): Simplest computational model; has limited memory but can perform various functions.

Example of a Finite State Machine

• Oven Controller:
  • States: On and Off.
  • Start State: Off (q0).
  • Transition:
    • Press button:
      • Off (q0) ➜ On (q1)
      • Press again: On (q1) ➜ Off (q0).

Constructing a More Complex Machine

Heat Wave Detector

• Definition: A heat wave occurs if max temperatures reach 45°C for two consecutive days.
• States:
  • Start State: q0 (temperature ≤ 45°C)
  • State Q1 (first day > 45°C)
  • Accept State Q2 (second consecutive day > 45°C).

Transitions

• From q0:
  • If temperature > 45°C ➜ Transition to Q1.
  • If temperature ≤ 45°C ➜ Remain in q0.
• From Q1:
  • If temperature > 45°C ➜ Transition to Q2.
  • If temperature ≤ 45°C ➜ Back to q0.
• From Q2: Remain in Q2 (heat wave already occurred).

Representation

• Inputs:
  • Use 1 for temperature > 45°C.
  • Use 0 for temperature ≤ 45°C.
• Machine: Recognizes strings with two consecutive 1s (heat wave).
  • Language of the Machine: Set of strings it accepts (e.g., 11, 110, 0110).

Deterministic Finite Automaton (DFA)

• Definition: A DFA is deterministic; for every input symbol, the next state is predictable.
• Components of DFA (5-tuple):
  1. Q: Finite set of states (e.g., {q0, q1, q2}).
  2. Sigma: Alphabet (set of symbols, e.g., {1, 0}).
  3. Delta: Transition function (rules for state transitions based on input).
  4. Start State: q0 (initial state).
  5. F: Set of accept states (e.g., {q2}).

Regular Languages

• A language is regular if recognized by a finite automaton.
• Example: Language of strings containing two consecutive 1s is regular.

Summary

1. DFAs are 5 tuples represented with state diagrams.
2. Machine ACCEPTS the input string if the last symbol leads to an ACCEPT state.
3. The language of a machine is the set of all accepted strings.
4. Languages recognized by finite automata are regular languages.

Final Note

• Designing DFAs is a creative process that takes time and practice.