1.
Introduction
1.1.
What is the state machine model?
1.2.
What is the Finite State machine model?
2.
Deterministic Finite Automata (DFA)
3.
Nondeterministic Finite Automata(NFA)
4.
4.1.
How is DFA different from NFA in terms of space complexity?
4.2.
5.
Conclusion
Last Updated: Mar 27, 2024

# Finite State Machine

Apoorv

## Introduction

Finite State Machines are one of the most elementary topics in the Theory of Computation. Here in this blog, we are going to take a detailed look at finite state machines as well as their types. Before going deep into the finite state machine. First, let's explore the state machine model.

### What is the state machine model?

• This is a reactive or event-driven model
• Or embedded system whose processing behavior is dependent on state transition
• It is represented as “states, Events, Actions, and Transitions”
• State: It is a representation of the current situation
• Event: It is a representation of input to the state
• Action: It is a representation of an activity to be performed by the state machine
• Transition: It is movement from one state to another

Also See, Simplification of CFG

### What is the Finite State machine model?

• It is one with a heaving number of states finite.
• A finite state machine is a machine that is used to recognize patterns.
• The input to a finite automata machine is a string of symbols, and the state of the machine is changed correspondingly. When the desired symbol is found in the input, the transition occurs.
• The Automata can either migrate to the next state or stay in the current state while transitioning.
• FA can be in one of two states: accept or reject. The automata will accept when the input string has been correctly digested, and the automata have reached its final state.
• The finite automata or finite state machine is an abstract machine with five elements or tuples. It has some predefined set of rules for moving from one state to another, but it also has a dependency on the applied input symbol.
•  It's essentially an abstract representation of a digital computer.

Example: Embedded system for driver seat belt warning in automotive here we can decide the states are alarm off, waiting, alarm on and events are ignition key on, ignition key off, waiting time expires and seat belt on using FMS

A finite automaton consists of the following:

``````                 Q: a finite set of states
∑: a finite set of input symbol
q0: initial state
F: final state
δ: Transition function
Representation of machine
{ Q, Σ, q, F, δ }``````
1. We can define the transition function as:
`` δ: Q x ∑ →Q  ``

Finite state machine or finite automata can be further characterized into two ways:

Also see, Turing Machine in TOC.

## Deterministic Finite Automata (DFA)

In DFA, the state to which the machine will move can be determined for each input symbol. As a result, it's known as a Deterministic Automaton. The machine is known as a Deterministic Finite Machine or Deterministic Finite Automaton because it has a finite number of states.

DFA consists of 5 tuples {Q, Σ, q, F, δ}

Q: a set of all states.

Σ: a set of input symbols. ( Symbols which machine takes as input )

q: Initial state. ( Starting state of a machine )

F: a set of the final state.

δ: Transition Function, defined as δ: Q X Σ --> Q.

In a DFA, the machine only goes to one state for each input character. Every state for each input symbol has a transition function defined. DFA doesn't accept the null move, which means the DFA cannot change the state without any input character. One thing to keep in mind is that a pattern can have several DFAs. A DFA with the fewest possible states is generally preferred.

Example:

=  {0,00,01,000,010,011,000,............}

## Nondeterministic Finite Automata(NFA)

In NDFA, the machine can move to any combination of the states in the machine for a given input symbol. In other words, the particular state to which the machine moves cannot be predicted. As a result, it's known as a Non-deterministic Automaton. The machine is known as a Non-deterministic Finite Machine or Non-deterministic Finite Automaton because it has a finite number of states.NDFA accepts the NULL move, which means it can change the state without reading the symbols.

NFA consists of 5 tuples {Q, Σ, q, F, δ}

Q: a set of all states.

Σ: a set of input symbols. ( Symbols which machine takes as input )

q: Initial state. ( Starting state of a machine )

F: a set of the final state.

δ: Transition Function, defined as δ: Q x ∑ →2Q

Example:

L1  =  Set of all strings that end with with ‘0’

=  {0,00,000,010,00,..000,............}

Also See, Symbol Table Operations

### How is DFA different from NFA in terms of space complexity?

DFA uses more space when compared with NFA because if we consider NFA, it can be visualized as multiple little machines computing at the same time, whereas In the case o DFA, the next possible state is distinctly set; hence a lot of space is saved in NFA.

### What is the dead state?

A state of rejection that is effectively a dead end. There is no way for the machine to achieve an accepted condition once it enters a dead state, thus we already know the string will be denied. For any input that the machine does not have explicit instructions on what to do with, the dead state is frequently neglected and presumed graphically. A machine can have numerous dead states, but each machine only requires one dead state.

## Conclusion

In this blog, we discussed a lot about Finite State Machine or finite Automata, along with we also discussed Finite State Machine types with examples in brief.