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.

Explore the fundamentals of finite-state machines with outputs through this quiz. Understand the different types and applications of these models critical to computer science. Enhance your knowledge of machine modeling as discussed in the Theory of Computation class.