Welcome to the World of Finite State Machines!
In this chapter, we are diving into the Theory of Computation to explore Finite State Machines (FSMs). Don't let the name intimidate you! At its heart, an FSM is just a simple "logic map" that shows how a system changes from one situation to another based on what happens to it.
Understanding FSMs is vital because they are the foundation for how computers process language, how stoplights work, and even how non-player characters (NPCs) in video games decide what to do next. By the end of these notes, you'll be able to draw and read these "logic maps" like a pro!
What is a Finite State Machine?
A Finite State Machine is a mathematical model of computation. Let’s break that name down to see what it really means:
1. Finite: This means the machine has a limited, fixed number of possible conditions it can be in. It can't have infinite options.
2. State: This is the "condition" or "status" of the machine at a specific moment.
3. Machine: A system that takes an input and, based on its current state, decides which state to move to next.
Did you know? Your microwave is a simple FSM! It has states like Idle, Cooking, and Paused. Pressing the "Start" button is an input that causes a transition from Idle to Cooking.
Key Terms to Remember
• State: A specific condition (e.g., "Locked" or "Unlocked").
• Transition: The movement from one state to another.
• Input: The event or trigger that causes a transition (e.g., a coin being inserted).
• Initial State: Where the machine starts.
• Accepting (Final) State: A state that represents a "successful" or "valid" result.
Visualizing FSMs: State Transition Diagrams
The most common way to show an FSM is using a State Transition Diagram. This is a visual map using specific symbols. Don't worry if this seems tricky at first—once you know the symbols, it's just like reading a flow chart!
The Anatomy of a Diagram
• Circles: These represent the States. Inside the circle, we usually write the name of the state (e.g., \(S_0, S_1\)).
• Arrows: These are the Transitions. They show which way the machine moves.
• Arrow Labels: The text on the arrow is the Input required to make that move.
• The "Start" Arrow: An arrow pointing into a circle from "nowhere" identifies the Initial State.
• Double Circles: A circle inside another circle represents an Accepting State. If the machine ends here after all inputs are processed, the input sequence is Accepted.
A Real-World Example: A Simple Gate
Imagine a security gate that is usually Locked.
1. If you push it while it's Locked, it stays Locked.
2. If you put in a Coin, it moves to the Unlocked state.
3. If you Push it while it's Unlocked, it opens and then moves back to Locked.
In this example, Locked and Unlocked are the States. Coin and Push are the Inputs.
Quick Review Box: Remember the Double Circle! It’s the most common thing students forget. It tells us that the machine has reached a "valid" conclusion.FSMs Without Output
In the AQA AS Level syllabus, we focus specifically on FSMs without output (also known as Finite State Automata). These machines have one simple job: to decide if a string of symbols is Accepted or Rejected.
How to Trace an FSM (Step-by-Step)
To determine if a sequence (like "1101") is accepted, follow these steps:
1. Start at the Initial State (look for the arrow from "nowhere").
2. Take the first symbol of your input string.
3. Follow the arrow that matches that symbol to the next state.
4. Repeat for every symbol in the string.
5. Check your final position: If you are standing in a Double Circle state when you run out of symbols, the string is Accepted. If not, it is Rejected.
Common Mistake to Avoid
The "Dead End" Trap: Sometimes a state won't have a transition for a specific input (e.g., you are in State A, the input is '1', but there is no '1' arrow). In many simple FSMs, if there is no valid move, the machine "crashes" and the input is immediately Rejected.
Key Takeaway: FSMs without output are like "Acceptance Detectors." They only care if you end up in the right place (the double circle).The State Transition Table
Sometimes, drawing a diagram gets messy if there are too many states. That's where the State Transition Table comes in. It’s the exact same information, just organized in a grid!
How to Read/Create a Table
• The Rows represent the Current State.
• The Columns represent the Input Received.
• The Cells tell you the Next State.
For example, a table might look like this:
Current State | Input: 0 | Input: 1
------------------------------------
S0 (Start) | S0 | S1
S1 (Final) | S0 | S1
This table tells us: "If you are in S0 and receive a 1, move to S1."
Memory Aid: The "IF-AND-THEN" Rule
To remember how to use a table, just say: "IF I am in this state AND I get this input, THEN I go to that state."
Summary of Theory of Computation: FSMs
• FSMs are models of systems with a finite number of states.
• Transitions are triggered by inputs.
• State Transition Diagrams are visual maps; State Transition Tables are grids.
• Initial State = arrow from nowhere. Accepting State = double circle.
• For FSMs without output, the machine only accepts a string if it ends in an Accepting State.
Don't worry if this feels abstract! The best way to master FSMs is to practice drawing them for simple tasks, like a machine that only accepts binary numbers ending in '1'. You've got this!