Real-World Finite Automata

What is a Finite Automaton?

At its core, a finite automaton (also called a finite state machine or FSM) is a mathematical model of a machine that can be in exactly one of a finite number of conditions, or states, at any given time. The machine changes from one state to another in response to an input.

Think of it as a machine with a very limited memory. It only knows what state it is currently in; it doesn't remember the sequence of events that led it to that state.

This might sound abstract, so let's make it concrete with some familiar examples.

Example 1: The Vending Machine

Vending machines are a classic illustration of a finite automaton. Their logic is based on tracking the amount of money inserted and dispensing an item once the correct amount is reached.

To see this in action, please watch the following video from Computerphile. It does an excellent job of breaking down this concept.

As the video explains, the machine operates as follows:

• States: Each possible amount of money collected is a state (e.g., 0p, 5p, 10p, 15p, ...).
• Start State: The machine begins in the '0p' state.
• Inputs: The coins you can insert (e.g., a 5p coin, a 10p coin).
• Transitions: When an input (a coin) is received, the machine moves from its current state to a new one. If it's in the '10p' state and receives a '5p' coin, it transitions to the '15p' state.
• Final State: The '25p' state is a special state. Once reached, the machine completes its task (dispensing a ticket).

A crucial aspect of this model is its lack of memory. Let's explore that idea a bit more.

This is a key takeaway: if the machine is in the '15p' state, it has no memory of how it got there. It could have been three 5p coins, or a 10p followed by a 5p. All that matters is the current state.

We can visualize this behavior using a state diagram. The diagram below shows a simple vending machine. The circles represent states, and the arrows, labeled with the input that causes the change, represent transitions.

Example 2: The Traffic Light

Your interest in traffic light controllers is a perfect fit here. A traffic light is another excellent real-world system that operates as a finite automaton.

For a simple traffic light, the model is straightforward:

• States: There are three states: Green, Yellow, and Red.
• Input: The main input is a signal from a timer, indicating that a certain amount of time has passed.
• Transitions: The machine cycles through its states based on the timer input. A timer_expires input in the Green state causes a transition to the Yellow state, and so on.

The diagram below illustrates this cyclical process.

Example 3: The Coin-Operated Turnstile

Our final example is a coin-operated turnstile, like one you might find at a subway station. This is a very simple but clear example of a system with only two states.

Please read the following text, which describes how a turnstile works as a finite state machine.

Let's summarize the turnstile FSM:

• States: Locked and Unlocked.
• Inputs: coin (a coin is inserted) and push (someone pushes the arm).
• Transitions:
  • In the Locked state, a coin input transitions the machine to Unlocked. A push input does nothing.
  • In the Unlocked state, a push input transitions the machine back to Locked. An additional coin input does nothing.

This example is particularly useful for showing that not every input necessarily causes a state change. The machine's response to an input depends entirely on its current state.

Bringing It All Together

Across these different examples—the vending machine, the traffic light, and the turnstile—we can see a common structure. Each system can be described by:

1. A finite set of states (e.g., {Locked, Unlocked}, {Red, Yellow, Green}).
2. A set of allowed inputs (e.g., {coin, push}, {timer_expires}).
3. A set of rules for transitions between states based on inputs.
4. A clearly defined start state (e.g., '0p collected', 'Locked').
5. In some cases, one or more final or accept states that signify the completion of a task (e.g., '25p collected').

These five elements are the fundamental building blocks of a finite automaton.

To broaden your perspective, other common applications include elevator controllers, combination locks, and even simple syntax checkers in a text editor (e.g., checking for balanced parentheses).

Conclusion

In this lesson, we have built an intuitive foundation for understanding finite automata. We've seen that these are models of simple machines that operate by moving between a finite number of states in response to inputs. By looking at real-world examples like vending machines, traffic lights, and turnstiles, we've identified the core components that define their behavior.

Key Takeaways:

• A finite automaton (or finite state machine) is a computational model with a limited number of states.
• It transitions from one state to another based on inputs.
• It is "memoryless" in that it only knows its current state, not the history of how it arrived there.
• Many everyday devices can be modeled as finite automata.

In our next lesson, we will begin to formalize these ideas. We will take the informal components we discussed today—states, inputs, transitions, start state, and accept states—and learn how to express them using a precise mathematical definition.