Non-Deterministic
Finite Automata

This ppt is the work by Dr. Costas Busch, used with permission, and available from http://csc.lsu.edu/~busch/courses/theorycomp/fall2008/ 1

Nondeterministic Finite Automaton (NFA)

Alphabet ={a}

a

q0

q1

a

q2

a

q3
2

Alphabet ={a}

Two choices a q0

q1

a

q2

a

q3
3

Alphabet ={a}

Two choices a q0

q1

a

q2

No transition

a

q3

No transition

4

First Choice a a

a

q0

q1

a

q2

a

q3
5

First Choice a a

a

q0

q1

a

q2

a

q3
6

First Choice a a
All input is consumed a q0

q1

a

q2

“accept”

a

q3
7

Second Choice a a

a

q0

q1

a

q2

a

q3
8

Second Choice a a
Input cannot be consumed a q0

a

q1

a

q2

Automaton Halts

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”
a

q0

q1

a

q2

a

q0

a

q3

because this computation accepts aa

q1

a

q2

a

q3

“reject”

this computation is ignored
11

Rejection example a a

q0

q1

a

q2

a

q3
12

First Choice a “reject” a q0

q1

a

q2

a

q3
13

Second Choice a a

q0

q1

a

q2

a

q3
14

Second Choice a a

q0

q1

a

q3

“reject”

q2

a

15

Another Rejection example a a a

a

q0

q1

a

q2

a

q3
16

First Choice a a a

a

q0

q1

a

q2

a

q3
17

First Choice a a a
Input cannot be consumed a q0

q1

a

q3

a

q2

“reject”

Automaton halts

18

Second Choice a a a

a

q0

q1

a

q2

a

q3
19

Second Choice a a a
Input cannot be consumed a q0

q1

a

q2

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”

a

q0

q1

a

q2

a

q0

a

q3

“reject”

q1

a

q2

a

q3

All possible computations lead to rejection
22

aaa is rejected by the NFA:
“reject”
a

q0

q1

a

q2

a

q0

a

q3

q1

a

q2

a

q3

“reject”

All possible computations lead to rejection
23

Language accepted:L {aa}

a

q0

q1

a

q2

a

q3
24

Epsilon 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
String

aa

a

q1 

q2

a

q3

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
String

a

aaa

q1 

q2

a

q3

is rejected
33

Language accepted:L {aa}

q0

a

q1 

q2

a

q3

34

Another NFA Example

q0

a

b

q1

q2



q3


35

a b

q0

a

b

q1

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

Another NFA Example

0 q0 1

q1

0, 1 q2


47

Language accepted

L( M )   , 10, 1010, 101010, ...
10 *
0
q0

1

q1



0, 1 q2

(redundant state) 48

Remarks:



•The symbol never appears on the input tape
•Simple automata:

M1 q0 M2

L(M1 ) = {}

L( M 2 ) { }

q0

49

•NFAs are interesting because we can express languages easier than DFAs
NFA

q0

a

M1

DFA

q2

q1

a q0 L( M1 ) = {a}

a

M2

a

q1

L( M 2 ) = {a}
50

Formal Definition of NFAs

M  Q, ,  , q0 , F 

 q0 , q1, q2 

Q:

Set of states, i.e.

:

Input aplhabet, i.e. a, b

:

Transition function

 

q0 : Initial state

F:

Accepting