Non-Deterministic

Finite Automata

1
Nondeterministic Finite Automaton (NFA)

Alphabet = {a}

q1 a q2
a
q0
a
q3

2
Alphabet = {a}

Two choices q1 a q2
a
q0
a
q3

3
Alphabet = {a}

Two choices q1 a q2 No transition

a
q0
a
q3 No transition

4
 First Choice

a a

q1 a q2
a
q0
a
q3

5
 First Choice

a a

q1 a q2
a
q0
a
q3

6
 First Choice

a a
All input is consumed

q1 a q2 “accept”
a
q0
a
q3

7
 Second Choice

a a

q1 a q2
a
q0
a
q3

8
 Second Choice

a a
Input cannot be consumed

q1 a q2
a
q0 Automaton Halts
a
q3 “reject”

9
An NFA accepts a string:
if there is a computation of the NFA
that accepts the string

i.e., all the input string is processed and the

automaton is in an accepting state

10
 aa is accepted by the NFA:

“accept”
q1 a q2 q1 a q2
a a
q0 q0
a a
q3 q3 “reject”
because this
this computation
computation
is ignored
accepts aa
11
 Rejection example

q1 a q2
a
q0
a
q3

12
 First Choice

a
“reject”
q1 a q2
a
q0
a
q3

13
 Second Choice

q1 a q2
a
q0
a
q3

14
 Second Choice

q1 a q2
a
q0
a
q3 “reject”

15
 Another Rejection example

a a a

q1 a q2
a
q0
a
q3

16
 First Choice

a a a

q1 a q2
a
q0
a
q3

17
 First Choice

a a a
Input cannot be consumed

q1 a q2 “reject”
a
q0
a
Automaton halts
q3

18
 Second Choice

a a a

q1 a q2
a
q0
a
q3

19
 Second Choice

a a a
Input cannot be consumed

q1 a q2
a
q0 Automaton halts
a
q3 “reject”

20
An NFA rejects a string:
if there is no computation of the NFA
that accepts the string.

For each computation:

• All the input is consumed and the
automaton is in a non final state

OR
• The input cannot be consumed
21
 a is rejected by the NFA:

“reject”
q1 a q2 q1 a q2
a a
q0 q0
a a
q3 “reject” q3

All possible computations lead to rejection

22
aaa is rejected by the NFA:

“reject”
q1 a q2 q1 a q2
a a
q0 q0
a a
q3 q3 “reject”

All possible computations lead to rejection

23
Language accepted: L = {aa}

q1 a q2
a
q0
a
q3

24
 Lambda Transitions

q0 a q1  q2 a q3

25
a a

q0 a q1  q2 a q3

26
a a

q0 a q1  q2 a q3

27
 input tape head does not move

a a

q0 a q1  q2 a q3

28
 all input is consumed

a a

“accept”

q0 a q1  q2 a q3

String aa is accepted
29
 Rejection Example

a a a

q0 a q1  q2 a q3

30
a a a

q0 a q1  q2 a q3

31
 (read head doesn’t move)

a a a

q0 a q1  q2 a q3

32
Input cannot be consumed

a a a

Automaton halts
“reject”

q0 a q1  q2 a q3

String aaa is rejected

33
Language accepted: L = {aa}

q0 a q1  q2 a q3

34
 Another NFA Example

q0 a q1 b q2  q3


35
a b

q0 a q1 b q2  q3


36
a b

q0 a q1 b q2  q3


37
a b

“accept”

q0 a q1 b q2  q3


38
 Another String

a b a b

q0 a q1 b q2  q3


39
a b a b

q0 a q1 b q2  q3


40
a b a b

q0 a q1 b q2  q3


41
a b a b

q0 a q1 b q2  q3


42
a b a b

q0 a q1 b q2  q3


43
a b a b

q0 a q1 b q2  q3


44
a b a b

“accept”

q0 a q1 b q2  q3


45
 Language accepted

L = ab, abab, ababab, ...

+
= ab

q0 a q1 b q2  q3


46
Exercise: What language is accepted by
the following NFA ?

0
q0 q1 0, 1 q2
1

47
 Language accepted

L(M ) = {λ, 10, 1010, 101010, ...}

= {10}*
0
q0 q1 0, 1 q2
1 (redundant
state)

48
Remarks:
•The  symbol never appears on the
input tape

•Simple automata:

M1 M2
q0 q0

L( M 1 ) = ? L(M 2 ) = ?
49
Remarks:
•The  symbol never appears on the
input tape

•Simple automata:

M1 M2
q0 q0

L(M1 ) = {} L(M 2 ) = ?
50
Remarks:
•The  symbol never appears on the
input tape

•Simple automata:

M1 M2
q0 q0

L(M1 ) = {} L(M 2 ) = {λ}

51
 Formal Definition of NFAs

M = (Q, ,  , q0 , F )

Q: q0 , q1, q2 
Set of states, i.e.

 : Input aplhabet, i.e. a, b  

: Transition function

q0 : Initial state

F: Accepting states
52
 Transition Function 

 (q , x ) = q1, q2,, qk 

q1
x resulting states with
q x
q1 following one transition
x
with symbol x

qk
53
 (q0 , 1) = q1

0
q0 q1 0, 1 q
2
1

54
 (q1,0) = {q0 , q2}

0
q0 q1 0, 1 q
2
1

55
 (q0 ,  ) = {q0 , q2 }

0
q0 q1 0, 1 q
2
1

56
  (q2 ,1) = 

0
q0 q1 0, 1 q
2
1

57
 *
Extended Transition Function 
Same with  but applied on strings

 (q0 , a ) = q1 
*

q4 q5
a a
q0 a q1 b q2  q3

58
  (q0 , aa ) = q4 , q5 
*

q4 q5
a a
q0 a q1 b q2  q3

59
  (q0 , ab ) = q2, q3, q0 
*

q4 q5
a a
q0 a q1 b q2  q3

60
Special case:

for any state q

q   (q ,  )
*

61
In general
q j   (qi ,w ) : there is a walk from qi to q j
*

with label w

qi w qj

w =  1 2  k
1 2 k
qi qj

62
 The Language of an NFA M
The language accepted by M is:

L(M ) = w1 ,w2,...wn 

where  (q0 ,w m ) = {qi ,..., qk , , q j }

*

and there is some qk  F (accepting state)

63
wm  L(M )
 (q0 ,wm )
*

qi
wm

q0 w qk qk  F
m

wm qj

64
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3


 (q0 , aa) = ?
*

65
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3



 (q0 , aa ) = q4 , q5
*

F
66
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3



 (q0 , aa ) = q4 , q5
*
 aa  L(M )
F
67
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3


 (q0 , ab) = ?
*

68
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3



 (q0 , ab ) = q2 , q3 , q0
*

F
69
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3



 (q0 , ab ) = q2 , q3 , q0
*
 ab  L(M )
F
70
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3


 * (q0 , abaa) = ?

71
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3



 * (q0 , abaa ) = q4 , q5 
F
72
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3



 * (q0 , abaa ) = q4 , q5  aaba  L(M )
F
73
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3


 * (q0 , aba) = ?
74
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3


 * (q0 , aba ) = q1 

F
75
F = q0 ,q5
q4 q5
a a
q0 a q1 b q2  q3


 * (q0 , aba ) = q1  aba  L(M )

F
76
What language is accepted by following
Machine ?

q4 q5
a a
q0 a q1 b q2  q3


L (M ) = ab  *  ab  * {aa }

77
Write the Languages Accepted By Following Finite Automata

78
Develop Finite
Automata for
the Given R.Es

79
NFAs accept the Regular
Languages

80
 Equivalence of Machines

Definition:

Machine M1 is equivalent to machine M 2

if L( M1 ) = L( M 2 )

81
Example of equivalent machines

NFA M1
L(M1 ) = {10} * 0
q0 q1
1

DFA M2 0,1
L(M 2 ) = {10} * 0
q0 q1 1 q2
1
0
82
 Theorem:

=
Languages
Regular
accepted
Languages
by NFAs
Languages
accepted
by DFAs

NFAs and DFAs have the same computation power,

i.e., accept the same set of languages
83
Proof: we only need to show

Languages
accepted  Regular
Languages
by NFAs
AND
Languages
accepted  Regular
Languages
by NFAs

84
 Proof-Step 1

Languages
accepted  Regular
Languages
by NFAs

Every DFA is trivially an NFA

Any language L accepted by a DFA

is also accepted by an NFA
85
 Proof-Step 2

Languages
accepted  Regular
Languages
by NFAs
Any NFA can be converted to an
equivalent DFA

Any language L accepted by an NFA

is also accepted by a DFA
86
 Conversion NFA to DFA
NFA M
a
q a
0 q 1
 q 2
b

DFA M
q0 

87
  * (q0 , a ) = {q1, q2 }
NFA M a
q0 a q1  q2
b

DFA M
q0  a
q1,q2 

88
  * (q0 , b ) =  empty set

NFA M a
q0 a q1  q2
b

DFA M
q0  a
q1,q2 
b

 trap state
89
  (q1, a ) = {q1, q2 }
*

NFA M a  * (q2, a ) = 
q0 a q1  q2 union

b q1,q2 

a
DFA M
q0  a
q1,q2 
b


90
  * (q1 , b) = 
NFA M a  * (q2 , b) = {q0}
a  union
q0 q1 q2
b q0 

a
DFA M b

q0  a
q1,q2 
b


91
NFA M a
q0 a q1  q2
b

a
DFA M b

q0  a
q1,q2 
b

 a, b trap state
92
 END OF CONSTRUCTION

NFA M a
q0 a q1  q2 q1  F
b
a
DFA M b

q0  a
q1,q2 
b
q1, q2 F 

 a, b
93
 General Conversion Procedure

Input: an NFA M

Output: an equivalent DFA M 

with L(M ) = L(M )

94
The NFA has states q0 , q1, q2 ,...

The DFA has states from the power set

, q0 , q1 , q0 , q1 , q1, q2, q3, ....

95
 Conversion Procedure Steps

step
1. Initial state of NFA: q0

Initial state of DFA: q0 

96
Example
NFA M a
q0 a q1  q2
b

DFA M
q0 

97
step
2. For every DFA’s state {qi , q j ,..., qm }

compute in the NFA

 * (qi , a )
(
  * qj , a ) Union
= {qk , ql,..., qn }
...
  * (qm , a )
add transition to DFA
 ({qi , q j ,..., qm }, a ) = {qk , ql,..., qn }
98
Example * (q0 , a) = {q1, q2}
NFA M
a
q0 a q1  q2
b

 (q0 , a ) = q1, q2 
DFA M
q0  a
q1,q2 

99
step
3. Repeat Step 2 for every state in DFA and
symbols in alphabet until no more states
can be added in the DFA

100
Example
NFA M a
q0 a q1  q2
b

a
DFA M b

q0  a
q1,q2 
b

 a, b
101
step
4. For any DFA state {qi , q j ,..., qm }

if some q j is accepting state in NFA

Then, {qi , q j ,..., qm }

is accepting state in DFA

102
Example
NFA M a
q0 a q1  q2 q1  F
b
a
DFA M b

q0  a
q1,q2 
b
q1, q2 F 

 a, b
103
Lemma:
If we convert NFA M to DFA M 
then the two automata are equivalent:
L( M ) = L( M  )

Proof:
We only need to show: L( M )  L( M  )
AND
L( M )  L( M  )
104
Exercise: Design NFA for each of the
following regular expressions and then
convert to equivalent DFA:

i. b*+ab*
ii. a(a+b)*
iii. (a+b)*a
iv. 01* + 10*
v. (0 + 1)* 01 (0 + 1)*

105
Exercise: Convert following NDFA to DFA

106
Exercise: Convert following NDFA to DFA

107
Exercise: Convert following NDFA to DFA

108
Exercise: Convert following NDFA to DFA

109
Exercise: Convert following NDFA to DFA

110
Single Accepting
State for NFAs

111
Any NFA can be converted

to an equivalent NFA

with a single accepting state

112
 Example
a NFA
a b

a Equivalent NFA

a b

b 

113
 In General
NFA

Equivalent NFA
 Single
 accepting

state
114
 Extreme Case

NFA without accepting state

Add an accepting state

without transitions

115
 Properties of
Regular Languages

116
For regular languages L1 and L2
we will prove that:

Union: L1  L2
Concatenation: L1L2
Star: Are regular
L1 *
Languages
Reversal: L1 R

Complement: L1
Intersection: L1  L2
117
We say: Regular languages are closed under

Union: L1  L2
Concatenation: L1L2
Star: L1 *
Reversal: L1 R

Complement: L1
Intersection: L1  L2
118
Regular language L1 Regular language L2

L(M1 ) = L1 L(M 2 ) = L2

NFA M1 NFA M2

Single accepting state Single aceepting state

119
 Example
M1
n0
a
L1 = {a b}
n
b

M2
L2 = ba b a

120
 Union
NFA for L1  L2
M1

 M2

121
 Example
NFA for L1  L2 = {a b}  {ba}
n

L1 = {a b}n
a
b


 L2 = {ba}
b a
122
 Concatenation

NFA for L1L2

M1 M2
 

123
 Example

NFA for L1L2 = {a b}{ba} = {a bba}

n n

L1 = {a b}n

a
L2 = {ba}
b  b a 

124
 Star Operation
NFA for L1 *

  L1 *
M1
 


125
 Example
w = w1w2  wk
NFA for L1* = {a b} *
n
wi  L1


L1 = {a b} n
a
 b 


126
 Reverse
R
NFA for L1
L1 M1 M1

1. Reverse all transitions

2. Make initial state accepting state

and vice versa
127
 Example
M1
a
L1 = {a b}
n
b

M1
a
R
L1 = {ba }
n b

128
 Complement

L1 M1 L1 M1

1. Take the FA that accepts L1

2. Make final states non-final,

and vice-versa
129
 Example
M1
a a, b

L1 = {a b}
n b a, b

M1
a a, b
L1 = {a, b} * −{a b}
n

b a, b

130
 Intersection

L1 regular
We show L1  L2
L2 regular regular

131
DeMorgan’s Law: L1  L2 = L1  L2

L1 , L2 regular

L1 , L2 regular

L1  L2 regular

L1  L2 regular
L1  L2 regular
132
 Example

L1 = {a b}
n regular
L1  L2 = {ab}
L2 = {ab, ba} regular regular

133
 Another Proof for Intersection Closure

Machine M1 Machine M2
FA for L1 FA for L2

Construct a new FA M that accepts L1  L2

M simulates in parallel M1 and M 2

134
 States in M

qi , p j

State in M1 State in M2

135
 FA M1 FA M2

q1 a q2 p1 a p2
transition transition

FA M

q1, p1 a q2 , p2
transition
136
FA M1 FA M2

q0 p0
initial state initial state

FA M

q0 , p0
Initial state
137
 FA M1 FA M2

qi pj pk

accept state accept states

FA M
qi , p j qi , pk

accept states

Both constituents must be accepting states

138
Class Exercise

139
Example:

n0 m0
L1 = {a b} n
L2 = {ab } m

M1 M2
a b
q0 b q1 p0 a p1
a, b b a
q2 p2
a, b a, b
140
Automaton for intersection
n n
L = {a b}  {ab } = {ab}
a, b

q0 , p0 a q0 , p1 b q1, p1 a q2 , p2

b a b a
q1, p2 b q0 , p2 q2 , p1

a b
a, b
141
M simulates in parallel M1 and M 2

M accepts string w if and only if

M1 accepts string w and

M 2 accepts string w

L ( M ) = L ( M1 )  L ( M 2 )

142
End of Lecture

143
Exercise: Convert following NDFA to DFA

 2 a

a b
1 3 3 F
c
c 4

Yes: ab abab cc ccab ccacc ccac abacab

No: b a cb cca
144