NFAs and Properties of Regular Languages
Prof. Shrisha Rao
IIIT Bangalore
srao@iiitb.ac.in
2025-08-12
2/15
More NFAs
Give NFAs to accept the following languages:
(1) The set of all strings with only an even number of 0s, or only
exactly two 1s.
(2) The language 0∗ .
(3) The set of all strings where every odd position is a 1.
3/15
Recap: Language of an NFA
What languages do these NFAs accept?
4/15
ϵ-transitions
• An ϵ-transition happens when an NFA moves from one state
to another on an ϵ, i.e., with no input symbol.
• Obviously, ϵ-transitions are only possible with NFAs, not with
DFAs.
• ϵ-transitions are particularly useful in case of NFAs that have
to accept REs of the form A + B.
• For instance, consider an NFA to accept all binary strings
which have only 1s, or where the last symbol is a 0. (What is
the RE for this language?)
5/15
NFA for 1∗ + (0 + 1)∗ 0
6/15
5-tuple definition of NFAs
• An NFA M is also given by the 5-tuple
M = ⟨Q, Σ, δ, qo , F⟩
• Q, Σ, q0 , and F have the same meanings as before.
• The transition function δ has to be changed to allow for
non-determinism.
• Problem: for any function, f(x) = a and f(y) = a, with x ̸= y
is quite possible; however, f(x) = a and f(x) = b with a ̸= b is
impossible. (A function can map different values in the
domain to the same value in the range, but it can never map
a single value in the domain to different values in the range.)
7/15
Transition Function for NFAs
• The solution is to define δ : Q × Σ −→ 2Q , i.e., δ maps from
Q × Σ to the powerset of Q.
• In this way, the problem is averted. If an NFA can transition
from state A to states B and C on some input a, then instead
of saying δ(A, a) = B and δ(A, a) = C, we say
δ(A, a) = {B, C}.
• There is a further enhancement possible, given that an NFA
can also transition on ϵ. So the best way to specify δ is by
saying ( )
δ : Q × Σ ∪ {ϵ} −→ 2Q .
8/15
Exercise
(4) Give 5-tuple definitions for each of the three NFAs so far
discussed (on slides 3 and 5).
9/15
Kleene’s Theorem
The following are identical properties for a language L.
• L is a regular language (given by a regular expression).
• L is accepted by a DFA.
• L is accepted by an NFA.
Therefore, non-determinism does not add to the power of a FA,
but it makes the construction easier.
10/15
Regularity is Closed Under Union
• The class of regular languages is closed under union; this
means that if L1 and L2 are regular languages, then so is
L1 ∪ L2 .
• We can prove this and similar properties using Kleene’s
theorem.
• In such cases, the approach is to assume that L1 and L2 are
accepted by DFAs (or NFAs) M1 and M2 , and then to
construct new automata that accept L1 ∪ L2 .
11/15
Showing Regularity to be Closed Under Union
• Let M1 ≡ ⟨Q1 , Σ, δ1 , q1 , F1 ⟩ accept L1 , and
M2 ≡ ⟨Q2 , Σ, δ2 , q2 , F2 ⟩ accept L2 . NB: Without loss of
generality, we can assume that the alphabet Σ is common to
M1 and M2 .
• We need a machine M that accepts L1 ∪ L2 .
• M will also of course be of the form ⟨Q, Σ, δ, q0 , F⟩.
• Have to specify the individual elements Q, δ, etc., in terms of
Q1 , Q2 , δ1 , δ2 , etc.
12/15
The DFA for the Union Language
Solution idea:
Construct a compound machine M which runs M1 and M2 in
parallel with their respective state changes for every input, and
accepts if either M1 or M2 accepts.
• Q ≡ Q1 × Q2
• δ : (Q1 × Q2 ) × Σ −→ Q1 × Q2 , given by
( ) ( )
δ (r1 , r2 ), a = δ1 (r1 , a), δ2 (r2 , a) , where r1 ∈ Q1 and
r2 ∈ Q2 .
• q0 ≡ (q1 , q2 ), i.e., the starting state of M is the ordered pair
of the starting states of M1 and M2 .
• F ≡ (F1 × Q2 ) ∪ (Q1 × F2 ). Note that F ≡ F1 × F2 is wrong!
F is {(r1 , r2 ) | r1 ∈ F1 or r2 ∈ F2 }.
13/15
Regularity is Closed Under Intersection
• The intersection L1 ∩ L2 of two regular languages L1 and L2 is
also regular.
• As before, the proof proceeds by constructing a machine M to
accept L1 ∩ L2 , given machines M1 and M2 that accept L1
and L2 .
14/15
Regularity is Closed Under Complementation
• If L is a regular language, then so is the complement language
L, where L ≡ Σ∗ \ L.
• The proof is as before, considering the existence of a machine
M that accepts L.
• Show the construction of a machine M that accepts L, given a
machine M that accepts L.
15/15
Exercises
Give NFAs to accept the following languages:
(5) The set of all strings with an even number of 0s (and possibly
1s as well), or exactly two 1s only.
(6) The language 0∗ .
(7) The language given by the RE 0∗ 1 + 1∗ 0.
