An Example-Based Introduction to Finite-State Machines

If you are enrolled in a CS program or happen to be fascinated by the aspects of theoretical Computer Science, you would most likely be introduced at some point to finite-state machines. It also might be the case that you were overwhelmed by their principles. But considering how ubiquitous this simple computational model is, it's time to unravel its mysteries once and for all!

An everyday example

It's Saturday morning. You'll wake up early today to enjoy the benefits of a morning walk, along the seaside. The clock rings at 8 am. Your eyes open, but your body feels quite relaxed under the sheets. For the next few moments, the motion of the second hand in the alarm clock is ticking rhythmically in your ears.

You finally decide to leave the bed and get ready. It's time to go, you're inserting the key in the front door to lock it, but the key does not match. You're using the wrong key! It doesn't take more than a few seconds to find the correct one and with a gentle motion, you turn the key to the right.

The beach is not far from home, but quite enough to make your head quickly to the driver's seat and start the engine. The alarm beeps reminding you to fasten the seat belt. You comply successfully with the demands of your vehicle.

Heading to your favorite spot, where the sea ​​breeze leaves a gentle, liquid sense in the air, way off the crowded area you live in, the yellow color of the traffic lights suggests slowing your speed. After two seconds, the traffic lights turn red, commanding you to stop. On your left, two people are buying from the vending machine near the coffee shop, where a couple is playing a board game. The lights turn green and you continue the ride to the desired location.

When you finally reach it, all the previous images start crossing your mind:

• the alarm clock
• the key hole
• the car commanding you to fasten the seat belt
• the traffic lights
• the vending machine
• the board game

You suddenly make the connection! They all represent some kind of finite-state machine.

Finite-State Machines (FSMs)

Think of a computer with extremely limited memory capacity. A device with such limited resources can seem inefficient at first glance but don't rush to a conclusion yet. What makes a machine like this special in a world where every computer tends to be big, complicated and fancy, is the simplicity of its design.

You see, modern computers are extremely complex to allow us to create a feasible mathematical theory of them directly. Sometimes scientists need only the basics to work on a solution. For that reason, we created an idealized computer, a computational model. The simplest model is called finite-state machine (FSM).

We can visualize one using state diagrams. Look at the image below:

For those who know the basics of graph theory, this is clearly a directed graph. We can see the nodes, represented by circles, and edges, represented by arrows. But unlike graphs, in state diagrams, we call them states and transitions respectively.

States represent the status of a system. For instance, automatic sliding doors in supermarkets have two states: either close or open. Traffic lights contain three states: red, yellow, green. More sophisticated examples can contain quite a lot of states, but never an infinite number. Having no states doesn't make sense either.

When a finite-state machine is running, one or many states are active in each execution step. Those active states represent the current value of the system.

In the first execution step, a default state, called the starting state, is being activated. In state diagrams, those states are indicated by an arrow pointing to them. In the above diagram, state s is the starting state.

Finite-state machines may also contain one or multiple accepting states. Accepting states are represented by a double circle, like states p and r. A finite-state machine is not required to have accepting states; it might be designed to run indefinitely. The purpose of accepting states is quite straight forward: when the processing ends, depending on if we are on any accepting states or not, the output of the finite-state machine is either accept or reject.

States are connected with each other using transitions. Each transition contains a set of symbols. The set of all symbols presented in the FSM is called the alphabet. When the source state is active and the transition is executed, it changes the active state from the source state to the destination state only if the current input matches the symbol of the transition.

It's like using a vending machine:

The active state when you first approach the machine is idle, which happens to also be the starting state. By inserting coins, you move to the next state choose product.

To recap, finite-state machines:

• have a set of states and transitions
• have at least one state
• cannot have an infinite number of states
• have one starting state, which is the first state that is activated upon their execution
• may or may not have accepting states
• have for each transition a set of symbols,
• have an alphabet which is the union of all the sets of transition symbols

There are two types of finite-state machines: deterministic and non-deterministic. Based on those types, the execution is handled differently. Remember that finite-state machines are a computational model: they calculate an output based on the provided input. Below we discuss these two types and provide a complete running example for each one.

Deterministic Finite Automatons (DFAs)

The first type of finite-state machine is the Deterministic Finite Automaton (DFA). The word deterministic has quite a value here. It means that you can transition from one state to the next while not being in multiple states concurrently. Think the example with the traffic signals: they can't be in green and red state at the same time.

Let's take a look at the bellow automaton:

The above DFA contains 4 states. Starting state is s and accepting state is r. The alphabet contains the symbols a, b, and c.

Observe that for each state, there is only one transition arrow for each symbol. In some cases, a transition arrow can contain multiple symbols, like the one from q to r, but this does not break the requirement as there is no other exiting transition from q with the same symbols (b and c).

In deterministic finite automatons, the transition from one state to another can happen only if the input matches the symbol(s) of the transition. For instance, we can move from s to q only if the current symbol of the input is b.

A running example

But enough with the theory! Let us see what the above DFA outputs for the input baabb.

---

When the execution begins, the starting state is being activated. To run the automaton, for each symbol in the input, from left-to-right, we're going to see if there is an exiting transition from the active state that match this symbol.

The first symbol of the input baabb is b. The current active state is s. Is there any exiting transition from s that contains the symbol b? Yes, the one that connects s to q.

---

The current active state is q. The next symbol of the input baabb is a. Is there any exiting transition from q that match the symbol a? Yes, the one that connects q with p.

---

The current active state is p. The next symbol of the input baabb is a. Is there any exiting transition from p that match the symbol a? Yes, the one that connects p with itself.

---

The current active state is p. The next symbol of the input baabb is b. Is there any exiting transition from p that match the symbol b? Yes, the one that connects p with q.

---

The current active state is q. The next symbol of the input baabb is b. Is there any exiting transition from q that match the symbol b? Yes, the one that connects q with r.

---

At this point we have traverse all the symbols of the input. The final active state is r. Is r an accepting state? Yes it is! That means the output is accept. In case that after traversing the input the final state was not an accepting state, the output would be reject.

Formal definition

It would be a shame not to mention the formal definition of a DFA, now that we have covered all the required details to do so.

---

A deterministic automaton is a 5-tuple ⟨Q, Σ, δ, q₀, F⟩, where

1. Q is a finite set of all states
2. Σ is a finite set of all symbols, the alphabet
3. δ: Q × Σ → Q is the transition function
4. q₀ ∈ Q is the starting state
5. F ⊆ Q is the set of accepting states

---

What may bother you in the above definition, is the transition function. Remember that we can move from one state to another only if the current input matches the symbol of the transition. For instance, consider that a finite automaton has a transition labeled 1 from a state p to a state q, then we can indicate the same thing with a transition function δ(p, 1) = q. This notion is just a kind of mathematical shorthand.

Non-deterministic Finite Automatons (NFAs)

The second type of finite-state machine is the Non-deterministic Finite Automaton (NFA). Compared to deterministic finite automatons, there are some major differences.

Consider the following automaton:

The above NFA contains 5 states. Starting state is s and accepting states are v and d. The alphabet contains the symbols a, b and c.

But wait a moment! What is this strange label ε? It is a Greek character called epsilon and is not part of the alphabet. In non-deterministic automatons, transitions can be labeled either with a symbol from the alphabet or ε.

In non-deterministic automatons, there are cases where more than one transitions are applicable. In those cases, the automaton splits into multiple copies of itself and continues to run in non-determinism manner like before. We can see this behavior as a kind of parallel computation, where the machine is forking into several children, each processing independently.

Label ε is the first difference between deterministic and non-deterministic automatons. The second difference is the use of multiple transition arrows that contain the same symbols for each state in the NFA. For instance, state s has two exiting transitions labeled with the symbol a. This is the opposite of a DFA which has only one symbol per exiting transition for each state.

A running example

A running example will clear any misconceptions.

---

When the execution begins, the starting state is being activated. We're going to check if there are any ε transition from s.

• Is there any ε transition from s? Yes, the one that connects s to w. Activate state w.

For the new state, we'll do the same procedure until no more ε transitions exist.

• Is there any ε transition from w? No, there isn't.

The initial active states are s and w.

---

For each symbol of the input, from left-to-right, we'll check if there are exiting transitions from the active states that match that symbol. Then we'll follow the previous process and activate all the states that connect with epsilon transitions.

The first symbol of the input aabc is a. The current active states are s and w.

• Any exiting transition from s that contains the symbol a? Yes, the ones that connect s to w and a.
• Any exiting transition from w that contains the symbol a? No, there isn't.

For the new activated states w and a, we're going to follow all the epsilon transitions and repeat until we run out of them:

• Any ε transition from w? No, there isn't.
• Any ε transition from a? Yes, the one that connects a to v.
• Any ε transition from v? Yes, the one that connects v to itself. Because this transition forms a self loop, we won't test v again.

The new active states are w, a and v.

---

The next symbol of the input aabc is a. The current active states are w, a and v.

• Any exiting transition from w that contains the symbol a? No.
• Any exiting transition from a that contains the symbol a? Yes, the ones that connect a to d and v.
• Any exiting transition from v that contains the symbol a? No.

For the new activated states d and v, we're going to follow all the epsilon transitions and repeat until we run out of them:

• Any ε transition from d? No.
• Any ε transition from v? Yes, the one that connects v to itself. Because this transition forms a self loop, we won't test v again.

The new active states are d and v.

---

The next symbol of the input aabc is b. The current active states are d and v.

• Any exiting transition from d that contains the symbol b? Yes, the one that connect d to s.
• Any exiting transition from v that contains the symbol b? Yes, the one that connect v to a.

For the new activated states s and a, we're going to follow all the epsilon transitions and repeat until we run out of them:

• Any ε transition from s? Yes, the one that connects to w.
• Any ε transition from w? No.
• Any ε transition from v? Yes, the ones that connects v to itself and a.
• Any ε transition from a? Yes, the one that connects to v. Because we already tested v we won't test it again.

The new active states are s, w, a and v.

---

The last symbol of the input aabc is c. The current active states are s, w, a and v.

• Any exiting transition from s that contains the symbol c? No.
• Any exiting transition from w that contains the symbol c? No.
• Any exiting transition from a that contains the symbol c? No.
• Any exiting transition from v that contains the symbol c? Yes, the one that connects to a.

For the new activated state a, we're going to follow all the epsilon transitions and repeat until we run out of them:

• Any ε transition from a? Yes, the one that connects to v .
• Any ε transition from v? Yes, the one that connects v to itself.

---

The final active states are a and v. Is any of them an accepting state? Yes, state v is an accepting state. That means the output is accept. In case that after traversing the input the final state was not an accepting state, the output would be reject.

Formal definition

The formal definition of a non-deterministic automaton is similar to the definition of a deterministic one. It consists of states, transitions, a transition function, an alphabet, and some accepting states. The only difference is the kind of transition function.

---

A non-deterministic automaton is a 5-tuple ⟨Q, Σ, δ, q₀, F⟩, where

1. Q is a finite set of all states
2. Σ is a finite set of all symbols, the alphabet
3. δ: Q × Σε → P(Q) is the transition function
4. q₀ ∈ Q is the starting state
5. F ⊆ Q is the set of accepting states

---

In deterministic automatons, the transition function takes as input a state, a symbol and returns the next state, as output. In non-deterministic automatons, the transition function takes as input a state, a symbol or ε and returns the set of all possible next states, as output.

Conclusion

This article was intended to provide you with all the required details and examples to get a better understanding of Finite-state Machines. Thank you for taking the time to read it. 🙏

Comments

[Andrew Murray]

Great detail on the theory of FSMs, thanks for taking the time to write that up. I was thinking, it might help to illustrate better with a few code samples?