MTH 307: Discrete Structures II

(Theory of Computation)
Chapter 2: Finite State Automata
Part 2 - NFA
Dr. Maroun Abi Assaf

1
Example - A Complicated DFA
• Can
0
you guess the language? Difficult 1

1 1 1
000 001 011 111

0 0

1 1 0
0

010 0 100 101 1 110

1
0
0
Example – An Equivalent NFA
Can you guess the language?

0,1

1 0,1 0,1
q1 q2 q3 q4

Bit Strings that have 1 in position third from the end

 2.2 Nondeterministic Finite State Automaton (NFA)

Example of an NFA
NFA – Nondeterministic Finite Automaton

q1 1 q2
Ԑ,0 q3 1 q4

0,1 0,1

1. A state may have 0 or more transitions labeled with

the same symbol.
2.  transitions are possible.
3. Trap states can be omitted

If needed, we can make a distinction between two types of NFAs:

- NFA is an NFA which does not allow ɛ transitions
- ɛ-NFA is an NFA which allows ɛ transitions
4
Definition 1
A nondeterministic finite state automaton or nfa is defined by the
quintuple
M  (Q, ,  , q0 , F )
where Q,  , q 0 , F are defined as for determinis tic finite accepters, but
 : Q  {  {ε }}  P(Q) .
• A string is accepted by an nfa if there is some sequence of
possible moves that will put the machine in a final state at
the end of the string.
• A string is rejected by an nfa only if there is no possible
sequence of moves by which a final state can be reached.

Example 2.8 q0 a q1 a q2 a q3
a
a
q4 q5
Nondeterministic a
 0  (q2 ,0)  
q0 q1 0,1 q2
Example 2.8 1  (q2 ,1)  
ε  (q2 , ε))  {q2 }
nondeterministic  (q1 , ε))  {q1}
It accepts ε ,1010,101010,but not 110,10100.  (q0 ,0)  
𝛿(q1,0) = {q0, q2}
Note for 10 there are two alternative walks.
𝛿(q0, ε) = {q0, q2}
The transitio n function can be extended so as its second argument is a string.
If  * (qi , w)  Q j then Q j is the set of all possible states the nfa may be in,
having started in state qi and having read w. (using notation:

Example 2.8
q0 a q1 ε q2
 (q0 , ε )  {q0 }

ε
 * (q1 , a )  {q0 , q1 , q2 }  (q1 , a )  
 * ( q2 , 
ε )  {q0 , q2 }  ( q2 , a )  
 * (q2 , aa )  {q0 , q1 , q2 }
Definition 2.6
The language L accepted by an nfa M  (Q,Σ, , q0 ,F ) is defined formally
as follows :
L(M)  {w  Σ* : δ*(q0 ,w)  F  }.
In words, the language consists of all strings w for which there is a walk
labeled w from the initial state of the transitio n graph to some final state.
Example 2.10 Does this nfa accept string
Find the language accepted by w=110?
the following nfa.
Dea Configuration!!!
0
q1 0,1 q2  ( q 2 ,0 )  
q0 1

ε  (q2 ,1)  
 ( q 0 ,0 )  
Solution
 (q,2 ,ε) =
𝛿(q ) { qq2 }
2 2
L  {(10) n : n  0}  (q1,1 ,ε) )={qq11}
𝛿(q
• Why Nondeterminism? (Digital computers are completely
deterministic)
1. Nondeterministic machines is sometime helpful in solving
problems easily.

Example Search-and-backtrack algorithms

2. A nfa is an effective mechanism for describing some
complicated languages concisely.

3. There is no essential difference between these two types of

automata.
Given any dfa M, we can find an nfa M’ such that L(M)=L(M’).
Also given any nfa M, we can find a dfa M’ such that L(M)=L(M’).
Example
The following nfa and dfa are equivelant ．
0
q0 q1 0,1 q2 nfa
1
ε

0 0,1
q0 q1 1 q2 dfa
1
0
The Subset Construction Algorithm
Procedure to convert nfa to dfa
1. Create a graph G(D) with vertex {q0}. Identify this vertex as the initial vertex.
2. Repeat the following steps until no more edges are missing.
take any vertex{qi,qj,…,qk} of G(D) that has no outgoing edge for some
a  . Compute  N* (qi , a),  N* (q j , a),...,  N* (qk , a).
If  N* (qi , a)   N* (q j , a )  ...   N* (qk , a )  {ql , qm,..., qn},

create a vertex for G(D) labeled {ql,qm,…,qn} if it is not already exist. Add to
G(D) an edge from {qi,qj,…,qk} to {ql,qm,…,qn} and label it with a.
3. Every state of G(D) whose label contains any q f  FN is identified as a final
vertex.
4. If M N accepts ε , the vertex {q 0} in G(D) is also made a final vertex.
Convert nfa to dfa
Example 1 a

q0 a q1 
ε q2 nfa
b
 ({q0 }, a}  {q1 , q2 } State/Alphabet a b
 ({q0 }, b}  
{q0} {q1,q2} ∅
 ({q1, q2 }, a}  {q1 , q2 }
𝛿 ¿ *{q1,q2} {q1,q2} {q0}
 ( , b}  
 ( , b}   ∅ ∅ ∅
a
b
{q0 } {q1 , q2 }
a
dfa
b
 a, b
 0
Example 2 q0 q1 0,1 q2 nfa
1
ε
 ({q0 },0}  
 ({q0 },1}  {q1} State/Alphabet 0 1

 ({q1},0}  {q0, q2 } *{q0} ∅ {q1}

 ({q1},1}  {q2 } {q1} {q0,q2} {q2}
 ({q0 , q2 },0}  
{q2} ∅ ∅
 ({q0 , q2 },1}  {q1}
 ({q2 },0}   *{q0,q2} ∅ {q1}
 ({q2 },1}  
∅ ∅ ∅

{q0 } 1 {q1}
0 {q0 , q2 }
1 dfa
1
0 {q2 }
0,1 0
0,1

Exercise 1 Give a non-deterministic finite automaton for each of
the following languages.
1.
2.

Exercise 2 Consider the following NFA:

1 0
q1 q2 q3

0,1 0,1

1. Write the formal definition of this NFA.

2. Show if 0110100 is accepted or rejected.
3. Convert this NFA to a DFA.