Finite State Machines: An Introduction to FSMs and their Role in Computer Science

I. Introduction

State machines serve as fundamental models for understanding and describing the behaviour of systems in computer science. At their core, state machines provide a structured approach to representing a system’s various states, the transitions between them, and the events triggering them. This article aims to elucidate the concept of state machines, exploring their significance in computer science and their diverse applications across different domains. Finite State Machines are also an essential component for understanding Universal Turing Machines (UTM), as the latter consists of two parts: an FSM and an infinite tape.

Other articles in the series:

A. Overview of State Machines

A state machine, also known as a finite state machine (FSM), is a mathematical model used to describe the dynamic behaviour of systems through a finite number of states, transitions between these states, and actions associated with these transitions. This model provides a clear and concise representation of how a system responds to different inputs or events, making it invaluable in software design, system modelling, and problem-solving.

B. Importance in Computer Science

State machines play a pivotal role in computer science due to their versatility and applicability in various areas:

II. Fundamentals of State Machines

State machines serve as fundamental models for describing the behaviour of systems in computer science. This section will delve into the basic principles of state machines, including their components and types.

A. Definition of State Machines

A state machine is a mathematical model that represents the dynamic behaviour of a system through a finite number of states, transitions between these states, and actions associated with these transitions. At any given moment, a system is in a particular state, and transitions occur in response to events or inputs.

B. Basic Components

State machines consist of several key components:

C. Other Types of State Machines

Besides Finite State Machines, several other types exist, each with its own characteristics and applications:

Understanding these fundamental components and types of state machines lays the groundwork for exploring their applications and implementations in computer science.

D. Deterministic vs. Nondeterministic FSMs

Finite State Machines can be categorized as deterministic or nondeterministic based on their behaviour:

IV. State Tables

State tables are another way of describing state machines. They tabulate the different stimuli, responses, and states the machine can take. In electronic implementations of state machines, transitions are controlled by clocks with discrete outputs. Describing the state machine at discrete time intervals makes sense in such an implementation. State tables describe the FSM’s future states and responses regarding its current states and stimuli.

We can model the state machine as follows:

Where:

The state table describes the mapping between the different inputs and outputs for F and G. The state table of F is:

This table shows that if the state machine receives an input of S2 while being in state Q1, it will transition to state Q2. There is no possibility of transitioning if it receives stimulus S1 while in state Q1, as the state table does not allow this.

The state table of G is:

This table shows that if the state machine receives an input of S2 while being in state Q1, the output or response will be R2.

V. What Problems Can Finite State Machines Solve?

Finite state machines (FSMs) are computational models representing and controlling systems with discrete states and transitions between these states. They are widely applicable and can solve various problems across different domains. Here are some problems that finite-state machines can effectively address:

Finite state machines provide a versatile framework for modelling and solving problems across diverse domains, from hardware design and software development to system control, automation, and beyond. Their simplicity, expressiveness, and formalism make them powerful computational modelling and problem-solving tools.

VI. A Pattern-Matching FSM

The graph below shows the different states, transitions, stimuli and outputs of a finite state machine (FSM) that takes two input strings, S and P and looks for P in S. The machine should exit when the first occurrence of P is found in S, or when the end of the string S is reached.

The FSM starts in the Start position with P(0) and S(0). S(0) is not shown because it’s a preparatory state that the FSM, by definition, will never return to. That is why the diagram does not show it to avoid cluttering. However, we must revisit state P(0) if the search at position m (say) does not match, and we must start over.

Next, one character from S is read, and both characters S(n) and P(k) are compared. If they match, both are incremented. If they don’t match, the pattern position is reset, and the search continues from the next position in S. The FSM exists in two cases. The first case is when the pattern matches, while the second case is when the string end is reached.

The Python code that implements this state machine can be found in the appendix.

VII. What Problems Are Not Adequate for Finite State Machines?

In his lectures on computation, Richard Feynman tries to solve the parenthesis-checking problem with a finite state machine. A string of parentheses is given as input, and the FSM should check if the string is balanced, meaning every open parenthesis has a closing one in the correct order. Since the problem requires a solution for strings of arbitrary lengths, Feynman argues that an arbitrarily large number of states is required for a state machine to work. Hence, for some problems, such as parenthesis-checking, the finiteness of the FSM makes it inadequate.

There are certain problems that FSMs are not well-suited to solve due to their inherent limitations. Here are some examples:

While finite state machines are versatile models for representing and solving certain problems, they have limitations when handling complex decision-making, dynamic data structures, recursion, continuous systems, context-sensitive behaviour, probabilistic behaviour, and other advanced computational tasks. It’s important to choose the appropriate modelling technique based on the nature and requirements of the problem.

VIII. Advantages of Using Finite State Machines

Finite state machines (FSMs) offer several advantages in programming, computer science, and problem-solving in general:

IX. Appendix A: Python Code for Pattern-Matching FSM

The following code shows how a pattern-matching FSM can be implemented in Python. The FSM has three states: PATTERN_READ, STRING_READ, ERROR, and MATCHING and runs iterations capped by the candidate string length.

class SearchFSM:

  def __init__(self, pattern):
    self.pattern = pattern
    self.state = "PATTERN_READ"
    self.pattern_index = 0
    self.string_index = 0

  def transition(self, char):
    # PATTERN_READ -> ERROR, MATCHING, STRING_READ
    if self.state == "PATTERN_READ":
      if self.pattern_index == len(self.pattern):
        self.state = "ERROR"  # Handle reaching end of pattern unexpectedly
      elif char == self.pattern[self.pattern_index]:
        self.pattern_index += 1
        self.state = "MATCHING"
      else:
        self.state = "STRING_READ"

    # STRING_READ -> PATTERN_READ
    elif self.state == "STRING_READ":
      self.string_index += 1
      self.state = "PATTERN_READ"

    # MATCHING -> STRING_READ
    elif self.state == "MATCHING":
      if char == self.pattern[self.pattern_index]:
        self.pattern_index += 1
        if self.pattern_index == len(self.pattern):
          return True  # Pattern found!
      else:
        self.state = "STRING_READ"
        self.pattern_index = 0  # Reset pattern matching
    else:
      raise Exception("Invalid state encountered")
    return False  # Pattern not found yet

def search(pattern, string):
  fsm = SearchFSM(pattern)
  for char in string:
    if fsm.transition(char):
      return True
  return False  # Pattern not found in the string

# Example usage
pattern = "ABC"
string = "ABCCDEF"
if search(pattern, string):
  print("Pattern found!")
else:
  print("Pattern not found.")

# Example usage
pattern = "CCD"
string = "ABCCDEF"
if search(pattern, string):
  print("Pattern found!")
else:
  print("Pattern not found.")

# Second usage
pattern = "123"
string = "ABCCDEF"
if search(pattern, string):
  print("Pattern found!")
else:
  print("Pattern not found.")

X. References

• Feynman Lectures on Computation, by Richard Feynman, 1996
• The Annotated Turing, by Charles Petzold, 2008
• The Feynman Processor, by Gerard J. Milburn, 1999