Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
4.1.
How is DFA different from NFA in terms of space complexity?
4.2.
What is the dead state?
5.
Conclusion
Last Updated: Mar 27, 2024

Finite State Machine

Author Apoorv
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
TOC

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.

Also Read, Moore Machine

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.

Also read - Arden's theorem

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

Driver Seatbelt Automotive

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:

Types of Finite State Machine

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:

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

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

Example DFA
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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,............}

Example NFA

Also See, Symbol Table Operations

 

Frequently Asked Questions

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.

Recommended Readings:


You can also consider our Online Coding Courses such as the Machine Learning Course to give your career an edge over others.

To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Introduction of Automata Theory
Next article
Deterministic Finite Automata or DFA
Live masterclass