1 of 25

Session 5: �Finite State systems – Non Deterministic Finite Automaton – NDFA

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 25

Formal Definition of NFAs

Set of states, i.e.

Input alphabet, i.e.

Transition function

Initial state

Final states

Amity School of Engineering & Technology

3 of 25

3

Alphabet =

Nondeterministic Finite Accepter (NFA)

Amity School of Engineering & Technology

4 of 25

4

Two choices

Alphabet =

Nondeterministic Finite Accepter (NFA)

Amity School of Engineering & Technology

5 of 25

5

No transition

Two choices

No transition

Alphabet =

Nondeterministic Finite Accepter (NFA)

Amity School of Engineering & Technology

6 of 25

6

An NFA accepts a string:

when there is a computation of the NFA

that accepts the string

all the input is consumed and the automaton

is in a final state

AND

Amity School of Engineering & Technology

7 of 25

Example

7

aa is accepted by the NFA:

“accept”

“reject”

because this

computation

accepts

Amity School of Engineering & Technology

8 of 25

8

An NFA rejects a string:

when there is no computation of the NFA

that accepts the string:

  • All the input is consumed and the

automaton is in a non final state

  • The input cannot be consumed

OR

Amity School of Engineering & Technology

9 of 25

Example

9

is rejected by the NFA:

“reject”

“reject”

All possible computations lead to rejection

Amity School of Engineering & Technology

10 of 25

Amity School of Engineering & Technology

11 of 25

Amity School of Engineering & Technology

12 of 25

Amity School of Engineering & Technology

13 of 25

Amity School of Engineering & Technology

14 of 25

Language accepted:

Amity School of Engineering & Technology

15 of 25

Language accepted

(redundant

state)

Amity School of Engineering & Technology

16 of 25

Formal Definition

  • The language accepted by NFA        is:

​

​

​

  • where

​

​

​

  • and there is some 

 

(final state)

Amity School of Engineering & Technology

17 of 25

Amity School of Engineering & Technology

18 of 25

Remarks:

  • The symbol never appears on the

input tape

  • Simple automata:

Amity School of Engineering & Technology

19 of 25

NFA

DFA

  • NFAs are interesting because we can

express languages easier than DFAs

Amity School of Engineering & Technology

20 of 25

Amity School of Engineering & Technology

21 of 25

Amity School of Engineering & Technology

22 of 25

Amity School of Engineering & Technology

23 of 25

Amity School of Engineering & Technology

24 of 25

Amity School of Engineering & Technology

25 of 25

Amity School of Engineering & Technology