Finite state machines

Finite state machines, also known as finite state automata, are models that help us to represent behavior of systems or processes that can exist in a finite number of states. These are widely used in computer science, software engineering, electronics, and various other fields to model and understand the behavior of systems and any patterns that exist between them.

Components of a finite state machine

The following are the components of a finite state machine:

• Set of states ($Q$): A state is a condition the system can be in at any given time. Each state represents a specific situation. It is represented by a circle.

• Set of inputs ($∑$): An input is a value or a symbol that triggers a transition from one state to another.

• Set of outputs ($Δ$): An output is a value or a symbol that is generated after a transition is completed.

• Start state ($q_o$): The initial state that begins the execution in the finite state machine. It is represented by a circle with an arrow with no starting end pointing to it.

• Final state ($F$): The ending states of our finite state machine that represents the completion of our execution. There can be multiple final states in our model. They are represented by a circle with a circular border.

Note: We use the final state component only in the finite state machines without output. We will be discussing this in the later section of the Answer.

• Transition function ($δ$): A representation of all the transitionsIt represents the change from one state to another. in the model. The transition function consists of all combinations of the current state and an input, providing the next state of the finite state machine. Transitions are represented by arrows connecting the states.

• Output function ($λ$): A representation of all outputs generated by the model with their corresponding inputs.

The following diagram shows the components that we have learned so far.

Note: The output component is only used in finite state machines with output, and we represent this output in different ways for each finite state machine type we discuss below.

States of finite state machines

There are two states of the finite state machine based on whether it recognizes an input and accepts/rejects that input.

1. Accept state: The finite state machine accepts and recognizes the input.

2. Reject state: The finite state machine rejects and doesn't recognize the input.

Types of finite state machines

There are two divisions in which types of finite state machines can be be defined: finite state machines without output and finite state machines with output.

1) Finite state machines without output

There are two types of finite state machine without output: deterministic and non-deterministic.

Note: In these types we can define all the components of finite state machine excluding the set of outputs ($Δ$) and output function ($λ$).

Deterministic finite state machines

In deterministic finite state machines, each state has a single transition for each input in the input set. These transitions are predefined and known. Moreover, every state must have transitions for all inputs in the input set, and each input should lead to a unique next state. For example, if the input set is {0, 1}, each state should have transitions for both 0 and 1, with each input leading to a distinct next state.

Note:  Deterministic finite state machines don't accept any null input, meaning no state change can occur without any input.

Let's assume the following example:

The above example shows that each state has a distinct and predefined output state for every input. All the states {A, B, C} have a transition for input 0 and 1 and every transition leads to a distinct next state.

• Set of states ($Q$): {A, B, C}

• Set of inputs ($∑$): {0, 1}

• Start state ($q_0$): A

• Final state ($F$): {C}

Note: We can represent the transition function of deterministic finite state machine as:

$δ: Q × ∑ →Q$

This means that for each combination of a current state Q and an input symbol ∑, there is one unique next state Q.

Non-deterministic finite state machines

In non-deterministic finite state machines, a state can have multiple transitions for the same input leading to multiple next states. These transitions not known already and determined on randomness. For example, if the input set is {0, 1}, each state can have multiple transitions for both 0 and 1.

Note: Non-deterministic finite state machines accept the null input (ε), meaning when there is no input, state change can still take place.

Let's assume the following example:

In the above example, we observe that each state can have multiple unique output states for an input. For instance, state A has two next states {B, C} for input 0. Some states may not have an output state for certain inputs; for example, state A does not have a next state for input 1. Additionally, even without any input, a state can still change; for example, state A changes to D in the absence of input.

• Set of states ($Q$): {A, B, C, D}

• Set of inputs ($∑$): {0, 1}

• Start state ($q_o$): A

• Final state ($F$): {D}

Note: We can represent the transition function of deterministic finite state machine as:

$δ: Q × ∑ →2^Q$

This means that for each combination of a current state $Q$ and an input symbol $∑$, there are $2^Q$ possible next states.

2) Finite state machines with output

There are two types of finite state machine with output: mealy machine and moore machine.

Note: In these types we can define all the components of finite state machine excluding the final state ($F$).

Mealy machine

In a mealy machine, each output depends on the input state and the input value. If the input state or input value changes, the output might also change. The output is written on the transition with the input.

Let's assume the following example:

The above example shows that each output value is defined for a combination of input state and input value.

• Set of states ($Q$): {A, B}

• Set of inputs ($∑$): {0,1}

• Set of outputs ($Δ$): {x, y}

• Start state ($q0$): A

Note:

• We can represent the transition function of a mealy machine as:

$δ: Q × ∑ →Q$

This means that for each combination of an input state Q and an input symbol ∑, there is one unique next state Q.

• We can represent the output function of a mealy machine as:

$δ: Q × ∑ →Δ$

This means that output Δ depends on the combination of an input state Q and an input symbol ∑.

Moore machine

In a moore machine, each output depends only on the input state. If the input state is changed only then the output might change, it is not dependent on the input value. The output is written inside the state.

Let's assume the following example:

The above example shows that each output value depends and is defined for a combination of input state and input value.

• Set of states ($Q$): {A, B}

• Set of inputs ($∑$): {0,1}

• Set of outputs ($Δ$): {x, y}

• Start state ($q0$): A

Note:

• We can represent the transition function of moore machine as:

$δ: Q × ∑ →Q$

This means that for each combination of an input state Q and an input symbol ∑, there is one unique next state Q.

• We can represent the output function of moore machine as:

$δ: Q →Δ$

This means that output Δ depends only on the input state Q.

Conclusion

Finite state machines are widely used in computer science and various other fields to model and describe the behavior of systems with distinct states and transitions between those states. They provide a clear and structured way to represent complex behavior and help in understanding, designing, and implementing systems with discrete and predictable states.