Nondeterministic Finite Automata
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 9

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction to NFA

A nondeterministic FA starts in one state. It accepts input, if at least one
sequence of transitions leads to a final state. Intuitively: it always
“guesses right.”
It allow several transitions for a single (state, symbol) pair
Simultaneous transitions with the same input symbol
may change states without reading any input
all possible input alternatives are not necessary at every state
This generalization allows more than one execution of the same word
(this is nondeterminism). A word is accepted iff one of these executions
ends in a final state.

kr chowdhary

TOC

2/ 9

NFA: Formal Definition
Let M be an NFA:
M = (Q, Σ, δ , s, F )

(1)

δ : Q × Σ → 2Q ,

(2)

Therefore, δ (q , q) ∈ 2Q
0

The language accepted by NFA is:
L = L(M) = {w ∈ Σ∗ | (q0 , w ) ⊢∗M ({. . . , qf , . . . }, ε), qf ∈ F }

(3)

Since, an NFA moves to a set of states, it simulates more than one
DFA in parallel. Collection of all these states is called state space.
If entire state space is searched in sequential way, it will require back
tracking, resulting to a slower process(in DFA).
Because NFA accepts null(ε) input also, the generalized transition
functions is modified as:
δ = Q × Σ ∪ {ε} → 2Q .
kr chowdhary

TOC

(4)
3/ 9

NFA is simpler

For any given regular expression, an
NFA will have lesser number of
states. Consider the regular
expressions (ab + aba)∗ .

The nfa has far 3 states. Also, all
inputs are not allowed, e.g.,
aba ⇒ q0 q1 q0 q1 , and
δ (q0 , abb) = φ .
a
a

a

b

q0

q1
b

q2
a

b

q3
b

q4
a, b

Figure 1: NFA for the regular
expression (ab + aba)∗ .

Figure 2: DFA for the regular
expression (ab + aba)∗ .

kr chowdhary

TOC

4/ 9

Language acceptability by NFA
Since in the final state set
{q1 , q2 , q3 }, the q2 , q3 ∈ F , string
abb is accepted by the NFA.
Are NFAs more powerful than
than DFA? Can they
recognize a language that
DFA cannot recognize?
Figure 3: NFA accepting w = aab.

If one of the paths in NFA
leads to final state, input is
accepted. In fact there are
other paths also for the same
input !!. So, are the class of
languages accepted by DFA
are subset of that by NFA?

(q0 , aab) ⊢ ({q0 , q1 }, ab)
⊢ (q0 , ab) ∪ (q1 , ab)
⊢ ({q0 , q1 }, b) ∪ ({q3 }, b)
⊢ (q0 , b) ∪ (q1 , b) ∪ (q3 , b)
⊢ (φ , ε) ∪ (q2 , ε) ∪ ({q1 , q3 }, ε)

An NFA is in fact not powerful
than DFA.

⊢ ({q1 , q2 , q3 }, ε)
kr chowdhary

TOC

5/ 9

For every NFA there is an equivalent DFA
Theorem
For every NFA their exists an equivalent DFA, which accepts the same
language as the NFA.
Proof.
Let the NFA be MN = {Q, Σ, δ , s, F }, and let there exists a DFA,
MD = {Q ′ , Σ, δ ′ , s ′ , F ′ }, which accepts the same language. Machine MD
can be constructed from MN as follows:
1

For every state qi ∈ Q obtain its closure due to ε transitions as:
C (qi ) := {qi };

2

while there is a transition δ (qi , ε) = rk
C (qi ) := C (qi ) ∪ {rk };

3
4

Q ′ = 2Q , S ′ = C (s) ; F ′ = {. . . , qf , . . . }, ∀qf ∈ F
δ ′ : if there is transition δ (qi , a) = qj , and in the DFA we have
{. . . , qi , . . . } and {. . . , qj , . . . } state sets, then keep a transition
between these state sets labeled as a.

kr chowdhary

TOC

6/ 9

Obtain a DFA for given NFA

δ ({q0 , q1 }, a) = δ (q0 , a) ∪ δ (q1 , a)

Figure 4: NFA

= {q0 , q1 } ∪ {q2 }
= {q0 , q1 , q3 }.

We generate all next state sets at
every state, starting with q0 , for all
the alphabet symbols. Then next
states for all these states:

δ ({q0 , q1 }, b) = {q1 , q2 }

δ (q0 , a) = {q0 , q1 }

δ ({q1 , 1}, a) = {q2 }

δ (q0 , b) = {q1 }

δ ({q1 }, b) = {q2 }

kr chowdhary

TOC

7/ 9

continued from previous . . .

δ ({q0 , q1 , q2 }, a) = {q0 , q1 , q2 }
δ ({q0 , q1 , q2 }, b) = {q1 , q2 }
δ ({q1 , q2 }, a) = δ (q1 , a) ∪ δ (q2 , a)
= {q2 } ∪ {φ }

Figure 5: Equivalent DFA for a given
NFA.

= {q2 }.
δ ({q1 , q2 }, b) = {q2 }

Since it does not exist, we can drop
the null state.

δ ({q2 , a}) = φ
δ ({q2 }, b) = {q2 };

kr chowdhary

TOC

8/ 9

Bibliography

Chowdhary, K.R. (2025). Variants of Finite Automata. In: Theory of
Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_3

kr chowdhary

TOC

9/ 9