Theory of Computation Lecture 9

Finite-State Machines with Output

• Finite-state machines (FSMs) are models that represent various technologies in computing, including components found in computers.
• They consist of a finite set of states, an initial state, a designated input alphabet, and a transition function that maps state-input pairs to new states.
• Common applications include spell checking, grammar checking, text indexing/searching, and speech recognition.

Formal Definition

• An FSM with output is defined as M = (S, I, O, f, g, s0), where:
  • S: Finite set of states
  • I: Finite input alphabet
  • O: Finite output alphabet
  • f: Transition function defining state transitions
  • g: Output function mapping state-input pairs to outputs
  • s0: Initial state

Representation of Finite-State Machines

• FSMs can be represented using state tables, showing states, inputs, and associated outputs.
• State diagrams are graphical representations using circles for states and arrows for transitions, labeled with input-output pairs.

Input and Output Relations

• The FSM processes an input string symbol by symbol, transitioning through states based on the transition function.
• Each transition generates an output, leading to an output string that corresponds to the input string through a defined output function.

Examples of Finite-State Machines

• Unit-Delay Machine:

  • Delays the output string by one time unit through three states (s0, s1, s2).
  • State s1 remembers if the previous input was 1; s2 remembers if it was 0.
  • Outputs 0 for initial transition and reflects the delayed input thereafter.

• Error Detection Machine:

  • Detects three consecutive 1s to indicate a transmission error, reflecting output accordingly.
  • Utilizes three states to track sequences of 1s:
    • State s0: previous input was not 1.
    • State s1: previous input was 1, but not two consecutive 1s.
    • State s2: two previous inputs were 1s.
  • An input of 0 resets the machine to state s0.

Limitations of Finite-State Machines

• FSMs have limited memory capabilities due to a finite number of states.
• They cannot perform tasks requiring unbounded memory, hindering their effectiveness for certain applications.