'Coding has over 700 languages', '67% of programming jobs arenâ€™t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Nondeterministic means where the transition from a state can be to multiple next states for each input symbol. It has been observed that NFA is easier to construct than DFA. Every NFA is not DFA, but not each NFA can be translated to DFA.

In Nondeterministic automation, we cannot determine the same state the machine moves.

Every NFA can be converted to DFA, but every NFA is not DFA. NFA is the same as DFA, but with two exceptions, It contains multiple states, and it contains Îµ transitions,Îµ here simply means empty string.

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

Graphical representation of NFA

An NFA is represented by digraphs called state diagrams.

Vertices represent the state.

The arc, which is labeled by input direction, shows the transition.

An arrow denotes the initial state.

A double circle represents the final state.

Regular Expressions

A regular expression can be defined as a language accepted by finite Automata. It is used to match character combinations in a string. The string searching algorithm uses a regular expression to find the operations on a string.

We will use Thompson's construction method to convert the regular expression to an NFA. Regular expressions and NFA are both representations of formal language. Text-processing utilities use regular expressions to describe advanced search patterns, but NFA is better suited for execution on a computer.

Thompson is a method for converting regular expressions to their respective NFA diagrams. Thompson construction consists of 5 rules:

NFA stands for nondeterministic automata. A finite automaton is called an NFA when multiple paths exist for specific input from the current state to the next state.

What do you mean by automata?

Automata is a relatively self-operating mechanism or machine designed to follow a predetermined sequence of instructions automatically.

What are the properties of NFA?

An NFA can have zero, one, or multiple transitions corresponding to a particular symbol.

Conclusion

In this article, we studied Nondeterministic finite Automata(NFA). We saw the definitions of NFA, regular expressions, and how to convert regular expressions to NFA. We have used Thompson's construction method to convert regular expressions to NFA.