CSE2013

Theory of Computation
MODULE - 2
School of Computer Science and Engineering
Module -2
• Finite State Automata
• Finite automata
• Deterministic Finite automata (DFA)
• Non-deterministic Finite automata (NFA)

• NFA without epsilon transition

• Conversion of NFA to DFA
• Equivalence of NFA and DFA
• Minimization of DFA
FINITE AUTOMATA
• Finite automata are computing devices that accept/recognize regular
languages and are used to model operations of many systems we find
in practice.
• Their operations can be simulated by a very simple computer program
Informal Explanation
• Finite automata are finite collections of states with
transition rules that take you from one state to
another.
• Original application was sequential switching
circuits, where the “state” was the settings of
internal bits.
• Today, several kinds of software can be modeled
by FA.

4
Representing FA
• Simplest representation is often a graph.
• Nodes = states.
• Arcs indicate state transitions.
• Labels on arcs tell what causes the transition.

5
Example: Recognizing Strings
Ending in “ing”
Not i or g

Not i
Not i or n i

nothing Saw i Saw in Saw ing

i n g

Start
i

6
Finite State Automata (FA)
0 1 1 0 0

Finite
Control

• One-way, infinite tape, broken into cells

• Read-only tape head.
• Finite control, i.e., finite number of states, and
• A string is placed on the tape, read head is positioned at the left end.
FA will read the string one symbol at a time until all symbols have been read.
The FA will then either accept or reject the string.
FSA Applications
• Lexical analysis (Compiler) recognition of tokens
• Thermostats (fridge)
• Elevators
• Train Track Switches
• Text editing
• Image compression
• Computer Network
Deterministic Finite State Automata (DFA)

A deterministic finite automaton is a 5-tuple M = (Q, Σ, , q0, F), where

• Q - is a finite set of states
• Σ - is a finite set of input symbols
• q0  Q - is the start state (initial state)
• F  Q - is the set of accept states (final states)
•  : Q  Σ → Q - is the transition function
f:A→B
A B

x1 f(x1) = y1

x2 f(x2) = y2

x3 f(x3) = y3
.

.
x. f(x) = y
 Q = {q0 , q1 } , Σ = { a, b}

n(Q) = 2 , n(Σ) = 2

A x B = { (x, y) / x  A , y  B } - Cartesian Product of A and B

n(A x B) = n(A) . n(B)

Q x Σ = { (q0, a), (q0, b), (q1, a), (q1, b) }

n(Q x Σ) = n(Q). n(Σ) = 2 . 2 = 4

:QΣ→Q
:QΣ→Q
QΣ Q

(q0, a) (q0, a ) = q1

(q0, b)
(q1, b ) = q0
(q1, a)

(q1, b)

(q0, a ) = q1
Examples
M = ( {q0 , q1 , q2 , D } , {a, b} , q0 ,  , {q2} ) a b
q1 D
where (q0 , a) = q1 (q0 , b) = D q0
q1 q2
(q1 , a) = q1 (q1 , b) = q2 q1 D q2

(q2 , a) = D (q2 , b) = q2 q2 D D

(D , a) = Da (D , b) = D D
Transition Table or State Table

q0 a b b
q1 q2
Transition diagram or State diagram
b a
D
a,b
Extended Transition Function
^
Extend  to  : Q  *
 Q
a q1 b c
^ q0 q2 q3
1)  (q,  ) q, q  Q ^ ^
 (q0 , abc)  ( (q0 , ab), c)
* ^
2) x   , a  , q  Q  ( ( (q0 , a ), b), c)
^
^ ^
 ( ( ( (q0 ,  ), a ), b), c)
 (q, xa)  ( (q, x), a)
 ( ( (q0 , a ), b), c)
 ( (q1 , b), c)
 (q2 , c ) q3
Grammar and Automata
L(M) is the of strings accepted by M
^
L( M ) {x / x   ,  ( q0 , x )  F }
*

L(G) is the of strings generated by G

*
*
L (G ) {w  T / S  w}

M - Automata is an accepting device of the language

L(G ) {

G - Grammar is the generating device of the language

 Examples
1) a
a,b
n
q0 b a,b
L( M ) {a b / n 0}
q1 q2
Trap state

a,b

2) q1  {a, b}
*
L( M ) 
3) a

q0 q1 n
L( M ) {(ab) / n 0}
b
b a

a,b
4) a,b  {a, b}
a,b

q0 q1
L(M ) 
5)

W1 =gmcgwmg W2 =gmwgcmg
6)

a,b
q0 q1

a,b a,b

 {a, b} q2

*
L( M ) {x / x   , | x |3k , k 0,1,2,...}
7) FORTRAN identifier Max length = 6
9 9 9 9 9
,1,
…
0, 1,… 0, 1,… 0, 1,… 1,…
,0 , , , , 0,
,Z , Z ,Z ,Z ,Z ,Z
, … , … , … , … , …
B,… , B ,B ,B ,B ,B
A, A A A A A
q0 q1 q2 q3 q4 q5 q6

8) Decimal Integer 0,1,…9 0,1,…9

9
1 ,… .
q0 q1 q2
DFA
Language accepted by a FSA is called regular set or regular language

Theorem: A language L is called regular if and only if there exists some

deterministic finite accepter M such that
L = L(M)
Problems
Give DFA (DFSA) for the following languages:
1) L(G) = { abnam / n ≥ 2, m ≥ 3 }
2) L(G) = { w1abw2 / w1 , w2  {a, b}* }
3) L(G) = {w1aw2 / |w1| ≥ 3, |w2| ≤ 5}
4) L(G) = { w {a, b}* / |w| mod 3 = 0}
5) L(G) = { w {a, b}* / |w| mod 5 ≠ 0}
6) L(G) = { an / n ≥ 4 }
7) L(G) = { an / n ≠ 4 }
8) Let L = { anb / n≥ 0 }, find DFA for L2.
9) L(G) = { an / n is either a multiple of 3 or a multiple of 5}
10) L(G) = { an / n is either a multiple of 3, but not a multiple of 5}
1) L(G) = { abnam / n ≥ 2, m ≥ 3 }

2) L(G) = { w1abw2 / w1 , w2  {a, b}* }

3) L(G) = {w1aw2 / |w1| ≥ 3, |w2| ≤ 5}

4) L(G) = { w {a, b}* / |w| mod 3 = 0}

5) L(G) = { w {a, b}* / |w| mod 5 ≠ 0}
= {a, b, aa, ab, ba, bb, aaa, aab, aba, abb , baa, bab, bba, bbb , . . .}

6) L(G) = { an / n ≥ 4 }
7) L(G) = { an / n ≠ 4 } = = {ε, a, a2, a3, a5, a6 , a7, a8 , a9, a10 , . . .}

8) Let L = { anb / n≥ 0 }, find DFA for L2.

L2 ={b, ab, a2b, a3b , a4b , a5b, . . .}{b, ab, a2b, a3b , a4b , a5b, . . .}
={bb, bab, ba2b, ba3b , ba4b , ba5b, . . .abb, abab, aba2b, . . .}
9) L(G) = { an / n is either a multiple of 3 or a multiple of 5}
10) L(G) = { an / n is either a multiple of 3, but not a multiple of 5}
Deterministic Finite State Automata (DFA)

A deterministic finite automaton is a 5-tuple M = (Q, Σ, , q0, F), where

• Q - is a finite set of states
• Σ - is a finite set of input symbols
• q0  Q - is the start state (initial state)
• F  Q - is the set of accept states (final states)
•  : Q  Σ → Q - is the transition function
Non-deterministic Finite Automata (NFA)
A non-deterministic finite automaton is a 5-tuple M = (Q, Σ, , q0, F),
where
• Q - is a finite set of states
• Σ - is a finite set of input symbols
• q0  Q - is the start state (initial state)
• F  Q - is the set of accept states (final states)
•  : Q  Σ → 2Q - is the transition function

(qi , a) = { qj , q j }
 Q = {q0 , q1 } , Σ = { a, b}

n(Q) = 2 , n(Σ) = 2

ρ(Q) = 2Q = { {q0} , {q1} , {q0 , q1 }, {ϕ} } - Power set of Q

n(2Q) = 2n(Q) = 22 = 4
 : Q  Σ → 2Q
QΣ 2Q

(q0, a) (q0, a ) = {q0 q1}

(q0, b)
(q1, b ) = { q0}
(q1, a)

(q1, b)

(qi, a ) = {qj , qk} qj

a

qi
a qk
Example - 1
a a
 (q0 , a) {q1 , q4 }
q1 q2 q3
a
 (q1 , a) {q2 }
q0 a
 (q2 , a) {q3}
a q4 q5
 (q4 , a) {q5 }
a  (q5 , a) {q4 }
3 2n
L( M ) {a }  {a / n 1}
Example - 2

a b a b

a b q0 {q0 , q1} 
q0 q1 q2

q1  {q1 , q2 }

q2  
n m
L( M ) {a b / m, n 1}
NFA to DFA (Procedure)
1. Create a graph GD 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 , q j ,...., qk } of GD that as no outgoing edge
for some input. Compute  {qi , a ),  {q j , a ),...,  {qk , a.)

If  {qi , a )   {q j , a )  ...   {qk , a ) {ql , qm ,..., qn }

create a vertex for GD labeled {ql , qm ,..., qn }if it does not
already exist. Add to GD an edge from {qi , q j ,...., qk } to
{ql , qm ,..., qn } and labeled it with a .
NFA to DFA (Procedure)
3. Every vertex of GD whose label contains any q f  F is identified as a
final state.

4. If MN accepts  , the vertex {q0 } in GD is also a final state.

Example – 1 q1 a
q2
a q3
a

q0 a

a
A

q4 q5

a
δ(q0 , a) = {q 1 , q4}
q0

δ(q1 , a) U δ(q4 , a) = {q2}U{q5} = {q2 , q5}

a q1,q4
q0
 a q1,q4 a
q0 q2,q5

δ(q2 , a) U δ(q5 , a) = {q3}U{q4} = {q3 , q4}

a a a
q0 q1,q4 q2,q5 q3,q4

δ(q3 , a) U δ(q4 , a) = {ϕ}U{q5} = {q5}

a q1,q4 a a a
q0 q2,q5 q3,q4 q5
 δ(q5 , a) = {q4}
a a a a a
q0 q1,q4 q2,q5 q3,q4 q5 q4

δ(q4 , a) = {q5}

q0 a q1,q4 a a a a
q2,q5 q3,q4 q5 q4

a
Example – 2

a b

a b q2
q0 q1

q0 δ(q0 , a) = {q0 , q1}

a q0,q1
q0

δ({q0 , q1}, a) = δ(q0 , a) U δ(q1 , a) = {q0 , q1}U{ϕ} = {q0 , q1}

a

a q0,q1
q0
δ({q0 , q1}, b) = δ(q0 , b) U δ(q1 , b) = {ϕ}U{q1 , q2} = {q1 , q2}

a b
q0 q0,q1 q1,q2

δ({q1 , q2}, b) = δ(q1 , b) U δ(q2 , b) = {q1 , q2}U{ϕ}= {q1 , q2}

a b

a b
q0 q0,q1 q1,q2
 b
a

a q0,q1 b
q0 q1,q2
Problems
1) Find a DFA equivalent to the NFA with initial state p, final state q,
and another state r having transitions:
(p , 0) = p , (p , 0) = q , (p , 1) = q , (q , 0) = r ,
(q , 1) = r , (r , 1) = r
2) Construct a DFA equivalent to the NFA with initial state p, final state
q, and transitions:
(p , a) = p , (p , a) = q , (q , b) = q , (q , b) = p
Omit inaccessible states.
NFA with  moves (-NFA)
A non-deterministic finite automaton with  moves is a 5-tuple
M = (Q, Σ, , q0, F), where
• Q - is a finite set of states
• Σ - is a finite set of input symbols
• q0  Q - is the start state (initial state)
• F  Q - is the set of accept states (final states)
•  : Q  Σ U { } → 2Q - is the transition function
-closure
-closure of a state q is the set of all states reachable from q through
-moves only and including q itself.

-closure(q0) = {q0 , q1 , q2 , q3} ECLOSURE(q0)

-closure(q1) = { q1 , q2 , q3}
a b c d
-closure(q2) = { q2 , q3}
  
-closure(q3) = {q3} q0 q1 q2 q3

n m k p
L( M ) {a b c d / m, n, k , p 0}
 Q = {q0 , q1 } , Σ = { a, b} , Σ U { } = { a, b, }

n(Q) = 2 , n(Σ U { } ) = 3

Q x (Σ U { } ) = {(q0, ), (q0, a), (q0, b), (q1, ), (q1, a), (q1, b) }

ρ(Q) = 2Q = { {q0} , {q1} , {q0 , q1 }, {ϕ} } - Power set of Q

n(2Q) = 2n(Q) = 22 = 4
 : Q  ( Σ U { })→ 2Q
Q  (ΣU { }) 2Q

(q0 , ) (q0,  ) = {q0 q1}

(q0, b)
(q1, b ) = { q0}
(q1, a)

(q1, b)

(q1 , ))

(qi, ) = {qj , qk} qj



qi
 qk
Eliminating -transitions (Procedure)
Let M = (Q, Σ, , q0, F) be an NFA with -moves. Then the equivalent
DFA M’ = (Q’, Σ, ’, q0’, F’) is constructed as follows:
1. q0’ = -closure(q0) is the start state of M’
2. F’ is the set of states that contain at least one final state of M
3. ’(S, a) is computed by,
a) let S = {p1 , p2 ,. . . ., pk}
b) (pk1, a) U (p2, a) U . . . . U (pk, a)
 ( pi , a ) {r1 , r2 ,...., rm }
i 1

c) ’(S, a) = -closure(r ) U -closure(r

m
2) U . . . . U -closure(rm)
 ( p, a )  
' 1
j 1 -closure(r )
j
Example-1

1 2
0
n m k
 
L( M ) {0 1 2 / m, n, k 0}
q0 q1 q2

-closure(q0) = {q0 , q1 , q2 }
[q0 , q1 , q2]
S = {q0 , q1 , q2}
(S, 0) = (q0, 0) U (q1, 0) U (q2, 0) = {q0} U{ϕ}U{ϕ}= {q0}
’(S, 0) = -closure(q0) = {q0 , q1 , q2}
0
[q0 , q1 , q2]

(S, 1) = (q0, 1) U (q1, 1) U (q2, 1) ={ϕ} U {q1} U{ϕ}= {q1}

’(S, 1) = -closure(q1) = { q1 , q2} 0
[q0 , q1 , q2]
1

[q1 , q2]
(S, 2) = (q0, 2) U (q1, 2) U (q2, 2) ={ϕ} U {ϕ} U {q2} = {q2}
’(S, 2) = -closure(q2) = { q2}

0
[q0 , q1 , q2]
1
2

[q1 , q2] [ q2 ]
S = {q1 , q2}
(S, 1) = (q1, 1) U (q2, 1) = {q1} U{ϕ}= {q1}
’(S, 1) = -closure(q1) = {q1 , q2}

0
[q0 , q1 , q2]
1
2

1 [q1 , q2] [ q2 ]
(S, 2) = (q1, 2) U (q2, 2) = {ϕ} U {q2} = {q2}
’(S, 2) = -closure(q2) = {q2}

0
[q0 , q1 , q2]
1
2

[q1 , q2] 2
1 [ q2 ]
S = {q2}
(S, 2) = (q2, 2) = {q2} = {q2}
’(S, 2) = -closure(q2) = {q2}

0
[q0 , q1 , q2]
1
2
2
[q1 , q2] 2
1 [ q2 ]
 0
p0
1
2
2
p1 2
1 p2

n m k
L( M ) {0 1 2 / m, n, k 0}
Example-2
a b c d

 q1  
q0 q2 q3

L( M ) {a n b m c k d p / m, n, k , p 0}

-closure(q0) = {q0 , q1 , q2 , q3}

-closure(q1) = { q1 , q2 , q3}
-closure(q2) = { q2 , q3}
-closure(q3) = {q3}
 a
[q0 , q1 , q2 , q3]
b
d
d
b [q1 , q2 , q3] d
[q3]

c
d
c

[ q2 , q3 ] c
Problems:
1) Draw the transition diagram of the NFA with initial state p, final
state q, and another state r, having transitions
( p , 0) = q , (p , 1) = q , (q , 0) = p , (q , 1) = q , (q , 0) = r ,
(q , ε) = r , (r , 1) = q
Which language does it accept? Find its equivalent DFA.
2) Find the DFA equivalent to the following NFA with ε edges.
( a , ε) = {b, c} , (b , 0) = d , (d , 0) = e , (e , 0) = b , (c , 0) = f ,
(f , 0) = g , (g , 0) = h , (h , 0) = i , (i , 0) = c
Where a is an initial state, b and c are two final states.
Regular Expression
Let  be a given alphabet. Then
1)  ,  , and any a are all regular expressions. These are called
primitive regular expressions.
2) If r1 and r2 are regular expressions, then
- r1 + r2 is a regular expression.
- r1  r2 is a regular expression.
- r1* is a regular expression.
- (r1 ) is a regular expression.
3) A string is a regular expression, if and only if it can be derived from the
primitive regular expressions by a finite number of applications of rules in
(2).
Regular Expression
Check whether the given string is a regular expression,
S ={ a, b, c}, the string (a + b . c)* . (c + )
r1 = a , r 2 = b , r 3 = c
r4 = r2 . r3 = b . c
r5 = r1 + r4 = a + b . c
r6 = (r5) = (a + b . c)
r7 = r6* = (a + b . c)*
r8 = 
r9 = r3 + r8 = c + 
r10 = (r9)= (c + )
Languages associated with regular
expressions
The language L(r) denoted by a regular expression r is defined by the
following rules,
1)  is a r.e denoting the empty set L () = {}
2)  is a r.e denoting the empty set L () = {}
3) For any a is a r.e denoting the set L (a) = {a}
If r1 and r2 are regular expressions, then
4) L (r1 + r2) = L{r1} U L{r2}
5) L (r1 . r2) = L{r1}.L{r2}
6) L ((r1)) = L(r1)
7) L (r1*) = (L (r1))*
Languages associated with regular
expressions
Exhibit the language L(a* . (a + b)) in set notation
L(a* . (a + b)) = L(a*) . L( (a + b))
= (L(a))*. L(a + b))
= (L(a))*. L(a) U L(b)
= { a }*. { a } U { b }
= {, a, aa, aaa,. . . }. { a, b}
= {a, aa, aaa, aaaa,. . . ,b, ab, aab, aaab,. . . }
Languages associated with regular
expressions
r = (a + b)*. (a + bb), find L(r)
L(r) = L((a + b)*. (a + bb))
= L((a + b)*). L(a + bb)
= (L(a + b))*. L(a + bb)
= (L(a) U L(b))* . L(a) U L(bb)
= {a, b}* . {a} U {b}.{b}
= {a, b}* . {a} U {bb}
= {a, b}* . {a, bb}
= {, a, b, aa, ab, ba, bb,. . .} . {a, bb}
= {a, aa, ba, aaa, aba, baa, bba,. . .,bb, abb, bbb, aabb, abbb, . . .}
Examples
Describe the following sets by regular expressions
1) L1 = the set of all strings of 0’s and 1’s ending with 00
2) L2 = the set of all strings of 0’s and 1’s and beginning with 0 and ending
with 1
3) L3 = {, aa, aaaa, . . . }
4) The set of all strings of 0’s and 1’s with at least two consecutive zeros
5) The set of all strings of a’s and b’s whose length is divisible by 6
6) The set of all strings of a’s and b’s whose 5th last symbol is b
7) The expression r = (aa)* (bb)*b denotes the set of strings with an even
number of a’s followed by an odd number of b’s
8) L4 = {an bm / n ≥ 4 , m ≤ 3}
Examples
1) (0 + 1)*00
2) 0(0 + 1)*1
3) (aa)*
4) (0 + 1)*00(0 + 1)*
5) [(a + b)6]*
6) (a + b)*b(a + b)4
7) L(r) = {a2n b2m+1 / n ≥ 0 , m ≥ 0 }
8) aaaaa*( + b + bb + bbb)
Regular expression to -NFA
Theorem: Let r be a regular expression, then there exists some NFA
with -moves that accept L(r). Consequently, L(r) is a regular language.
Proof: We begin with automata that accepts the language for primitive
regular expressions  ,  , and any a
i) a) NFA accepts 
q0 qf

b) NFA accepts  c) NFA accepts a

a
 q0 qf
q0 qf
Regular expression to -NFA
ii) NFA accepts L(r)
M(r)

iii) NFA accepts L(r1+r2)

M(r1)

 

M(r2)


 Regular expression to -NFA
iii) NFA accepts L(r1.r2)
M(r1) M(r2)

 

iii) NFA accepts L(r1*) 

M(r1)




Examples
1) The set of integers
(1+2+. . . +9)(0+1+. . . +9)*
2)The set of decimal numbers

.
(1+2+. . . +9)(0+1+. . . +9)* (0+1+. . . +9)*
3) Strings over {a, b} and length multiple of 3
[(a + b)(a + b)(a + b)]*
Examples
1) (0 + 01)*
2) (a + b)*b(a + bb)*
3) (a+b)*abb
4) aa* + ab a*b*
5) (abab)* + (aa*+ b)*
6) ((00*)*1)*
7) (01)* + 1(01)* + (01)*0 + 1(01)*0
1) (0 + 01)*
0
0

1
1

0  1
01
 0
 
0 + 01
 
0  1


(0 + 01)* 0
 
 

 
0  1


2) (a + b)*b(a + b)*

a a

b
b

a
 

a+b
 b 
(a+b)*

a 

 

 
b

(a + b)*b(a + b)*

 

a a 
  
 b  

   
b b
 
DFA to Regular Expressions
Theorem: If L = L(A) for some DFA A, then there is a regular
expression r such that L = L(r)

Theorem: (Arden’s Theorem)

Let P and Q be two regular expressions over . If P does not
contain , then the following equation in R,
R = RP + Q
has unique solution, given by
R = P*Q
Algebraic Method using Arden’s
Theorem
The following method is an extension of Arden’s theorem. It is used to
find r.e recognized by the transition system.
The following assumptions are made regarding the transition system:
1) The transition system does not have -moves
2) It has one initial state say v1
3) Its vertices are v1 , v2 , . . .,vn
4) αij denotes the r.e representing the set of labels of edges from vi to vj,
when there is no edge, αij = . Consequently, we can get the following
set of equations in v1 , v2 , . . .,vn
Algebraic Method using Arden’s
Theorem
v1 = α11 v1+ α12 v2 + . . . .+ α1n vn
v2 = α21 v1+ α22 v2 + . . . .+ α2n vn
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
vi = αi1 v1+ αi2 v2 + . . . .+ αin vn
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
vn = αn1 v1+ αn2 v2 + . . . .+ αnn vn + 
By repeatedly applying substitutions and Arden’s theorem, we can
express vi in terms of αij
Examples
1) a

q0 q1
b a
a b
a,b
q2 b q3

Since there are 4 states namely q0 , q1 , q2 and q3 , therefore we have 4 equations,

q0 =  + a q1 + b q2 ----------- (1)
q1 = b q0 + a q3 ----------- (2)
q2 = a q0 + b q3 ----------- (3)
q3 = a q3 + b q3 ----------- (4)
From (4),
q3 = q3 (a + b) + 
By applying Arden’s theorem,
q3 = (a + b)*  =  -----------(5) a.  = 

Sub. (5) in (3) and (4), we get a.  = a

q2 = a q0 -----------(6)
q1 = b q0 -----------(7)
Sub. (6) and (7) in (1), we get
q0 =  + ab q0 + ba q0

= (ab + ba) q0 + 
By applying Arden’s theorem,
q0 = (ab + ba)*  = (ab + ba)*
1) Construct the regular expression for the following FSA:

Since there are 3 states namely q0 , q1 and q2 , therefore we have 3 equations,

q0 = 1 q0 + 0 q1 ----------- (1)
q1 = 1 q0 + 1 q2 ----------- (2)
q2 =  + 0 q1 ----------- (3)
Sub. (3) in (2), we get
q1 = 1 q0 + 1 ( + 0 q1)
= 1 q0 + 1 + 10 q1
= 10 q1 + (1 + 1 q0)
By applying Arden’s theorem,
q1 = (10)* (1 + 1 q0)
= (10)* 1 + (10)* 1 q0 -----------(4)

Sub. (4) in (1), we get

q0 = 1 q0 + 0 [ (10)* 1 + (10)* 1 q0]
= [1 + 0(10)* 1] q0 + 0(10)* 1
By applying Arden’s theorem,
2)

Since there are 3 states namely q0 , q1 and q2 , therefore we have 3

equations,
q0 = aq1 ----------- (1)
q1 = a q1 + b q2 ----------- (2)
q2 =  + b q2 ----------- (3)
From (3),
q2 = b q2 + 
By applying Arden’s theorem,
q2 = b*  = b* -----------(4)
Sub. (4) in (2), we get
q1 = a q1 + b b*
By applying Arden’s theorem,
q1 = a* b b* -----------(5)
Sub. (5) in (1), we get
q0 = a a* b b*
Find regular expressions for the languages accepted by the following
automata:-
1)

2)
Minimization of Automata
Example-1
0

q0 q1
0
1 1

q2 q3

0 1
1
0 0,1
q4 q5
1
0
Minimum State Automaton
0,1
0 0

J0 U J1 1 1
J2 U J3 U J4 J5

0,1
0 0

1 1
[] [1] [11]

The minimum state automaton accepting L is unique

Let M be a DFA. Let ≡ be the equivalence relation on the states of M such that
p is equivalent to q
p ≡ q if for any x in Σ*
(p , x) and (q , x) are both in F or both not in F

p and q are distinguishable if there exists x in Σ*

(p , x)  F  (q , x) 
F
or
(p , x) F  (q , x)  F

x is called the distinguishable sequence.

Minimization of Automata
Example-1
0

q0 q1
0
1 1

q2 q3

0 1
1
0 0,1
q4 q5
1
0
 q0 q1q2 q3 q4 q 5

q0 q1q 5 q2 q3 q4

q0 q1 q5 q2 q3 q4
Example-2
 q0 q1q2 q3 q4 q5 q6 q7

q0 q1q3 q4 q5 q6 q7 q2

q0 q1q4 q6 q7 q3 q5 q2

q0 q 4 q1q7 q6 q3 q5 q2
• Example-3
 abcdefgh

abcefgh d

ag bcefh d

ag ce bfh d
ag ce bf d h
Minimization of DFA
Myhill Nerode Theorem- Table Filling Method
Minimized DFA