 OBJECTIVE : To know the different types of finite automata and regular languages

UNIT I FINITE AUTOMATA AND REGULAR EXPRESSIONS 9

Basic Definitions - Finite Automaton - DFA and NFA - Finite Automaton with -moves -
Equivalence of NFA and DFA - Equivalence of NFAs with and without -moves - Regular
Languages - Regular Expression - Equivalence of finite Automaton and regularexpressions-
Minimization of DFA

Introduction
Strings, Alphabets and Languages
Symbol :
 A symbol is abstract entity.
 Letters and digits are examples of symbols.
String :
 A string or word is finite sequence of symbol.
 Example
a, b and c are symbols and abcd is a string.
 The length of a string w is the number of symbols composing the string.
 It is denoted as |w|
 Example :
abcd has length 4
The empty string E, the string consisting of zero symbols |E| =0.
 A prefix of a string is any number of leading symbols of the string.
 Example :
String abc has prefixes,
E, a, ab, abc.
 A suffix is any number of trailing symbols of that string.
 Example :
String abc has suffixes
E, c, bc, abc
 A prefix or suffix of a string other than the string itself is called a proper prefix
or suffix.
 The concatenation of two strings is the string formed by writing the first
followed by the second without space.
 For eg.
 Concatenation of dog and house is doghouse
  The empty string is the identity for concatenation operator
∈w = w∈ = w
Alphabet :
 An alphabet is a finite set of symbols.
Language :
 A language is a set of string of symbols from some one alphabet.
 The empty set φ and the set consisting of the empty string { ∈ } are
languages.
 The set of all string over a fixed alphabet ∑ ¿¿ , this language is denoted by
¿
∑ ¿¿
 Example
1.    a
¿
∑ ¿ { ∈, a,aa, aaa, .. . }

2. ∑ = { 0, 1 }
¿
∑ = { ∈, 0, 1, 01 , 10 , 00 , 11, 000, 000, ... }
Set Notation :
 Set is a collection of objects without repetition.
 Finite sets may be specified by two forms
i. listing their members between brachets.
ii. Set former
{x | p (x )}
{ x in A | p ( x ) }
 If every member of A is a member of B, then we write A ⊆ B and say A is
contained in B.
 If A ⊆ B but A ≠ B , that is every member of A is in B and there is same
member of B that is not in A, then we write A ⊆ B .
 A and B are equal if they have same members That is A = B iff A ⊆ B nad
B⊆A .
Operations on Sets :
1. A ∪ B , the union of A and B is
{ x | x is in A of x is in B }
2. A ∪ B , the intersection of A and B is
{ x | x is in A and x is in B }
3. A – B, the difference of A and B is
{ x | x is in A and x is not in B }
4. A x B, the Cartesian product of A and B, is the set of ordered pairs (a, b) such
that a is in A and b is in B.
 5. 2A , is the power set of A is the set of all, subsets of A
Example :
Let A = {1, 2}
B = {2, 3}
1. A ∪ B = {1, 2, 3}
2. A ∩ B = {2}
3. A – B = {1}
4. A x B = {(1, 2), (1, 3), (2, 2), (2, 3)}
5. 2A = { φ {1 } , { 2 } , {1, 2 } }
 If A and B have n and m members respectively, then
A x B has nm members
2A has 2n members.
Relations :
 A binary relation is a set of pairs.
 The first component of each pair is chosen from a set called the domain and the
second component of each pair is chosen from a set called a range.
 If R is a relation and (a, b) is a pair in R then we write a R b.
Properties of Relations :
 We say a relation R on set S is
1. Reflexive
if aRa for all a in S
2. Irreflexive
if aRa is false for all a in S
3. Transitive
if aRb and bRc imply aRc
4. Symmetric
if aRb implies bRa
5. Asymmetic
if aRb implies that bRa is false.
 Any asymmetric relation must be irreflexive.
Equivalence relation :
 A relation R that is
i. Reflexive
ii. Symmetric
iii. Transitive
is said be an equivalence relation.
Closure of relations :
 The transitive closure of R, denoted Rt is defined by
1) If (a, b) is in R, then (a, b) is in R+
2) if (a, b) is in Rt and (b, c) is in R then (a, c) is in R+
 3) Nothing is in R+, unless it follows from (1) and (2)
 The reflexive and transitive closure of R denoted R+ is defined as
R+ U {( a, a ) | a is in s }
Example :
Let R = {(1, 2), (2, 2), (2, 3)} be a relation on the set {1, 2, 3}
R+ = {(1, 2), (2, 2) (2, 3), (1, 3)}
R* = {(1, 2), (2, 2), (2, 3), (1, 3), (1, 1) (3, 3)}
Graphs :
 A graph consist of a finite set of verticles V and a set of paris of vertices E
called edges.
 Graph is denoted as G = (V, E)
 A path in a graph is a sequence of verticle V 1, V2, V3, …., Vk k ≤ 1, such that
there is an edge (Vi, Vi+1) for each I |≤ i ≤ k
Directed Graphs:
 A directed graph or digraph consists of a finite set of vertices V and a set of
ordered pairs of vertices E called arcs.
 The arc from V → W is denoted as V →W
 If V → W is an arc, we say
V →Pr edecessor of W
W → Successor of V
Trees:
 A tree is a digraph with the following properties
1. Three is one vertex, called the root that has no predecessor and from
which there is a path to every vertex.
2. Each vertex other than the root has exactly one predecessor.
3. The successor of each vertex is ordered from the left.
 If there is a path from vertex V 1 to Vertex V2 then V2 is said to be descendant
of V1 and V1 is said to be an ancestor of V2.

INDUCTIVE PROOFS

Inductive Proofs :
 Theorems can be proved by mathematical induction
 Let P(n) be a statement about a non negative integer n
 The Principal of mathematical induction is that P(n) follows from
(a) P (o)
(b) P (n-1) imples P(n) for n ≥ 1
  Condition (a) is called the basis and condition (h) is called the inductive step.
Example 1 :
Prove by mathematical induction.
n (n + 1) (2n + 1)
02 + 12 + 22 + …. + n2 = 6
Solution
n (n + 1) (2n + 1)
Let P (n) = 12 + 22 + 32 + ….. n2 = 6
Basic Step
for n = 0
n
L.H.S. ∑ ¿¿i=0
i2 = 0
n (n + 1) (2n + 1)
=0
R.H.S. 6
Inductive step
for n = n – 1
n−1 (n) (n − 1) (2n 1 1) n n (n + 1) (2n + 1)
∑ ¿¿i=0 i2 = 6 implies ∑ ¿¿i=0 i2 = 6
Since
n n−1
∑ ¿¿i=0 i2 = ∑ ¿¿i=0 i2 + n2
n (n−1) (2n−1) 2
+n
= 6
2 2
(n −n ) (2 n−1) + 6 n
= 6
2 n3 − 2n 2 − n2 + n + 6 n 2
= 6
3 2
2n + 3n + n
= 6
n (2 n2 + 3n + 1)
= 6
n (n+1 ) (2n+1)
= 6
L.H.S = R.H.S.
∴ Thus by induction it is true for all n

Example 2 :
Prove by mathematical induction.
 n (n+1)
0 + 1 + 2 + …. + n = 2
Solution
n (n+1)
Let P (n) = 1 + 2+ 3 + n = 2
Basis Step
for n = 0
n
L.H.S. ∑ ¿¿i=0 i = 0
n n (n+1)
R.H.S. ∑ ¿¿i=0 i = 2
=0
Inductive step
for n = n – 1
n (n−1)n n n (n+1)
∑ ¿¿i=0 i = 2 implies ∑ ¿¿i=0 i = 2
Since
n n
∑ ¿¿i=0 i = ∑ ¿¿i=0 i + n
(n−1)n
+n
= 2
(n−1)n + 2n
= 2
2
n −n+2 n
= 2
n2 +1
= 2
n(n+1)
= 2
L.H.S. = R.H.S.
Thus by induction it is true for all n.
Example 3 :
x 2
Prove if x ≥ 4 then 2 ≥ x by mathematical inducations
Solution
Basic step :
4 2
If x = 4 then 2 ≥4
16 ≥ 16
 5 2
x = 5 then 2 ≥5
32 ≥ 25
Inductive step
putx = x + 1
x+1 2
∴2 ≥ ( x+1)
2 x .2 ≥ ( x+1)2
x 2 2
2 .2 ≥ 2x ≥ ( x1+)
2 2
2x ≥ x + 2x + 1
2
x ≥ 2x + 1
¿ by x
1
x≥2+
x
1 1
x ≥ 4, ≤ ,
Since x 4 where RHS = 2.25
2x 2 ≥ ( x + 1) for x ≥ 4

INTRODUCTION TO FORMAL PROOF

Introduction to formal Proof :

 Formal proof is a step by step to solve the problem.
 In format proof
We try to prove that statement B is true because statement A is true.
 The statement A is called hypothesis and B is called conclusion statement.
The four ways of Theorem Proving
(or)
Methods of formal proof.
(1) Deductive Proof
(2) Reduction Proof
(3) Other theorem forms
(4) Theorems that appear not to be if then statement.
Deductive Proof :
 A deductive proof consists of a sequence of statements whose truth leads us
from some initial statement called the hypothesis or the given statement (s) to a
conclusion statement.
 The theorem that is proved when we go from a hypothesis H to a conclusion C
is the statement.
“If H then C”
 We say that C is deducted from H
 The hypothesis may be true or false hypically depending on values of its
parameters.
Theorem 1
2
If x ≥ 4 then 2x ≥ x
Proof :
 The hypothesis H is x ≥ 4
 The hypothesis has a parameter x and thus is neither true of false.
 eg. H is true for x = 6 and false x = 2
2
 The conclusion C is 2x ≥ x
 This statement also uses parameter x and is true for certain values of x and not
others.
2
 The intuitive argument that tells the conclusion 2x ≥ x will be true whenever
x≥4
 The left side 2x doubles each time x increase by 1
2
x+1
 The right side x2 grows by the ration
( )
x
2 2
 Hence if x ≥ 4 then 2x ≥ x , for all integers x ie 2x ≥ x is deduced from x ≥ 4
Theorem 2 :
2
If x is the sum of squares of four positive integers, then 2x ≥ x
Statement Justification

1 x = a2 + b2 + c2 + d2 Given

2 a ≥ 1, b ≥ 1, c ≥ 1, d≥ 1 Given

3 2 2 2 2 (2) and properties of arithmetic

a ≥ 1, b ≥ 1, c ≥ 1, d ≥ 1
4 x≥4 (1) and (3) properties of
arithmetic

5 x 2 (5) and Theorem (1)

2 ≥x

Reduction to definitions
 If you are not sure how to start a proof convert all terms in the hypothesis to
their definitions.
Theorem :
Let S be a finite subset of some infinite set Let T be the complement of S with
respect to Then T is infinite.
Proof :
Original Statement New Statement

S is finite There is an integer n such |s| = n

U is infinite for no integer P is |U| = p

SUT = U and
T is the complement of S
S∩T = φ

 We use a common proof technique called “Proof by contradiction”

 In this proof, the contradiction of the conclusion is “T is finite”
 Let us assume T is finite,
|T| = m for some integer m
|S| = n
 Since SUT = U and S∩T = φ the elements of U are exactly the elements of S
and T
 Thus there must be n + m elements of U |U| = n + m
 The statement that U is finite contradicts the given statement that U is infinite
 Thus our assumption is contradiction
 So T is infinite
Other Theorem Forms :
 Ways of saying “if – Then”
 The other ways in which if H then C might appear.
1. H implies C
2. H only if C
3. C if H
4. whenever H holds, C follows.
If – And – only – If statements :
 The statement of the form
A if and only if B is actually two if – then statements.
(i) if A then B and
(ii) if B then A
Theorems that appear not to be if – then statements :
 Sometimes we find a theorem that appear not to have a hypothesis.
 An example is the well-known fact from the trigonometry.
 Theorem
2 2
Sin θ + Cos θ = 1
Additional Forms of Proof :
1. Proofs about sets.
 2. Proofs by contradiction.
3. Proofs by counter example.
Proving Equivalences about sets :
 If E and F are two sets, then the statement E=F means the two sets represented
are the same.
 Every element in the set epresented by E is in the set represented by F
 And every element in the set represented by F is in the set represented by E.
Example :
 The commutative law of union says that we can take the union of two sets R
and S in either order.
i.e., RUS = SUR
 The commutative law of union says E = F
 The proof of any statement that asserts the equality of two sets E = F, if follows
the form of any if – and – only – if – proof
1. Proof that if x is in E then x is in F
2. Proof that if x is in F then x is in E
Theorem :
R∪ (S∩T ) = ( R∪S ) ∩ ( R∪T )
Proof :
The two set of expressions involved are
E = R∪(S∩T )
R = ( R∩S ) ∩ ( R∪T )
Steps in the part R∪(S∩T ) ddd
Statement Justification

1 x is in R∪U (S∩T ) Given

2 x is in R or x is in S∩T (1) and definition of union

3 x is in R or x in in both S and T (2) and definition of intersection

4 x is in RUS (3) and definition of union

5 x is in RUT (4) and definition of union

(4), (5) and definition of

6 x is in ( R∪S ) ∩ ( R∪T )
intersection

Steps in the ‘only-if’ part.

Statement Justification
 1 x is in ( R∪S ) ∩ ( R∪T ) Given

2 x is in RUS (1) and definition of intersection

3 x is in RUT (1) and definition of intersection

4 x is in R or x is in both S and T (2) and (3) reasoning about union

5 x is in R or x is in S∩T (4) and definition intersection

6 x is in RU S∩T (5) and definition of union.

The Contrapositive :
 The contrapositive of the statement “if H then C” is “if not C then not H”
 A statement and its contrapositive are either both true or both false.
 To see “if H then C” and if not C then not H are logically equivalent.
There are four cases to consider
1. H and C both true
2. H true and C false
3. C true and H false
4. H and C both false
Proof by contradiction :
 Another way to prove a statement of the form.
“if H then C is to prove the statement.
 H and not C implies false hood.
 Start by assuming both the hypothesis H and the negation of the conclusion C
 Complete the proof by showing that something known to be false follows
logically from H and C
 This form of proof is called proof by contradiction.
Counter example :
 Statements that have no parameters, or that apply to only a finite number of
values of its parameter are called observations.
 It is easier to prove that a statement is not a theorem than to prove it is a
theorem.
Example
All primes are odd.
More formally, we might say
if integer x is a prime, then x is odd
Example
There is no pass of integers a and b such that
a mod b = b mod a
 BASIC DEFINITIONS DFA AND NFA

Finite state systems :

 The finite Automaton is a mathematical model of a system with discute inputs
and outputs.
 The system can be in a any one of a finite number of internal configuration or
states.
 The state of the system summarixes the information concerning past inputs that
is needed to determine the behavior of the system on subsequent inputs.
 The primary example of finite automaton is a switching circuit such as control
unit of a computer.
 A switching circuit is composed of a finite number of gates each of which can
be in one of two conditions usually 0 and 1
 The state of a switching network with n gates is thus any one of the 2 n
assignments of 0 or 1 to the various gates.
 Text editors and the lexical analyzers found in most compiters are designed as
finite state systems.
0 1 0 1 0 0 0

Finite Control
Basic Definitions :
Deterministic finite automata :
 A finite automator (FA) consists of a finite set of states and a set of transitions
from state to state that occur on an inpul symbol chosen from an alphabet 
 For each input symbol there is exactly one transition out of each state.
 One state denoted qo is the initial state in which the transition starts.
 Some states are designated as final states or accepting states.
 The Deterministic finite automata can be represented as a transition diagram or
transition table.
 The directed graph is used to represent the transition diagram.
 The vertices of the graph correspond to the states of FA
 If there is a transition from state q to state p on input a there is an are
labeled a from state q to state p
 The FA accepts a string x if the sequence of symbols of x leads start
state to final state.
Example :
  The initial state, qo is indicated by the arrow labeled start.
 The final state indicated by the double circle.
 The FA accepts all string of 0’s and 1’s in which both the number 0’s and the
number of 1’s are even.
 for eg.
The string accepted by the above FA, 11, 1100, 00, 0000, 1111, 110110
Formal Definition of DFA :
 We formally denote a finite automaton by a 5 tube.
M =  Q, , , q o , F
Q  is a finite set of states
  is a finite input alphabet
q o  in Q is the initial state
F  F  Q is the set of final states
  is the transition function mapping from Q x  to 

ie  (q, a ) is a state for each state q and input symbol a

 FA is denoted as a finite control

0 1 0 1 0 0 0

Finite Control
 Finite control which is in same state from Q reads a sequence of symbols from
 written on a tape.

 In one move, the FA in state q, scanning a symbol a enters state  (q, a ) and
moves its head one symbol to the right.


 We define a function  from

Q x  * to Q


  (q, w ) is the unique state p such that there is a path in the transition diagram
from q to p labeled w
  Formally we define


(1) 
(q, t )  q
(2) for all string w and input symbols a
 

 (q, wa)   ( (q, w ), a )

 A string x is said to be accepted by FA
M = (Q, , , q o , F) if
 (q o , x )  p, for some P in F
 The language accepted by FA, denoted as L(M)
L (M) =  x |  (q o , x ) is in F
 The language is a regular set if it is the set accepted by the same FA
Example :
Consider the transition diagram

 This FA is denoted as
M = (Q, , , q o , F) where
Q =  q 0 , q1 , q 2 , q 3 
   0,1
q0 = q0
F = q 0 
 is given as a transition table
s 0 1
q0 q2 q1
q1 q2 q1
q1 q3 q0
q2 q0 q3
q3 q1 q2

 To find the string accepted by DFA, suppose w = 110101 is input to M we have

to find  (q 0 ,110101)
 (q 0 ,1)  9,

 (q 0 ,110 )   ( (q,1),1)
  (q1 ,1)
 q0
 
 (q0 ,110 )   ( (q 0 ,11), 0)
  ( q 0 , 0)
 q2
 
 (q0 ,1101)   ( (q 0 ,110 ),1)
  (q2 ,1)
 q3
 
 (q0 ,11010 )   ( (q 0 ,1101), 0)
  ( q 3 , 0)
 q1
 
 (q 0 ,110101)   ( (q 0 ,11010 ),1)
  (q1 ,1)
 q 0 F
 Thus 110101 is accepted by the FA Thus 110101 is in L(M)
 L(M) = is the set of string with an even number of o’s and an even number of
1’s

Non – Deterministic finite Automata :

 A finite automata model to allow zero, one or more transitions from a
state on the same input sympol. This new model is called a non
deterministic finite Automata (NFA)
 Any set accepted by NFA can also be accepted by DFA.
 Example
  The input sequence a1, a2, a3 …. an is accepted by NFA, if the
transition leads from the initial state of final state.
Formal Definition of NFA :
 Formally we denote a NFA by a 5 – tuple
M = (Q, , , q 0 , F)
where
Q  set of states
  is a finite input alphabet
q o  in Q is the initial state
F  F  Q is the set of final states
  is the transition function mapping from Q x  to 
Q x   2Q

 The function  can be extended to a function  mapping from
Q x  * to 2 Q and


(i)  (q,)  {q}


 
 (q, wa )     (q, w ), a 
(ii)  
Example :
Consider the NFA

Let the input w = 01001

Solution :
Q   q 0 , q1 , q 2 , q 3 , q 4 
   0,1
q0 = q0
 F = {q2, q4}
:
0 1
q0 {q0, q0,} {q0, q1,}
q1  {q2}
q2 {q2} {q2}
q3 {q4} 
q4 {q4} {q4}

 (q 0,01001)  q
 (q 0 , 0)  {q, q 3 )
 (q 0 , 01)   ( (q 0 , 0),1)

=  ( {q 0 , q 3 },1)
=  (q 0 ,1)  (q 3 ,1)
= {q0,q1) 
= {q0, q1}
 (q 0 , 010)   ( (q 0 , 01), 0)

=  ( {q 0 , q1 }, 0)
=  (q 0 , 0)  (q1 , 0)
= {q0,q3) 
= {q0, q3}

 (q 0 , 0100)   ( (q 0 , 010),1)

=  ( {q 0 , q 3 }, 0)
=  (q 0 ,1)  (q 3 , 0)
= {q0,q3)  {q4}
= {q0, q3, q4}

 (q 0 , 01001)   ( (q 0 , 0100),1)

=  ( {q 0 , q 3 , q 4 },1)
=  (q 0 ,1)  (q 3 ,1)  (q 4 ,1)
= {q0,q1)   {q4}
= {q0, q1, q4}
 (q 0 , 01001) contains a state in F so the input string 01001 is accepted by the NFA.

EQUIVALENCE DFA AND NFA

The Equivalence of DFA’s and NFA’s
 Since every DFA is an NFA it is clear that the class of languages accepted by
NFA’s includes the regular sets.
 for every NFA we can construct an equivalent DFA.
Theorem :
Let L be a set accepted by NFA, then there exists a DFA that accepts L.
Proof :
Let M = (Q , ∑ , δ , q0 , F ) be an NFA which accepts L.
Define a DFA.
1
M 1 = ( Q1 , ∑ , δ 1 , q 1 , F1 )
0

 The states of M1 are all the subsets of the set of states of M

i.e) Q1 = 2Q
 F1 is the set of all states in Q1containing a final state of M.
 An element of Q1will be denoted by [q1, q2, ……….q1) are in Q.
 2is a single state of the DFA corresponding to the set of states of the NFA
 q01 = [q0]
1
 δ ( [q1], a) = [p1]
iff δ (q1, a) = {p1}
δ1 ([q1, q2, … qi], a) = [p1, p2, …. pj]
iff δ1 ([q1, q2, … qi], a) = [p1, p2, …. pj]
 It is easy to show by induction on the length of the input string x that
δ 1 (q 1 , x )
0 = [q1, q2, …qj]
iff
1
δ (q 0 , x) = [q , q , …q ]
1 2 j

Basis :
The result is trivial for 1 x 1 = 0, since q01 = [q0] and x must be ∈
1
δ ( [q 0 ], ∈ = [ q 0 ]
iff
δ ( q0 ∈) = q 0
Induction :
 Suppose that the hypothesis is true for inputs of length m or less
 Let xa be a string of length m + 1 with a in ∑ ¿¿ then
δ 1 (q 0 1 , xa) = δ 1 (δ 1 ( q 1 , x ), a)
0

By the inductive hypothesis

δ 1 (q 1 , x) = [ p1 , p 2 , . . . p j ]
0

iff
δ (q0 , x) = [ p1 , p 2 , ... p j ]
 δ 1 (q 0 , xa) = δ 1 ( δ 1 (q 0 1 , x), a)
1
= δ [ p 1 , p 2 , .. .. . p j ], a )
= {r 1 , r 2 , ... r k }
iff
1
δ (q 0 , xa) = δ (δ (q 0 , x), a)
= δ 1 [ p 1 , p 2 , .. .. . p j ], a )
= {r 1 , r 2 , ... r k }
Thus
iff
δ 1 (q 1 , xa) = [ r 1 , r 2 , .. . r k ]
0

iff
δ (q0 , xa) = [ r 1 , r 2 , ... r k ]
which establishes the inductive hypothesis
1 1
 δ (q 0 , x) is in F1 exactly when δ (q0 , x) contains a state in F
L (M) = L (M)

PROBLEM ON NFA TO DFA

Example 1:
1. Let M = ( {q 0 , q1 } 0 , 1 , δ , q 0 , {q 1 } be an )
{ }

NFA where δ (q0 , 0) = { q0 , q1 ) }

δ (q0 , 1) = {q 1 }
δ (q0 , 0) = φ
δ (q0 , 1) = {q 0 , q 1 ) }
Solution :
We can construct a DFA
1
M1 = (Q1, {0, 1}, δ , [q0], F)
Q1 = all subsets of {q0, q1)
Q1 = {[q 0 ], [ q 1 ], [ q 0 ,q 1 ], φ }
F1 = Set of states of Q1 containing state in F
F1 = { [q1], [q0, q1]}
1
Transition Table : δ
0 1

[q0] [q0, q1,] [q1]

 [q1]  [q0, q1]

[q0, q1] ? ?
  

1
To find δ ( [q 0 , q 1 ], 0
δ ( {q 0 , q 1 } , 0 )
= δ (q 0 , 0) ∪ δ (q 1 , 0)
= {q 0 , q 1 }∪ φ
= {q0, q1}
δ 1 ( [ q 0 , q 1 ], 0) = [q 0 , q1 ]

1
To find δ ( [q 0 , q 1 ], 1
δ ( {q 0 , q 1 } , 1 )
= δ (q 0 , 1) ∪ δ (q1 , 1)
= {q 1 } ∪ {q 0 , q 1 }
= {q0, q1}
1
δ ( [q 0 , q 1 ], 1) = [q 0 , q1 ]
1 1 1 1
∴ M1 = (Q1, ∑ , δ , q 0 , F )
Q1 = { [q0], [q1], [q0, q1], φ }
∑ = {0, 1}
q01 = [q0]
F1 = { [q1], [q0, q1] }
δ1
0 1

[q0] [q0, q1,] [q1]

[q1]  [q0, q1]

[q0, q1] [q0, q1] [q0, q1]

  

Transition Diagram
 Examples 2 :
Consider the following NFA
a b

q0 {q0, {q2}
q1}

q1 {q1} {q0}

[q2] {q0} {q1, q2}

Construct an equivalent DFA
Solution :
We construct DFA M1
11 1 1
M1 = (Q1, ∑ , δ , q 0 , F )
Q1 = { [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2], φ }
∑ = {a, b}
q01 = [q0]
F1 = { [q2], [q0, q1], [q1, q2], [q0, q1, q2] }
δ1
a b

[q0] [q0, [q2]

q1]

[q1] [q1] [q0]

[q2] [q0] [q1, q2]

[q0, q1] ? ?
 [q0, q2] ? ?

[q1, q2] ? ?

[q0, q1, q2 ] ? ?

1
To find δ ( [q 0 , q 1 ], a
δ ( {q 0 , q 1 } , a )
= δ (q 0 , a) ∪ δ ( q1 , a)
= {q 0 , q 1 }∪ { q 1 }
= {q0, q1}
1
δ ( [q 0 , q 1 ], a) = [q 0 , q1 ]
1
To find δ ( [q 0 , q 1 ], b
δ ( {q 0 , q 1 } , b )
= δ (q 0 , b) ∪ δ ( q1 , b)
= {q 2 }∪ { q 0 }
= {q0, q2}
1
δ ( [q 0 , q 1 ], b) = [q 0 , q2 ]
1
To find δ ( [q 0 , q 2 ], a
δ ( {q 0 , q 2 } , a )
= δ (q 0 , a) ∪ δ ( q2 , a)
= {q 0 , q 1 }∪ { q 0 }
= {q0, q1}
1
δ ( [q 0 , q 2 ], a) = [q 0 , q1 ]
1
To find δ ( [q 0 , q 2 ], b
δ ( {q 0 , q 2 } , b )
= δ (q 0 , b) ∪ δ ( q2 , b)
= {q 2 }∪ { q 1 , q 2 }
= {q0, q1}
= [q 1 , q 2 ]
1
δ ( [q 0 , q 2 ], b) = [q 1 , q 2 ]
1
To find δ ( [q 1 , q 2 ], a
δ ( {q 1 , q 2 } , a )
= δ (q 1 , a) ∪ δ (q 2 , a)
= {q 1 }∪ { q 0 }
= {q0, q1}
1
δ ( [q 1 , q 2 ], a) = [q 0 , q1 ]
1
To find δ ( [q 1 , q 2 ], b
 δ ( {q 1 , q 2 } , b )
= δ (q 1 , b) ∪ δ (q 2 , b)
= {q 0 }∪ { q 1 , q 2 }
= {q0, q1, q2}
1
δ ( [q 1 , q 2 ], b ) = [q 0 , q 1 , q 2 ]
1
To find δ ( [q 0 , q 1 , q 2 ], a
= δ (q 0 , a) ∪ δ ( q1 , a) ∪ δ ( q2 , a)
δ ( {q 0 , q 1 , q 2 } , a )

= {q 0 , q 1 }∪ { q 1 }∪ {q 0 }
= {q0, q1,}
1
δ ( [q 0 , q 1 , q 2 ], a) = [q 0 , q 1 , ]

1
To find δ ( [q 0 , q 1 , q 2 ], b
)
= δ (q 0 , b) ∪ δ ( q1 , b) ∪ δ ( q2 , b)
δ ( {q 0 , q 1 , q 2 } , b )

= { q 2 }∪ {q 0 }∪{q 1 , q 2 }
= {q0, q1, q2}
1
δ ( [q 0 , q 1 , q 2 ], b) = [q 0 , q 1 , q 2 ]

a b

q0 [q0, q1] [q2]

q1 [q1] [q0]

[q2] [q0] [q1, q2]

[q0, q1] [q0, q1] [q0, q2]

[q0, q2] [q0, q1] [q1, q2]

[q1, q2] [q0, q1] [q0, q1, q2]

[q0, q1, q2 ] [q0, q1] [q0, q1, q2]

 FINITE AUTOMATA WITH ∈ -MOVES

Finite Automata with ∈ Moves :

 The NFA may be extended to include transitions on the empty input ∈

 For eg.

 We say an NFA accepts a string w if there is some labeled w from the initial
state to a final state of course edges labeled ∈ may be included in the path
although the ∈' s do not appear explicitly in w.
 For eg. the word 002 is accepted by the NFA by the path q 0 – q0 – q0 – q1 – q2 –
q2 with arcs labeled 0, 0, ∈, ∈, 2
Formal definition :
 A NFA with ∈ − moves to be a 5 – tuple,
M = (Q , ∑ , δ , q 0 , F)
δ is the transition function maps
Q
Q x (∑ ∪ { ∈ } to 2
 δ (q, a) will consist of all states P such that there is a transition labeled a from
q to p where a is either ∈ or a symbol in ∑ ¿¿
0 1 2 ∈
 q0 {q0 φ φ {q1
} }

q1  {q1  {q2
} }

[q2]   {q2 
}

∈ - closue (q)
∈ -closue (q) is the set of all vertices p such that there is a path from q to p

labeled
Example :
∈ - closure (q0) = {q0, q1, q2}

 ie) the path consisting of q0 alone is a from q0 to q0 with all arcs labeled ∈.
 Path q0 – q1, shows that q1 is in ∈ − closure. (q0)
 Path q0 – q1 – q2 shows that q2is in ∑ ¿¿ -closure.
¿
 δ can be defined as follows :
¿

1. δ (q, ∈) = ∈− closure ( q)
2. for w in ∑ ¿ and a in ∑ ¿¿
¿
δ (q, wa) = ∈ - closure (p)
Where p = { p| }
¿

For some p in δ (δ (q, w)

3. δ (R , a) = ∪ δ (q, a)
q in R
¿ ¿

4. δ (R , W ) =∪ δ (q,w)
q in R
 We can define L (M) as
The language accepted by M ( Q , ∑ , δ , q 0 , F) to be
¿
{w| q δ (q,w) contains a state in F}
 Example :
Consider the NFA
 ¿

Find δ (q0, q1)

¿ ¿
δ (q0, 01) = ∈ − closure (δ ( δ (q 0 , 0), 1)
¿ ¿
δ (q0, 0) = ∈ − closure (δ ( δ (q 0 , ∈), 0)
¿
δ (q0, ∈ 01) = ∈ − closure (q 0 )
= {q0, q1, q2}
¿ ¿
δ (q0, 01) = ∈ − closure (δ ( δ (q 0 , ∈), 0)
= ∈ − closure ( δ ( ¿ ¿
= ∈ − closure (δ ( q 0 , 0) ∪ δ (q, 0) ∪δ ( q2, 0))
= ∈ − closure (δ {q 0 }∪ φ ∪ φ)
= {q0, q1, q2}
¿ ¿
δ (q0, 01) = ∈ − closure (δ ( δ (q 0 , 0), 1)
= ∈ − closure ( δ ( ¿ ¿
= ∈ − closure (δ ( q 0 , 1) ∪ δ (q 1 , 1) ∪δ (q 2 , 1))
= ∈ − closure (φ ∪ {q 1 }∪ φ)
= ∈ − closure {q 1 }
= {q1, q2}

EQUIVALENCE OF NFA’s WITH AND WITHOUT ∈ -MOVES

 Prove that “A language accepted by some NFA with ∈ - moves iff L is

accepted by without ∈ - moves NFA
Theorem :
If L is accepted by an NFA with ∈ -transitions then L is accepted by an NFA
without ∈ - transition.
Proof :
Let M = (Q, ∑ , δ , q 0 , F) be an NFA with ∈ - transitions.
Now we have to define NFA without ∈ - move M’
1 1 0 1
M1 = (Q1, ∑ , δ , q , F )
Where F1 = FU{q0} if ∈ - closure (q0) contains a state of F
=F Otherwise
 It is easy show by induction on the length of the input string .We have to prove
¿
δ 1 (q 0 , x) = δ (q 0 , x)
 This statement may not be true for x = ∈
1
δ (q0, ∈) = {q 0 }
while δ (q 0 , ∈) = ∈−closure (q 0 )
 Therefore we begin our induction at 1
Basis :
|x|=1
Then x is a symbol a
δ 1 (q 0 , a) = δ (q 0 , a) by the definition of δ 1
Induction :
| x | >1 Let x = wa
δ 1 (q 0,wa) = δ 1 (δ (q0, w), a)
δ 1 ( p, a)
=
¿ δ 1 (q , a)
=
q in p
¿ δ (q, a)
=
q in p
δ ( p , a)
=
¿ ¿
δ (δ (q 0 ,w ), a = δ ( q 0 , wa)
=

CONVERSION OF NFA WITH ∈ -MOVES TO NFA WITHOUT ∈ -

MOVES

 CONVERT THE NFA WITH ∈ -MOVES TO NFA WITHOUT ∈ -

MOVES
∈
Consider the NFA with - moves
Find an equivalent NFA without ∈ - moves
Solution :
Given NFA with ∈ - moves
M = ({q0, q1, q2}, {0, 1, 2, ∈ }, δ , q0, {q2})
Now we have to define NFA without ∈ - move
M1 = (Q1, ∑ , δ 1, q 0, F 1)
Q = {q0, q1, q3}
∑ = {0, 1, 2}
1
F = {q0, q2} ∈ - closure (q0) = {q0, q1, q2} contains a state of F.
δ1
0 1 2

q0 {q0, q1, q2} {q0, {q2

q1} }

q1  {q1, q2} {q2

q2   {q2
}
∈ − closure( q1 )= {q 1 , q 2 }
∈ − closure( q2 )= {q 2 }
δ (q0, ∈) = ∈ − closure( q0 )
= {q0, q1, q2}
1
δ (q0, 0) = ∈ − closure (δ ( q0 , 0))
= ∈ − closure (δ ( δ (q 0 , ∈), 0)
= ∈ − closure (δ ({q 0 , q 1 , q 2 }, 0)
= ∈ − closure (δ ( q 0 , 0) ∪δ (q 1 , 0) ∪δ (q 2 , 0))
= ∈ − closure (δ ({q 0 } ∪φ∪φ)
= {q0, q1, q2}

1
δ (q 0 , 1) = ∈ − closure (δ ( q0 , 1))
= ∈ − closure (δ ( δ (q 0 , ∈), 1)
= ∈ − closure (δ ({q 0 , q 1 , q 2 }, 1)
= ∈ − closure (δ ( q 0 , 1) ∪δ ( q 1 , 1) ∪δ (q 2 , 1))
 = ∈ − closure (φ∪ ({q 1 }∪φ)
= {q1, q2}
1
δ (q 0 , 2) = ∈ − closure (δ ( q0 , 2))
= ∈ − closure (δ ( δ (q 0 , ∈), 2)
= ∈ − closure (δ ({q 0 , q 1 , q 2 }, 2)
= ∈ − closure (δ ( q 0 , 2) ∪δ (q 1 , 2) ∪δ (q 2 , 2))
= ∈ − closure (φ∪φ∪ {q 2 }
= {q2}
1
δ (q 1 , 0) = ∈ − closure (δ ( q1 , 0))
= ∈ − closure (δ ( δ (q 1 , ∈), 0)
= ∈ − closure (δ ({ q 1 , q 2 }, 0)
= ∈ − closure (δ ( q 1 , 0) ∪δ (q 2 , 0))
= ∈ − closure (φ∪φ)
= φ
1
δ (q 1 , 0) = ∈ − closure (δ ( q1 , 0))
= ∈ − closure (δ ( δ (q 1 , ∈), 1)
= ∈ − closure (δ ({ q 1 , q 2 }, 1)
= ∈ − closure (δ ( q 1 , 1) ∪δ (q 2 , 1) ))
= ∈ − closure ({q 1 }∪φ)
= {q1, q2}
1
δ (q 1 , 2) = ∈ − closure (δ ( q1 , 2))
= ∈ − closure (δ ( δ (q 1 , ∈), 2)
= ∈ − closure (δ ({ q 1 , q 2 }, 2)
= ∈ − closure (δ ( q 1 , 2) ∪δ (q 2 , 2) )
= ∈ − closure (φ∪ {q 2 } )
= {q2}
1
δ (q 2 , 0) = ∈ − closure (δ ( q2 , ∈), 0)
= ∈ − closure (δ (¿¿
= ∈ − closure (φ)
= φ
δ 1 (q 2 , 1) = ∈ − closure (δ ( q2 , ∈), 1)
 = ∈ − closure (δ (¿ ¿
= ∈ − closure (φ)
= φ
1
δ (q 2 , 2) = ∈ − closure (δ ( q2 , ∈), 2)
= ∈ − closure (δ (¿¿
= ∈ − closure (q 2 )
= φ

Example 2 :
Construct a NFA without ∈ - moves from NFA with ∈ - moves

Solution :
∈ − closure (q0) = {q0, q1}
∈ − closure (q1) = {q1}
Let Given NFA with ∈ − moves

M = (Q , ∑ , δ , q 0 , F)
We have to find M’, NFA without ∈ − move
1 1
M = (Q , ∑ , δ , q 0 , F )
F1 = {q0, q1} ∈−closure (q 0) contains a state in F

F1 = F∪ {q 0 }
1
δ (q 0 , ∈) = ∈−closure (q0 )
= {q0, q1}
1 1 1
δ (q 0 , 0) = ∈ − closure (δ (δ (q 0 , ∈), 0)
1
= ∈ − closure ( δ ( ¿ ¿
 = ∈ − closure ( δ ( ¿ ¿
= ∈ − closure ( ¿ ¿
= {q0, q1}
1 1 1
δ (q 0 , 1) = ∈ − closure (δ (δ (q 0 , ∈), 1)
1
= ∈ − closure ( δ ( ¿ ¿
= ∈ − closure ( δ ( ¿ ¿
= ∈ − closure (φ∪¿¿
= {q1}
1 1 1
δ (q 1 , 0) = ∈ − closure (δ (δ (q 1 , ∈), 0)
1
= ∈ − closure (δ (¿ ¿
= ∈ − closure (φ)
= φ
δ 1 (q 1 , 1) = ∈ − closure (δ1 (δ1 (q 1 , ∈), 1)
1
= ∈ − closure (δ (¿ ¿
= ∈ − closure (q 1 )
= {q1}
0 1

q0 {q0, q1} {q1

q1  {q1
}

EQUIVALENCE OF FINITE AUTOMATA AND REGULAR EXPRESSIONS

Equivalence of finite automata and regular expressions :

 The languages accepted by finite automata are the languages denoted by
regular expressions.
 For every regular expression there is an equivalent NFA with ∈ - transitions.
Theorem 1:
 Let r be a regular expression. Then there exists an NFA with ∈ - transitions
that accepts L (r)
Proof :
We show by induction on the number of operator in the regular expression r
that
there exists an NFA with ∈ - transitions having one final state and no
transitions out of this final state such that
L (M) = L (r)
Basis :
For regular expressions having zero operators.
 The expression r must be ∈, φ , or a for some a in ∑ ¿ ¿

Induction :
One or more operators in the regular expressions.
 Assure that the theorem is true for regular expression with fewer that I
operators.
i≥1
 Let r have I operators.
Case 1 :
r = r1 + r2
 Both r1 and r2 must have fewer than i operator
 Thus there are 2 NFA’s
M1 = (Q 1 , ∑ 1 , δ 1 , q 1 , {f 1 } with
= L (M1) = L (r1)
 Assume Q1 and Q2 are disjoint
Let q0 → be a new initial state
f0 → be a new initial state
 Now we can construct NFA with
M = Q1 , ∪ Q 2 ∪ {q 0 , f 0}, ∑ , ∪∑ 2 , δ , q 0 , {f 0 })
where δ is defined by
(i) δ (q 0 , ∈) = {q 1 , q 2 }
(ii) δ (q, a) = δ 1 (q , a) for q in Q 1 − {f 1 } and a in ∑ 1 ∪ {∈}
(iii) δ (q, a) = δ 2 (q , a) for q in Q 2 − {f 2 } and a in ∑ 2 ∪ {∈}

(iv) δ 1 ( f 1 , ∈) = δ 2 (f 2 , ∈) = {f 0 }
  Hence
L (M) = L (M1) U L (M2)
Any path in the transition diagram of M from q 0 to f0 must begin by going to
either q1 or q2on ∈ . If the path goes to q1 it may follow any path in M1 to f1 and then
go to f0 on ∈
Hence L (M) = L (M1) U L (M2)
Case 2 :
r = r1 r2
Let M1 and M2 be 2 NFA’s
M = Q 1 , ∑ 1 , δ 1 , q 1 , {f 1 }) with
1

L (M1) = L (r1)
and
M2 = Q 2 , ∑ 2 , δ 2 , q 2 , {f 2 }) with
L (M2) = L (r2)
 Assume Q1 and Q2 are disjoint
 No we can construct NFA with
L (M) = L (r)
M = (Q , ∪Q 2 , ∑ , ∪∑ 2 , δ , {q 1 }, {f 2 })
where
δ is defined as

(i) δ (q, a) = δ 1 (q 1 , a) for q in Q 1 − {f 1 } and a in ∑ 1∪ {∈}

(ii) δ (q , a) = δ ( q 1 , a) for q in Q 2 − {f 1 } and a in ∑ 2 ∪ {∈}
(iii) δ (f 1 , ∈) = {q 2 }
 Every path in M from q1 to f2 is a path labeled by some string x form q1 to f1
followed by the edge from f1 to q 2 labeled ∈ followed by a path labeled by
some string y form q2 to f2.
M
M1 M2

 Thus
 L (M) = L (M1) L (M2)
ie. L (M) = {xy| x is in L ( M 1 ) and y is in L ( M 2 )}
Case (iii)
r = r1*
Let M1 = (Q 1 , ∑ 1 , δ 1 , q 1 , {f 1 }) with
L (M1) = L (r1)
Now we can construct NFA
Let M1 = (Q 1 {q 0 , f 0 }, ∑ 1 , δ 1 , q 0 , {f 0 }) with
L (M) = L (r)
where
q0 → be an new initial state
f0 → be an new final state
and δ is given by
(i) δ (q0 , ∈) = δ ( f 1 , ∈) = {q 1 , f 0 }
δ (q , a ) = δ (q , a) for q in Q − {f } and a in
∑1 ¿ {∈}
(ii) 1 1 1

 Any path from q0 to f0 consists either of a path from q 0 to q1 on ∈ followed

by some number of paths from q to f and back to q on ∈ 1 each labeled by a
1 1 1

string in L (M1) followed by a path from q1 to f1 on a string in L (M 1) then to f0

on ∈
Hence :
L (M) = L (M1)

Theorem 2
If L is accepted by DFA, then L is denoted by the regular expression.
Proof :
Let L be the set accepted by accepted by the DFA
M = ({q 1 , ........, q n }, ∑ , δ , q 1 , F)
Let
k
R ij → denote the set of all string x such that δ (q i , x ) = q j and δ (q i , y) = q for any
l

that is a prefix of x, then l = k

 k

i.e.) Rij = is the set of all strings that take the FA from state qi to qj without going
though any state numberd higher than k.
k

 we can define ij R
= is the set of all strings that take the FA from state q i to qj
without going through any state numbered higher than k.
k

 We can define R ij recursively.

k k −1 k−1 k −1 k −1
R = R (R ij ik kk )∗ R kj ∪ R ij

 The inputs of R ij are, either

k −1

1) in R ij

(or)
k −1 k −1

2) Composed of a string R ik followed by zero of more strings in R kk

k −1

followed by a string R kj
k

 We must show that for each i, j and k, there exists a regular expression r ij

denoting the language ij R

 We can show by induction on k.
Basis :
k=0
0
R ij is a finite set of strings, each of which is either ∈ or a single symbol.
Induction :
k

 The recursive formula R ij involves only the regular expression operators

a) union
b) concatenation
c) closure
k
 By the induction hypothesis, for r ij , we may select the regular expression
k k−1 k−1 k−1 k−1
r ij , = r ij (r kk )∗ r kj + r ij
 We can conclude
¿ Rnij
L (M) = q j in F
Thus L (M) is denoted by the regular expn.
n n n
rij1 + rij2 + ........... + r ijp where F = {q ji , q j 2 , ..... q jp }
 CONVERSION OF REGULAR EXPRESSION TO FINITE AUTOMATA

Construct an NFA for the regular express on 01* + 1 (or) (0 (1*)) + 1

Solution :
Given regular expression
r = 01* + 1
It is of the form r = r1 + r2 where
r1 = 01*
r2 = 1
The NFA for r2 = 1

Now r1 is of the form

r1 = r3 r4
where r3 = 0
r4 = 1*
The NFA for r3 = 0

r4 = r5*
r5 = 1
The NFA for r5 = 1

The NFA for r4 = r5* = 1*

The NFA for r1 – r3r4 = 01*

The NFA for r = r1 + r2

CONVERSION OF FINITE AUTOMATA TO REGULAR EXPRESSION

Convent the following DFA to a regular expression

Solution :
k
Find Rij for i, j, k
Let k = 0

Ro
ij = ¿ ¿¿
¿
r 011 = ∈ + 1
r 012 = 0
r 021 = φ
r 022 = ∈ + 0 + 1
k k−1 k−1 k−1 k−1
Rij , = Rik ( Rkk )∗ Rkj ∪ Rij
r kij = r k−1 k−1 k−1 k−1
ik (r kk )∗ r kj + r ij
For K = 1
0 0 0 0
R(1)
11 = r 11 (r 11 )∗ r 11 + r 11
 = (∈ + 1) (∈ + 1)∗ (∈ + 1) + (∈ + 1)
= 1* + (∈ + 1)
= 1*

0 0 0 0
r (1)
12 = r 11 (r 11 )∗ r 12 + r 12

= (∈ + 1) (∈ + 1)∗0 + 0
= 1* + 0
= 1*0
0 0 0 0
r (1)
21 = r 21 (r 11 )∗ r 11 + r 21

= φ (∈ + 1)∗ (∈ + 1) + φ
= φ1∗ + φ
= φ
0 0 0 0
r (1)
22 = r 21 (r 11 )∗ r 12 + r 22

= φ (∈ + 1)∗ (0) + ∈ + 0 + 1
= φ1∗+ 0 + ∈ + 0 + 1
= φ+ ∈+ 0+1
= ∈+0+ 1
Let K = 2
r (211 ) = r 112 (r 122 )∗ r 121 + r 111
= 1∗0 (∈ + 0 + 1)∗ φ + 1∗¿ ¿
= φ + 1∗
= 1∗¿ ¿
r (212) = r 112 (r 122 )∗ r 122 + r 112
= 1∗0 (∈ + 0 + 1)∗(∈ + 0 + 1) + 1∗¿ ¿
= 1∗0 (0+1)∗+ 1∗0
= 1∗0 (0+1)∗¿ ¿
r (221) = r 122 (r 122 )∗ r 121 + r 121
= (∈ + 0 + 1) (∈ + 0 + 1)∗ φ + φ
= (0+1)∗ φ + φ
= φ
r (222) = r 122 (r 122 )∗ r 122 + r 122
= (∈ + 0 + 1) (∈ + 0 + 1)∗ (∈ + 0 + 1) + (∈ + 0 + 1)
= (0+1)∗ + (∈+0+1)
= (0+1)∗¿ ¿
 (2 )
L (M) = r 12
= 1* 0 (0 + 1)*
L (M) = 1* 0 (0 + 1)*

MINIMIZATION OF DFA

Minimization of DFA :
 There is unique minimum state DFA for every regular set.
Theorem :
 The minimum state automata accepting a language L is unique upto an
isomorphism ie) renaming of the states.
Proof :
Any DFA M = (Q , ∑ , δ , q 0 , F) accepting L defines an equivalence relation that
is a refinement of RL
 Thus the number of states of M is greater than or equal to the number of states
of M1
 If equality holds then each of the states of M can be identified with one of the
states of M1
 Let q be a state of M there must be some x in ∑ ¿ such that
δ (q 0 , x) = q , otherwise q would be removed from Q
1 1 1
 Identify q with the state δ (q 0 , x) of M
 The identification will be consistent.
 If δ (q 0 , x) = δ (q 0 , y) = q , then x and y are in the same equivalence class of RL.
0 δ 1 (q 1 , x ) = δ 1 (q , y )
1
Thus 0

A Minimization Algorithm :
 There is a simple method for finding the minimum state DFA M 1, equivalent a
given DFA M = ( Q , ∑ , δ , q0 , F )
 Let ¿ be the equivalence relation on the states of M.
 If P ≡ q, we say p is equivalent to q.
P ≡ q iff for each input string x
δ ( p , x ) is an accepting state.
δ (q, x) is an accepting state.
 We say that p is distinguishable from q if there exists on x such that
δ ( p , x ) is an F and
δ (q, x) is not in F and vice versa.
Procedure :
  An X is placed in the table each time a of states that cannot be equivalent.
 Initially an X is placed in each entry corresponding to one find state and one
non – final state.
 Next for each pair of states P and q that are not distinguishable, we consider.
r = δ ( p , a)
s = δ (q, a) for each input symbol a
 If states r and s have been shown to be distinguishable by some string x, then p
and q are distinguishable by string ax.
 Thus if the string (r,s) in the table has an x, an x is placed at the entry (p, q)
Example :
Minimize the following DFA

Solution :
b x
c x x
d x x x
e x x x
f x x x x
g x x x x x x
h x x x x x x
a b c d e f g
 Intially an x placed in each entry corresponding to one final state and one final
state.
The entries
(c, a), (c, b), (c, d), (c, e), (c, f), (c, g), (c, h)
  Now the unmarked pairs are
(a, b) (b, d) (d, e) (l, f) (f, g) (g, h)
(a, d) (b, e) (d, f) (e, g) (f, h)
(a, e) (b, f) (d, g) (e, b)
(a, f) (b, g) (d, b)
(a, h)
(a, b)
δ (a, 0) = b
δ (b, 0) = g (b, g) is unmarked
δ (a, 1) = f
δ (b, 1) = c (f, c) is marked, so mark (a, b)

(a, b)
δ (a, 0)= b
δ (d , 0) = c (b, c) is marked so mark (a, d)

(a, l)
δ (a, 0) = b
δ (l, 0) = h (b, g) is unmarked
δ (a, 1) = f
δ (l, 1)= f (f, f) is unmarked

(a, f)
δ (a, 0) = b
δ (f , 0) = c (b, c) is marked so mark (a, f)

(a, g)
δ (a, 0) = b
δ (g , 0) = g (b, g) is unmarked
δ (a, 1) = f
δ (g , 1)= e (f, e) is unmarked

(a, h)
δ (a, 0)= b
δ (h, 0) = g (b, g) is unmarked
 δ (a, 1) = f
δ (h, 1) = c (f, c) is marked. So mark (a, h)

(b, d)
δ (b, 0) = g
δ (d , 0) = c (g, c) is marked. so mark (b, d)

(b, e)
δ (b, 0) = g
δ (e, 0)= h (g, h) is unmarked
δ (b, 1) = c
δ (e, 1)= f (c, f) is marked. So mark (b, e)
(b, f)
δ (b, 0) = g
δ (f , 0)= c (g, c) is marked. So mark (b, f)

(b, g)
δ (b, 0) = g
δ (g , 0) = g (g, g) is unmarked
δ (b, 1) = c
δ (g , 1)= e (e, e) is marked. So place an x in (b, g)

(b, h)
δ (b, 0) = g
δ (h, 0) = g (g, g) is unmarked
δ (b, 1) = c
δ (h, 1)= c (c, c) is unmarked.

(d, e)
δ (d , 0) = c
δ (e, 0) = h (c, h) is unmarked. So place x in (d, e)

(d, f)
δ (d , 0) = c
δ (f , 0) = c (c, c) is unmarked
δ (d , 1)= g
δ (f , 1) = g (g, g) is unmarked.
(d, g)
δ (d , 0) = c
δ (g , 0) = g (c, g) is marked. So place an x in (d, g)

(d, h)
δ (d , 0) = c
δ (g , 0) = g (c, g) is marked. So place an x in (d, g)

(d, h)
δ (d , 0) = c
δ (h, 0) = g (c, g) is marked. So place an x in (d, h)

(e, f)
δ (e, 0) = h
δ (f , 0) = c (h, c) is marked. so place x in (e, f)

(e, h)
δ (e, 0) = h
δ (h, 0) = g (h, g) is unmarked.
δ (e, 1) = f
δ (h, 1) = c (f, c) is marked. So place an x in (e, h)

(e, g)
δ (e, 0) = h
δ (g , 0) = g (h, g) is unmarked
δ (e, 1)= f
δ (g , 1)= e (f, e) is marked. So place x in (e, g)

(f, g)
δ (f , 0) = c
δ (g , 0) = g (c, g) is marked. So place an x in (f, g)

(f, h)
δ (f , 0) = c
δ (h, 0) = g (c, g) is marked. So place an x in (f, h)
(g, h)
δ (g , 0) = g
δ (h, 0) = g (g, g) is unmarked
δ (g , 1) = e
δ (h, 1) = c (e, c) is marked. So place x in (g, h)
Now the unmarked place are,
(a, e) (b, h) (d, f) (a, g)
(a, e)
δ (a, 0) = b
δ (e, 0) = h (b, h) is unmarked
δ (a, 1) = f
δ (e, 1)= f (f, f) is unmarked.

(a, g)
δ (a, 0) = b
δ (g , 0) = g (b, g) is marked. So pace an x in (a, g)

(b, h)
δ (b, 0) = g
δ (h, 0) = g (g, g) is unmarked
δ (b, 1) = c
δ (h, 1)= c (c, c) is unmarked.

(d, f)
δ (d , 0) = c
δ (f , 0) = c (c, c) is unmarked
δ (d , 1)= g
δ (f , 1) = g
(g, g) is unmarked.
On completion of the table, we conclude that the equivalent states are
a≡e b≡h d≡f

Algorithm :
begin
for p in F and q in Q-F do mark (p, q) for each pair of disfinct states (p, q)in F x F
or (Q – F) x (Q – F) do
if for some input symbol a
(δ ( p, a), δ (q, a) is marked then begin mark (p, q)
recursively mark all unkarked pairs on the lists of other paurs that are marked at this
step.
end.
else
for all input symbols a do
put (p, q) on the list for (δ ( p, a), δ (q, a) unless
(δ ( p, a) = δ (q , a)
end.

Method II
For the above same problem, the DFA can be minimized using DFA minimization
algorithm.
Solution :
Transition table :
0 1

a b f

b g c

c a c

d c g

e h f

f c g

f c g

g g c

h g c

Step 1
The pair of status (b, h) are same state transition. So b and h are equivalent state.
b≡h
0 1

a b f
 [b,h g c
]

*c a c

d c g

e h f

f c g

g c g

Step 2
The pair of status (d, f) are same state transition.
d≡f
0 1

a [b, h] c

c a c
⇒ [d, c g
f]

e [b, h] [d, f]

g g e

Step e
The pair of states (a, e) are same state transition diagram. ∴ a ≡ e
0 1

[a, e] [b, [d, f]

h]

[b, h] g c

c [a, e] c

[d, f] c g

g g [a, e]

 Thus the minimized FA is

 PUMPING LEMMA FOR REGULAR SETS
Pumping lemma for regular sets :
 Pumping lemma is a powerful for proving certain languages non-regular.
 It is also useful for developing algorithms to answer whether the language
accepted by FA is finite or infinite.
 If languages is regular it is accepted by a DFA M = Q , ∑ , δ , q0 , F ) with some
particular number of states n.
 Consider an input of n or more symbols a, a 2, … am, m ≥ n and for i = 1, 2 …
m let δ (q 0 , a, a 2 .... a i ) = q i
 It is not possible for each of the n + 1 states q 0, q1, …..qn to be distinct, since
there are only n different states.
 Thus there are two integers j and k.
O ≤ j < k ≤ n, such that qj = qk
 The path labeled a, a2…. am in the transition diagram of M.

 Since j<k, the string aj + 1 …. ak is of length atleast 1, and since k ≤ n , its

length is no more than m.
 If qm is in F, that is a, a 2 … am is in L (M) then a, a 2… aj then a, a2 … ajak+1 …
am is also in L (M)
 Since there is a path from q0 to qm that goes through qj but not around the loop.
δ (q0 , a, .... a j a k+1 .... a m ) = δ (δ (q 0 , a 1 ... a j ), a n+1 .... am
= δ (q j , a k+1 ... am )
= δ (q k , ak+1 ... a m )
 = qm
 Similary we can go around the loop, as many times.
 Thus a, .. aj (aj+1 … a)i ak+1 … am is in L (M)
Applications of pumbing lemma :
 The pumping lemma is useful in proving that certain languages are not regular.
1. Select the language L you wish to prove non-regular and assume that L is
regular.
2. The adversary picks n, the constant mentioned in the pumping lemma.
3. Select a string z in L. The choice may depend implicitly on the value of n.
4. The adversary breaks z into u, v and w subject to the constraints that |uv|
¿ n and |v| ¿ 1.
5. Achieve a contradiction to the pumping lemma by showing for any u, v and
w determined by the adversary, that there exists an i for which uvw is not in
L. I may then be concluded that L is not regular you selection of i may
depend on n, u, v and w.
6. The formal statement of the pumping lemma,
(∀ L) (ℑ n) (∀ z) [ z in L and |z|≥n imphess

and (∀ i ) uviw is in L))]

Lemma :
Let L be a regular set. Then there is constant n, such if z is any word in L and |z|
¿ n, we may write z = uvw in such a way that
|uv|≤ n
|v|≥1 and
i
for all i ≥0 uv w is in L
Proof :
Z is a, a2 …. am
u = a1, a2 … aj
v = aj+1 …. ak
w = ak+1 … am
 The pumping lemma states that if a regular set contains a long string, z, then it
contains infinite set of string of the form uviw.

Problems based on pumping lemma :

n n
1. Show that the language L = {a b | n≥ 1 } is not regular
Solution :
n n
(a) Assume that L = {a b | n≥ 1 } is a regular languages.
(b) Let n be the integer, ie) no of states in the pumping lemma.
(c) Take one string z from L
 Z = aibi such that |z|≥n
(4) Break z into 3 strings.
z = uvw
z = a i bi
and mak the assumptions that
uv = am
v = aj
w = ai-m bi
= ai bi
our assumption is correct
i.e) |uv|≤n ε
|v|≥1
since both the conditions are true the string uvkw is also in L
uvkw = uvvk-1w
= amaj(k-1) ai-mbi
= am+j(k-1) bi
put k = 0
uvkw = ai-j bi ¿ ai bi
put k = 2
uvkw = ai+j bi ¿ ai bi
Since for k = 0, 2, the strings that does not belong to the language L. So the language
is not regular.
2

2. Show that L { 0i | i is an int eger i ≥ 1 } is not regular.

Solution :
2

1. Assume L = { 0i | i is an int eger i ≥ 1 }

is regular.
2. Let n be the integer, ie. no. of states in the pumping lemma.
3. Take one string Z
2
n
Let Z = O
4. Break z into z = uvw.
m2
uv = O
2
j
V= O
W = On2 – m2
2 2
m n 2
uvw = O O −m
2
n
= O
Our assumption |uv|≤n ε |v|≥1 is correct.
Since both candidates are true, the string uvkw is also in L
uvkw = uvvk-1w.
 2 2 2 2
m j (k−1) n −m
= O O O
2 2 2 2
m j (k−1) n −m
= O O O
for k = 0
2 2 2 2
−j
m
uvkw = O O On −m
2 2
n 2 n
= O −j ≠ O
for k = 0, 2 the strings vukw does not belong to the language L. so the language is not
regular.