NFA or Non deterministic finite automata

NFA, conversion to dfa, minimizing dfa

1. Non-deterministic
finite automaton
Er. Deepinder Kaur

2. Not A DFA
•Does not have exactly one transition from every state on
every symbol:
–Two transitions from q
0
on a
–No transition from q
0
(on either a or b)
•Though not a DFA, this can be taken as defining a
language, in a slightly different way

q1

a,b
q0
a
Er. Deepinder Kaur

3. Nondetermistic Finite Automata
•A nondeterministic finite automaton can be
different from a deterministic one in that
–for any input symbol, nondeterministic one can
transit to more than one states.
–epsilon transition
Er. Deepinder Kaur

4. 1
q
2
q
3
q
a
a
a
0
q
}{a
Alphabet =
Nondeterministic Finite Accepter (NFA)
Er. Deepinder Kaur

5. 1
q
2
q
3
q
a
a
a
0
q
Two choices
}{a
Alphabet =
Nondeterministic Finite Accepter (NFA)
Er. Deepinder Kaur

6. No transition
1
q
2
q
3
q
a
a
a
0
q
Two choices
No transition
}{a
Alphabet =
Nondeterministic Finite Accepter (NFA)
Er. Deepinder Kaur

7. a a
0
q
1
q
2
q
3
q
a
a
First Choice
a
Er. Deepinder Kaur

8. a a
0
q
1
q
2
q
3
q
a
a
a
First Choice
Er. Deepinder Kaur

9. aa
0
q
1
q
2
q
3
q
a
a
First Choice
a
Er. Deepinder Kaur

10. aa
0
q
1
q
2
q
3
q
a
a
a “accept”
First Choice
Er. Deepinder Kaur

11. a a
0
q
1
q
2
q
3
q
a
a
Second Choice
a
Er. Deepinder Kaur

12. a a
0
q
1
q
2
q
a
a
Second Choice
a
3
q
Er. Deepinder Kaur

13. a a
0
q
1
q
2
q
a
a
a
3
q
Second Choice
No transition:
the automaton hangs
Er. Deepinder Kaur

14. a a
0
q
1
q
2
q
a
a
a
3
q
Second Choice
“reject”
Er. Deepinder Kaur

15. Er. Deepinder Kaur
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

16. Er. Deepinder Kaur
aa is accepted by the NFA:
0q
1
q
2
q
3q
a
a
a
“accept”
0
q
1
q
2
q
a
a
a
3
q “reject”
because this
computation
accepts
aa
this computation
is ignored

17. Formal Definition of Nondeterministic Finite Automata
•An NFA is a five-tuple:N = (Q, Σ, δ, q
0
, F)
QA finite set of states
ΣA finite input alphabet
q
0
The initial/starting state, q
0
is in Q
FA set of final/accepting states, which is a subset of Q
δA transition function, which is a total function from Q x Σ to 2
Q
δ: (Q x Σ) → P(Q) -P(Q) is the power set of Q, the set of all subsets
of Q
δ(q,s) -The set of all states p such that there is a transition
labeled s from q to p
δ(q,s) is a function from Q x S to P(Q) (but not to Q)
Er. Deepinder Kaur

18. Powerset
•If S is a set, the powerset of S is the set of all subsets
of S:
P(S) = {R | R Í S}
•This always includes the empty set and S itself
•For example,

P({1,2,3}) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
Er. Deepinder Kaur

19. Difference between NFA and DFA
1.In DFA, For a given state on a given input we
reach to a deterministic and unique state.
2. In NFA or NDFA we may lead to more than
one state for a given input.
3. Empty string can label transitions.
5. We need to convert NFA to DFA for designing
a compiler.

Er. Deepinder Kaur

20. •An NFA can easily implemented using a transition
table.
State a b
0 {0, 1} {0}
1 - {2}
2 - {3}
0 1 2 3
a b b
a
b
Er. Deepinder Kaur

21. For any NFA N = (Q, S, d, q
0
, F), L(N) denotes the
language accepted by N which is
L(N) = {x Î S* | d*(q
0
, x) Ç F ¹ {}}.
The Language An NFA Defines
Er. Deepinder Kaur

22. 0,1
1 0
0 1
0,1
Er. Deepinder Kaur
DC
B
E
A
0
Construct a NFA for a language consisting a substring
{0101} over å={0,1}

23. e-Transitions To Accepting States
•An e-transition can be made at any time
•For example, there are three sequences on the empty string
–No moves, ending in q
0
, rejecting
–From q
0
to q
1
, accepting
–From q
0
to q
2
, accepting
•Any state with an e-transition to an accepting state ends up working
like an accepting state too

q0
a q1

q2



b
Er. Deepinder Kaur

24. e-transitions For NFA Combining
•e-transitions are useful for combining smaller automata
into larger ones
•This machine combines a machine for {a}* and a machine
for {b}*
•It uses an e-transition at the start to achieve the union of
the two languages

q0
a q1

q2



b
Er. Deepinder Kaur

25. Incorrect Union
A = {a
n
| n is odd}
B = {b
n
| n is odd}
A È B ?
No: this NFA accepts aab


a
a

b
b


a
a

b
b
Er. Deepinder Kaur

26. Correct Union
A = {a
n
| n is odd}
B = {b
n
| n is odd}
A È B


a
a

b
b


a
a

b
b



Er. Deepinder Kaur

27. Example:
Possible Sequences of 001
•Determining if a given NFA accepts a given string (001) can be done
algorithmically:
q
0
q
0
q
0
q
0
q
3
q
3
(stuck) q
1
q
4
q
4
accepted
•Each level will have at most n states
0 0 1
q
0
0/1
0
0
q
3
q
4
0/1
q
1
q
2
0/1
1
1
Er. Deepinder Kaur

28. NFA – Examples
• Now there are two possible transitions to follow
for state A with a leading 0. One transition is back
to A, consuming the 0, while the other is to B.
• Check for string 00010101

Er. Deepinder Kaur

29. Design a NFA for the language L=all strings over {0,1} that
have atleast two consecutive 0’s or 1’s
q0
q3
q1
q2
q4
0
0
0/1
0/1
1
1
0/1
start
Er. Deepinder Kaur

30. Draw transition table for previous example
0 1
qo {qo,q1} {qo,q3}
q1 q2 ?
* q2 q2 q1
q3 ? q4
*q4 Q4 Q4
Er. Deepinder Kaur

31. Design a NFA for the language L=(ab Ս aba)*
b
q4
q1
star
t
a a
b
a
a
b
b
q0 q3q2
a/b
DFA for the given statement
Er. Deepinder Kaur

32. NFA’s for previous DFA
q1
q2
q1
q2
b
a
b
a
b
a
a
q0
q0
start
start
є
q0
ab
aba
start
Er. Deepinder Kaur

33. Draw the state diagram for NFA accepting language
L=(ab)*(ba)* U aa*
We can construct NFA for the language L in two parts.
L=L1 U L2
Where L1=(ab)*(ba)*
L2=aa*
Er. Deepinder Kaur

34. NFA for (ab)*(ba)*
q1
q2
ba
ab ba
start
q3
a
a
q4
NFA for aa*
start
Er. Deepinder Kaur

35. For Combining the two, we take a new state q0 and join the two NFAs with null
transition
q0
q1
q2
ba
ab ba
ϵ
q3
a
a
q4
ϵ
start
Er. Deepinder Kaur

36. Find NFA with four state for the language
L={(a
n
:n>=0) U (b
n
a:n>=1)}
L=L1 U L2
L1= a
n
:n>=0
L2= b
n
a:n>=1
Er. Deepinder Kaur

37. q1
start
a
q2 q4q3
b
a
b
start
NFA for a
n
NFA for b
n
a


Er. Deepinder Kaur

38. Combined NFA
q1
a
q2 q4
q3
b
a
b
ϵ
Er. Deepinder Kaur

39. NFA Practice
•Design a NFA for language L={0101
n
U 0100|
n>=0}
• Design a NFA to accept strings with a’s and
b’s such that strings end with ‘aa’
•Construct a NFA in which double ‘1’ is
followed by double ‘0’ over {0,1}
Er. Deepinder Kaur

40. Transformation of NFA to DFA
•For every non deterministic finite automata, there exist an
equivalent deterministic finite automata.
• The equivalence is determined in terms of language
acceptance.
•A NFA is nothing but a finite automata in which zero, one
or more transitions on an input symbol is permitted, we
can always construct a finite automata which will simulate
all the moves of NFA on a particular input symbol in
parallel, then get a finite automata in which there will be
exactly one transition on every input symbol, hence it will
be DFA equivalent to NFA
Er. Deepinder Kaur

41. Convert the following NFA into DFA

q0 q1 q2
q3
a
a
b
a,b
a,b
b
start
Er. Deepinder Kaur

42. Solution: Step1: Seek all the transition from starting state q0 for every
symbol in ∑ i.e (a,b).If we get a set of states for same input, consider
the set as a new single state
δ(q0,a)={q0,q1}-------------new state

δ(q0,b)={q0}
Step2: In step1 we are getting a new state {q0,q1}. Repeat step 1 for
this new state only i.e check all transitions of a and b from {q0,q1} as:
δ({q0,q1},a)= δ(q0,a) U δ(q1,a)
= {q0,q1} U {q2}
= {q0,q1,q2}-------------new state
δ({q0,q1},b)= δ(q0,b) U δ(q1,b)
= {q0} U {q1}
={q0,q1}---------------old state
Er. Deepinder Kaur

43. Step 3: Repeat step 2 till you are getting any new state. All those states
that consist of any of the accepting state of given NFA as member
state will be considered as final states
δ({q0,q1,q2},a)= δ(q0,a) U δ(q1,a) U δ(q2,a)
={q0,q1} U {q2} U {q3}
={q0,q1,q2,q3}-------new state
δ({q0,q1,q2},b)= δ(q0,b) U δ(q1,b) U δ(q2,b)
= {q0} U {q1} U {q3}
={q0,q1,q3}--------new state

δ({q0,q1,q2,q3},a)= δ(q0,a) U δ(q1,a) U δ(q2,a) U δ(q3,a)
={q0,q1} U {q2} U {q3} U {q3}
={q0,q1,q2,q3}----------old state
δ({q0,q1,q2,q3},b)=δ(q0,b) U δ(q1,b) U δ(q2,b) U δ(q3,b)
={q0} U {q1} U {q3} U {q2}
={q0,q1,q3,q2}----------old state

Er. Deepinder Kaur

44. δ({q0,q1,q3},a)=δ(q0,a) U δ(q1,a) U δ(q3,a)
={q0,q1} U {q2} U {q3}
={q0,q1,q2,q3}----------old state
δ({q0,q1,q3},b)=δ(q0,b) U δ(q1,b) U δ(q3,b)
={q0} U {q1} U {q2}
={q0,q1,q2}----------old state
Transition table :
δ/∑ a b
q0 {q0,q1} {q0}
{q0,q1} {q0,q1,q2} {q0,q1}
*{q0,q1,q2} {q0,q1,q2,q3} {q0,q1,q3}
*{q0,q1,q2,q3}{q0,q1,q2,q3} {q0,q1,q2,q3}
*{q0,q1,q3} {q0,q1,q2,q3} {q0,q1,q2}
Er. Deepinder Kaur

45. Let us say:
q0----A
{q0,q1}-----B
{q0,q1,q2}-----------C
{q0,q1,q2,q3}---------D
{q0,q1,q3}-----------E

Er. Deepinder Kaur

46. •A is the initial state and C,D and E are final states since they contain q2 and q3 as
member which are final states of NFA
δ/∑ a b
A B A
B C B
*C D E
*D D D
*E D C
Er. Deepinder Kaur

47. A
B
a a
b
b
a
a,b
b
b
C
D
E
start
a
Er. Deepinder Kaur

48. NFA to DFA conversion intuition
1 0
0, 1
q
0
q
1
q
2NFA:
DFA:
1
q
0
{q
0
, q
1
}
1
{q
0
, q
2
}
1
0 0
0
Er. Deepinder Kaur

49. Convert the following NFA to DFA
δ/∑ 0 1
q0 {q0,q1} {q1}
*q1 - {q0,q1}
Er. Deepinder Kaur

50. A

0
1
B
D
start
1
DFA for previous problem
0
1
0
A=[q0]
B=[qo,q1]
C=[q1]
Er. Deepinder Kaur

51. q0
q1
0 0
1
q2
start
Convert the following NFA into DFA
q3
0
1
q2
q4
q2
1
Er. Deepinder Kaur

52. Epsilon Transitions
•Extension to NFA – a “feature” called epsilon
transitions, denoted by ε, the empty string
•The ε transition lets us spontaneously take a
transition, without receiving an input symbol
•Another mechanism that allows our NFA to be in
multiple states at once.
–Whenever we take an ε edge, we must fork off a new
“thread” for the NFA starting in the destination state.
•While sometimes convenient, has no more power
than a normal NFA
–Just as a NFA has no more power than a DFA
Er. Deepinder Kaur

53. Formal Definition of NFAs with ε Moves
•An NFA-ε is a five-tuple:N = (Q, Σ, δ, q
0
, F)
QA finite set of states
ΣA finite input alphabet
q
0
The initial/starting state, q
0
is in Q
FA set of final/accepting states, which is a subset of Q
δA transition function, which is a total function from Q x Σ U {ε} to P(Q)
δ: (Q x (Σ U {ε})) → P(Q)
•A String w in Σ
*
is accepted by NFA iff there exists a path in NFA from q
0
to a
state in F labeled by w and zero or more ε transitions.
•Sometimes referred to as an NFA-ε other times, simply as an NFA.
Er. Deepinder Kaur

54. Formal Definition of ε Closure
•The ε closure (p) is a set of all states which are reachable from state p
on ε transitions such that:
1.Ε- CLOSURE (P)=P where P ЄQ
2.If there exists ε-closure (p) ={q} and δ(q, ε) = r then
ε-closure (p)={q,r}
ε-closure (q0)={q0,q1,q2}
ε-closure (q1)={q1,q2}
ε-closure (q2)={q2}
q
0
ε
0/1
q
2
1
0
q
1
0
q
3
ε
0
1
Er. Deepinder Kaur

55. Epsilon Closure
•Epsilon closure of a state is simply the set
of all states we can reach by following the
transition function from the given state
that are labeled ε.
• ε-closure(q) = { q }
• ε-closure(r) = { r, s}
qStart r s
ε1
0
ε0
1
Example:
Er. Deepinder Kaur

56. Eliminating Epsilon Transitions
1. Compute ε-closure for the current state, resulting in a set of states S.
2. δD(S,a) is computed for all a in S by
a. Let S = {p1, p2, … pk}
b. Compute 
k
i
i
ap
1
),(
=
d and call this set {r1, r2, r3 … rm} This set is achieved
by following input a, not by following any ε-transitions
c. Add the ε-transitions in by computing 
m
i
i
rclosureaS
1
)(),(
=
-=ed
3. Make a state an accepting state if it includes any final states in the ε-NFA.
In simple terms: Just like converting a regular NFA to a
DFA except follow the epsilon transitions whenever
possible after processing an input
To eliminate ε-transitions, use the following to convert to a DFA:
Er. Deepinder Kaur

57. Conversion of NFA with ε to NFA without ε

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

58. Step 1: Find ε closures
ε closure(q)= {q,r,s}
ε closure(r)= {r,s}
ε closure(s)= {s}
Step 2: Find δ for all states
δ’(q,a)= ε closure (δ(δ’(q, ε),a))
= ε closure (δ(ε closure(q),a))
= ε closure(δ((q,r,s),a))
= ε closure (δ(q,a) U δ(r,a) U δ(s,a) )
= ε closure (q U θ U θ )
= ε closure (q)
= {q,r,s}
δ’(q,b)= ε closure (δ(δ’(q, ε),b))
= ε closure (δ(ε closure(q),b))
= ε closure(δ((q,r,s),b))

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

59. = ε closure (δ(q,b) U δ(r,b) U δ(s,b) )
= ε closure (θ UrU θ )
= ε closure (r)
= {r,s}
δ’(q,c)= ε closure (δ(δ’(q, ε),c))
= ε closure (δ(ε closure(q),c))
= ε closure(δ((q,r,s),c))
= ε closure (δ(q,c) U δ(r,c) U δ(s,c) )
= ε closure (θ U θ U s )
= ε closure (s)
= {s}
δ’(r,a)= ε closure (δ(δ’(r, ε),a))
= ε closure (δ(ε closure(r),a))
= ε closure(δ((r,s),a))
= ε closure (δ(r,a) U δ(s,a) ) = ε closure (θ U θ ) = θ


q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

60. δ’(r,b)= ε closure (δ(δ’(r, ε),b))
= ε closure (δ(ε closure(r),b))
= ε closure(δ((r,s),b))
= ε closure (δ(r,b) U δ(s,b) )
= ε closure (r U θ ) = ε closure (r ) ={r,s}
δ’(r,c)= ε closure (δ(δ’(r, ε),c))
= ε closure (δ(ε closure(r),c))
= ε closure(δ((r,s),c))
= ε closure (δ(r,c) U δ(s,c) )
= ε closure (θ U s )
= ε closure (s)
= {s}
δ’{s,a}= ε closure (δ(δ’(s, ε),a))
=ε closure (δ(s,a)) = ε closure (θ )
= θ

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

61. δ’{s,b}= ε closure (δ(δ’(s, ε),b))
=ε closure (δ(s,b))
= ε closure (θ )
= θ
δ’{s,c}=ε closure (δ(δ’(s, ε),c))
=ε closure (δ(s,c) )
= ε closure (s )
= {s}

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

62. q
s
r
a b c
q {q,r,s}{r,s} s
r θ {r,s} S
s θ θ c
Step 4: Draw NFA without ε
transitions
a
a,b
a,b,c
b
b,c
c
q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

63. Conversion of NFA with ε to DFA

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

64. Step 1: Find ε closures
ε closure(q)= {q,r,s}
ε closure(r)= {r,s}
ε closure(s)= {s}
Step 2: Find δ for all new states
δ’{(q,r,s),a}= ε closure (δ((q,r,s),a))
= ε closure (δ(q,a) U δ(r,a) U δ(s,a) )
= ε closure (q U θ U θ )
= ε closure (q)
= {q,r,s}
δ’{(q,r,s),b}= ε closure (δ((q,r,s),b))
= ε closure (δ(q,b) U δ(r,b) U δ(s,b) )
= ε closure (θ UrU θ )
= ε closure (r)
= {r,s}

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

65. Step 1: Find ε closures
ε closure(q)= {q,r,s}
ε closure(r)= {r,s}
ε closure(s)= {s}
Step 2: Find δ for all new states
δ’{(q,r,s),a}= ε closure (δ((q,r,s),a))
= ε closure (δ(q,a) U δ(r,a) U δ(s,a) )
= ε closure (q U θ U θ )
= ε closure (q)
= {q,r,s}
δ’{(q,r,s),b}= ε closure (δ((q,r,s),b))
= ε closure (δ(q,b) U δ(r,b) U δ(s,b) )
= ε closure (θ UrU θ )
= ε closure (r)
= {r,s}

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

66. δ’{(r,s),c}= ε closure (δ((r,s),c))
= ε closure (δ(r,c) U δ(s,c) )
= ε closure (θ U s )
= ε closure (s)
= {s}
δ’{s,a}= ε closure (δ(s,a))
= ε closure (θ )
= θ
δ’{s,b}= ε closure (δ(s,b))
= ε closure (θ )
= θ
δ’{s,c}= ε closure (δ(s,c) )
= ε closure (s )
= {s}

q
Start r
e
s
a
e
b c
Er. Deepinder Kaur

67. Step 3: Draw transition table for all new states
Let q,r,s= D
r,s =E
s =F
q
Start r
e
s
a
e
b c
a b c
D D E F
E θ E F
F θ θ F
Er. Deepinder Kaur

68. D
F
E
a b c
D D E F
E θ E F
F θ θ F
Step 4: Draw NFA without ε
transitions
a
b
c
b
c
c
q
Start r
e
s
a
e
b c
Er. Deepinder Kaur
G
a
a,b

69. Epsilon Elimination Example
qStart r s
ε1
0
ε0
1
q
Start sr
0,1
0,1
Converts to:
Er. Deepinder Kaur

70. Examples
NFA with epsilon-transitions:
Er. Deepinder Kaur

71. Minimizing DFA
• Minimization of automata refers to detect those states of
automata whose presence or absence in a automata does
not affect the language accepted by automata.
• These states are like Unreachable states, Dead states,
Non-distinguishable states etc.
Er. Deepinder Kaur

72. Minimizing DFA
Minimization Algorithm for DFA 
Construct a partition   = { A, Q - A } of the set of states Q ; 
new
 := new_partition( } ; 
while (
new!=
    ) 
          := 
new
 ; 
        
new
 := new_partition( ) 
final
 :=   ; 
function new_partition( ) 
for each set S of    do 
        partition S into subsets such that two states p and q of S are in the
same subset of S 
        if and only if for each input symbol, p and q make a transition to
(states of) the same set of   . 
  The subsets thus formed are sets of the output partition in place of S. 
If S is not partitioned in this process, S remains in the output partition. 
end 
Er. Deepinder Kaur

73. Minimizing DFA
Example:
State 0 1
-> q0 q1 q5
q1 q6 q2
q2
(Final state) q0 q2
q3 q2 q6
q4 q7 q5
q5 q2 q6
q6 q6 q4
q7 q6 q2
Er. Deepinder Kaur

74. Minimizing DFA
For minimizing the above automata,
  Q1= F={q2} Final state
Q2= Q-Q0= {q0, q1, q3,q4,q5,q6,q7}
Hence ,пo = { {q2}, {q0, q1, q3,q4,q5,q6,q7}}
We cannot partition {q2} further, Hence Q1’={q2}
Now Consider another set from пo i.e. {q0, q1, q3,q4,q5,q6,q7}.
Now compare input entries of q0 for all remaining states in this set.
0 1
q0 q1 q5
q1 q6 q2
Here q5 belongs to
Q2 and q2 belongs
to Q1
Hence they are not
1-equivalent
Here q1 and q6 both belongs
to Q2
Er. Deepinder Kaur

75. Minimizing DFA
0 1
q0 q1 q5
q3 q2 q6
Here q1 belongs to Q2 and q2 belongs to Q1
Hence they are not 1- equivalent
0 1
q0 q1 q5
q4 q7 q5
Same StatesQ1 and q7
both belongs
to Q2
Hence they are 1- equivalent
Er. Deepinder Kaur

76. Minimizing DFA
0 1
q0 q1 q5
q5 q2 q6
Here q1 belongs to Q2 and q2 belongs to Q1
Hence they are not 1- equivalent
0 1
q0 q1 q5
q6 q6 q4 q5 and q4both belongs to
Q2
q1 and q6both
belongs to Q2 Hence they are 1-equivalent
Er. Deepinder Kaur

77. Minimizing DFA
0 1
q0 q1 q5
q7 q6 q2
Here q5 belongs to Q2 and q2 belongs to Q1
Hence they are not 1- equivalent
As q0, q4 and q6 are equivalent thus {q0,q4,q6} will be one subset in п1

We will now consider a subset {q1,q3,q5,q7}. Now we will find the 1-
equivalent subset from this subset. Hence we need to compare q1 with
q3,q5 and q7 resp.
0 1
q1 q6 q2
q3 q2 q6
Here q6 belongs to
Q2 and q2 belongs to
Q1
Hence they are not 1-
equivalent
Er. Deepinder Kaur

78. Minimizing DFA
0 1
q1 q6 q2
q5 q2 q6
Here q6 belongs to Q2 and q2 belongs to Q1
Hence they are not 1-equivalent
0 1
q1 q6 q2
q7 q6 q2 q2 belongs to Q1
q6 belongs to
Q2 Hence they are 1-equivalent
Er. Deepinder Kaur

79. Minimizing DFA
i.e. q1 is 1- equivalent to q7. Hence {q1,q7} will be one subset . We
cannot partition this subset further. Hence Q3={q1,q7}
0 1
q1 q6 q2
q7 q6 q2 q2 belongs to Q1
q6 belongs to
Q2 Hence they are 1-equivalent
Er. Deepinder Kaur

80. Minimizing DFA
Now we will compare q3 with q5
0 1
q3 q2 q6
q5 q2 q6 q6 belongs to Q2
q2 belongs to
Q1 Hence they are 1-equivalent
Q4={q3,q5}
Now п1 = { {q2}, {q0, q4,q6}, {q1,q7}, {q3,q5}}
Er. Deepinder Kaur

81. Minimizing DFA
From п1 we can consider a subset {q0,q4,q6}. We will again
compare q0 with q4 and q6. This will be known as 2- equivalent
0 1
q0 q1 q5
q4 q7 q5
Same States
Q1 and q7 both
belongs to Q3
Hence they are 2- equivalent
0 1
q0 q1 q5
q6 q6 q4
Hence they are 2-equivalent
Er. Deepinder Kaur

82. Minimizing DFA
Now
п2 = { {q2}, {q0, q4}, {q6}, {q1,q7}, {q3,q5}}
Similarly q3 and q5 are 2-equivalent
Then
п3 = { {q2}, {q0, q4}, {q6}, {q1,q7}, {q3,q5}}
here п2 = п3  so stop making п sets.
Now we can construct finite automata with minimized state
as M’=(Q’,{0,1}, δ’,q0’,F’)
Where Q’ is set of states in FA
i.e. {[q2],[q0,q4],[q6],[q1,q7],[q3,q5]}
q0’ is initial state i.e. [q0,q4]
F’ is set of final states i.e. [q2]
Er. Deepinder Kaur

83. Minimizing DFA
State 0 1
[q0, q4] [q1, q7] [q3, q5]
[q1, q7] [q6] [q2]
[q2] [q0, q4] [q2]
[q3, q5] [q2] [q6]
[q6] [q6] [q0, q4]
Minimized DFA:
Er. Deepinder Kaur

84. Minimizing DFA
Example:
Er. Deepinder Kaur

85. Minimizing DFA
Initially  Pi = { { 3 } , { 1 , 2 , 4 , 5 , 6 } }. 
By applying new_partition to this  , 
Pi
new
 = { { 3 } , { 1 , 4 , 5 } , { 2 , 6 } } is obtained. 
Applyting new_partition to this  , 
Pi
new
 = { { 3 } , { 1 , 4 } , { 5 } , { 2 } , { 6 } } is obtained. 
Applying new_partition again, 
Pi
new
 = { { 1 } , { 2 } , { 3 } , { 4 } , { 5 } , { 6 } } is
obtained. 
Thus the number of states of the given DFA is already
minimum and it can not be reduced any further. 
Er. Deepinder Kaur

86. Minimizing DFA: Exercises
Construct the minimum state automaton
equivalent to the following transition table:
State A b
-> q0 q1 q0
q1 q0 q2
q2 q3 q1
q3
(Final state) q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
q7 q6 q3
Er. Deepinder Kaur

87. Minimizing DFA: Exercises
Construct the minimum state automaton
equivalent to the following transition table:
State 0 1
-> q0 q0 q3
q1 q2 q5
q2 q3 q4
q3
(Final state) q0 q5
q4 q0 q6
q5 q1 q4
Er. Deepinder Kaur