Study of NFA and DFA

Introduction to Study of NFA, DFA with its comparison

About Finite Automata(FA)

A finite automaton (FA) is a machine(model) used to identify and recognize patterns within input taken from some character set and respond in a manner of whether the pattern will be accepted or rejected.

When you talk simply about a “Finite Automaton” then it may or may not be deterministic. One can only assume it is deterministic if it is specifically stated otherwise it is non-deterministic.

In this article, we will study specifically the automata without output i.e., Deterministic Finite Automata and Non-Deterministic Automata.

Formal Definition of DFA :

DFA is a deterministic finite automaton having a single resultant state from its corresponding input symbol. It comprises of 5 tuple such as, A = (Q, ∑, δ, q₀, F) .

(For better understanding refer and correlate terminologies with diagram )

• Q is a finite set of states {q₀,q₁,q_f}.
• ∑ is a finite set of symbols called the alphabet {0,1}.
• δ is the transition function where δ: Q × ∑ → Q
• q₀ is the initial state from where any input is processed (q₀ ∈ Q).
• F is a set of final states. Q (F ⊆ Q), {q_f ∈ Q}.

Graphical Representation of a DFA

A DFA is represented by digraphs called state diagrams or transition diagrams.

• The nodes in a circle represent the states.
• The arrows labeled with an input alphabet show the transitions.
• The initial state is denoted by a single incoming arrow.
• The final state is indicated by double circles (One inside the other).
• The transition in itself signifies a loop.
• Every state is deterministic with a set of input symbols.

Examples of DFA

Traffic Lights, Vending Machines, Video Games, Text Parsing, Regular Expression Matching, CPU Controllers, Protocol Analysis, Natural Language Processing, Speech Recognition

Non Deterministic Finite Automata

In NFA, there exist many paths for specific input from the current state to the next state. Where it moves cannot be determined. Hence, it is called Non-deterministic Automaton. As it has a finite number of states, the machine is called a Non-deterministic Finite State Machine or Non-deterministic Finite Automaton.

Formal defination of NDFA

An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −

• Q is a finite set of states.
• ∑ is a finite set of symbols called the alphabets.
• δ is the transition function where δ: Q × ∑ → 2^Q

(Here the power set of Q (2^Q) has been taken because in the case of NDFA, from a state, the transition can occur to any combination of Q states)

• q₀ is the initial state from where any input is processed (q0 ∈ Q).
• F is a set of final states/states of Q (F ⊆ Q).

For every NFA there’s a corresponding DFA that accepts the same language, For NFA with n states, there would be DFA having Θ(2ⁿ) states. That is the reason why NFA is mostly preferred over DFA while designing a model of the machine.

Some  real-life examples of Non-Deterministic Automata are;

Games such as Tic Tac Toe, Ludo, Playing Cards, etc. all follow the NDFA approach in some another manner.

Comparision of DFA & NFA

Now, let us understand both DFA & NFA by their comparison :