CS 1104 Introduction to Computer Science

COMPILERS AND TRANSLATORS


FINITE STATE MACHINES

A finite state machine is an abstract machine that recognizes strings of characters giving an answer of "YES" or "NO" based on transitions between "states" in the machine, the transitions being chosen on the basis of the next character in the string.

ALGORITHM

  1. Commence at the "start state" and at the first character in the string to be analyzed;

  2. Repeat:
    • Transition to the next state by choosing the exiting arc that is labelled with that character;
    • Move on to the next character in the string;
    • Until the string is empty or there is no applicable transition;

  3. If the string is empty AND the current state is an ending state report "YES"

  4. else report "NO".

 




[TOC]


© J.A.N. LEE
Last Updated 2001/04/09