Computer Science (9645) | Finite state machines (FSMs)

Understanding Finite State Machines (FSMs)

Hello! Welcome to the section on the Theory of Computation. This area of Computer Science looks at what problems can be solved by computers and how we can model these processes. Don't worry if this sounds abstract—we are going to start with the simplest, most relatable model of computation: the Finite State Machine (FSM).

You interact with FSMs every single day, whether you realise it or not! They are the mathematical bedrock for how simple systems behave, from traffic lights to password validation.

What is a Finite State Machine (FSM)?

A Finite State Machine (FSM), sometimes called a Finite Automaton (FA), is a mathematical model used to design systems that only have a limited, fixed number of possible operational conditions or "states."

Analogy: Think of a traffic light. It can only be in one of three states: Red, Red/Amber, or Green. It cannot be Red and Green at the same time. The change between these states is triggered by an input (like a timer).

Core Components of an FSM

An FSM has four main required components:

• States: A finite set of conditions or configurations the machine can be in.
• Start State: The initial state of the machine when it begins operation.
• Input Alphabet: A finite set of symbols (or events) that the machine can receive. These trigger movement between states.
• Transitions: Rules that specify how the machine moves from one state to another based on the received input.

Key Takeaway: FSMs are simple machines that are defined by a fixed, finite number of states and rules for moving between them. They are memoryless (they only care about the current state and the current input).

Representing Finite State Machines

We have two main ways to describe an FSM formally: using diagrams (visual) and using tables (structured). You must be able to draw and interpret both.

1. State Transition Diagrams

This is the most intuitive way to visualise an FSM.

• States are drawn as circles or nodes.
• The Start State is indicated by an arrow pointing to it from nowhere.
• Transitions (movements between states) are drawn as arrows connecting the states.
• Each transition arrow is labelled with the input symbol that triggers that move.
• If the FSM is used for recognition (like validating a password), we might use Accept/Halting States, often represented by a double circle.

Example: A simple FSM that checks if an input string contains two consecutive '1's.

If State A is the start state, and State C is the accepting state, the arrow from A to B might be labeled '1', and the arrow from B to C might also be labelled '1'.

2. State Transition Tables (The Formal View)

A State Transition Table shows the same information as a diagram but in a formal, tabular format. This is often better for checking every possible scenario.

• Rows usually represent the Current State.
• Columns usually represent the Input Symbol.
• The entry in the table specifies the Next State.

FSMs with Output: Mealy Machines Only

The syllabus requires you to understand FSMs that produce an output. Crucially, you only need to know about Mealy Machines.

In a Mealy Machine, the output is generated during the transition.

Output depends on: (Current State) AND (Input Received)

Memory Aid: Think 'M' for Movement. Mealy outputs occur on the Movement (transition).

When labelling transitions on a Mealy diagram or table, the label will look like this:

Input / Output

Example Transition: If the FSM is in State S1 and receives input 'a', it moves to S2 and outputs '0'.
Diagram Label: a / 0

Key Takeaway: FSMs can be modelled visually (diagrams) or formally (tables). For machines with output, remember the Mealy rule: Output is tied to the specific input/transition.

Regular Expressions and Regular Languages

Finite State Machines are a computational model. Regular Expressions (REs) are a way to describe the set of strings (the language) that those FSMs can recognise. They are incredibly useful in programming for validating data, searching text, and checking input formats.

What is a Regular Language?

A Regular Language is any set of strings that can be defined by a Regular Expression or recognised by an FSM.

Did you know? Nearly all modern programming languages (Python, Java, etc.) use regular expressions for pattern matching!

Metacharacters: The Building Blocks of Regular Expressions

REs use special symbols (metacharacters) to describe patterns concisely. You must be familiar with the following symbols:

Repetition and Optionality

• * (Kleene Star): Matches zero or more repetitions of the preceding element.
  • Example: A* matches "", "A", "AA", "AAA", etc.
  • Memory Aid: The star means "totally optional, maybe many times."
• + (Kleene Plus): Matches one or more repetitions of the preceding element.
  • Example: A+ matches "A", "AA", "AAA", etc., but not "".
  • Memory Aid: The plus sign means "at least one."
• ? (Optional): Matches zero or one repetition (the preceding element is optional).
  • Example: Colou?r matches both "Color" (US spelling) and "Colour" (UK spelling).

Grouping and Selection

• | (Alternation or OR): Matches either the expression before or the expression after the symbol.
  • Example: Cat|Dog matches either the string "Cat" or the string "Dog".
• () (Grouping): Used to group regular expressions together so that a metacharacter (like * or +) applies to the entire group.
  • Example: (AB)+ matches "AB", "ABAB", "ABABAB", etc. (If we wrote AB+ it would match "A" followed by one or more "B"s).

Character Classes

Character classes allow you to specify a set of characters that can match at a specific position.

• Direct Selection: [CH] matches either the character 'C' or the character 'H'.
• Range Selection: [A-Z] matches any single character that is an uppercase letter between A and Z (inclusive).

Common Mistake to Avoid: Make sure you understand the difference between * (zero or more) and + (one or more). If the language requires a character to be present at least once, use +.

Key Takeaway: Regular expressions are powerful pattern descriptions. Learn the metacharacters (especially *, +, ?, |) as they are essential for defining regular languages.

The Relationship between FSMs and Regular Expressions

This is one of the most important theoretical concepts in this section:

Regular expressions and FSMs are equivalent ways of defining a regular language.

This means that if you can draw an FSM to recognise a pattern, you can definitely write a regular expression to describe that pattern, and vice versa.

Applying the Equivalence

In an exam scenario, you might be asked to perform a translation between these two models:

1. FSM to Regular Expression (RE)

You need to trace the paths through the FSM that lead from the start state to an accepting state, using the metacharacters to represent loops and choices.

• Task: Write an RE to describe the language recognised by a given FSM.
• Example FSM: Recognises an even number of '1's (Starts at State S0, stays at S0 on input '0', moves to S1 on '1'. Moves back to S0 on '1', stays at S1 on '0'). S0 is the accept state.
• Corresponding RE: (0*10*1)*0*
  • Explanation: Any number of 0s (0*), followed by a pair of 1s separated by any number of 0s (10*1). This whole pattern must repeat zero or more times (...) * to ensure an even count of 1s, ending with any number of 0s (0*).

2. Regular Expression to FSM Design

You need to design the states and transitions necessary to accurately implement the logic defined by the RE.

• Task: Design an FSM to recognise the same language as a given RE.
• Example RE: A(B|C)* (Matches an 'A', followed by zero or more sequences of 'B' or 'C').
• FSM Design Steps:
  1. Create a Start State (S0).
  2. Transition from S0 must be 'A' to reach the next logical state (S1).
  3. S1 must handle the (B|C)* part. Since this means 'B' or 'C' zero or more times, S1 must be the final Accept State, and it must loop back to itself upon receiving input 'B' or 'C'.
  4. You would draw arrows from S1 back to S1 labelled 'B' and 'C'.

The Significance

The key takeaway here is knowledge of the Regularity Principle:

A language is regular if and only if it can be recognised by an FSM. Since FSMs and REs are equivalent, this means if you see an RE, you know a simple FSM can process it.

Key Takeaway: FSMs and Regular Expressions are interchangeable. They define the same class of simple languages—the Regular Languages. You must practice converting between the two forms.