THEORY OF COMPUTATION AND FORMAL METHODS

Course Type – Core L-T-P Format 3-1-0 Credits - 4

COURSE SUMMARY
Introduction to regular expressions, language, finite state machine, NFA, DFA, Mealy machine,
Moore machine, pumping lemma, context free grammar, push down automata, Turing machine,
Chomsky Hierarchy, Halting problem.

COURSE-SPECIFIC LEARNING OUTCOMES (CO)

CO1: Comprehend regular languages and finite automata and develop ability to provide the
equivalence between regular expressions, NFAs, and DFAs.
CO2: Disambiguate context-free grammars by mastering the concepts of context‐free languages
and push‐down automata.
CO3: Apply the concepts of recursive and recursively enumerable languages and design efficient
Turing Machines.

Detailed Syllabus

Unit 2 (Contact hours: 8)

Minimization of DFA. Convert NDFA to DFA, Finite State Machine with output- Moore
machine and Mealy Machine, Conversion of Moore machine to Mealy Machine & Vice-Versa,
Conversion of NFA with Є to NFA without Є,

TEXTBOOKS/LEARNING RESOURCES:
a) J. E. Hopcroft, J. D. Ullman and R. Motwani, Introduction to Automata Theory,
Languages and Computation (3rd ed.), Pearson Education, 2006. ISBN 978-
0321455369.
b) John C. Martin, Introduction to Languages and the Theory of Computation (3rd ed.),
McGraw-Hill Higher Education, 2001. ISBN 978-0070660489.

REFERENCE BOOKS/LEARNING RESOURCES:

a) Michael Sipser, Introduction to the Theory of Computation (3rd ed.), Cengage, 2014.
ISBN 978-8131525296.

b) Theory of Computer Science, K.L.P.Mishra, N.Chandrasekaran.

 THEORY OF COMPUTATION
NON-DETERMINISTIC FINITE AUTOMATA (NFA):
In DFA, starting at a state by reading a string 'w', it will reach exactly one either state or
remains in same state. But the result is only one state. q1 w q2

In NFA, starting at a state by reading a string 'w', it may reach more than one state and
may not goto any state i.e., no state may be stated  . So, we call it as NFA

In real life, human computers and other mechanical devices are DFA's. But where we find
NFA. In reality no where we found. It is actually used for exhaustive search and
backtracking.

For example, In Chess game we check for possible steps and result of those steps and
come back and choose one.

In DFA, we have no options to select 'd' options, We need to move to a state

q1 w
q1
q2
q3
.
.q
n


NFA is also represented with quintuple(set of five elements or five parts) Q, ,  , q0 , F 
Where Q - is a finite set of states
 - is input alphabet
q 0 - start symbol / initial state
F - is a set of final states
delta  - is transition function Q    2 Q (Power set of Q)

By considering the following example we can explain to construct a NFA for which
accepts set of all strings over {a,b} such that where every string ends with 'a'.

Language is L={every string ends with 'a'}

L={a,aa,ba,............}

a,b
a
A > B A > A
>
B

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 1

 THEORY OF COMPUTATION
Construction of NFA is very simple when compared to DFA
a,b
It means string can start with anything but ends with 'a'

If we observe the above NFA, it is definitely not DFA, because on state 'B' we didn't see
the inputs i.e., what happens if we get 'a' or 'b' as inputs.

Moreover, if we look at state 'A', we are giving the transition in two ways. one is on
seeing 'a' we are staying in the same state or goto the next state. Now we have to decide
the acceptance state.

Let us enumerate the language i.e., the language contains the set of all strings ends with
'a' L={a,aa,ba,..........}
A a
A
B

This is called Non Deterministic Finite Automata, means on seeing input at state it go to
more than states or even go to no state also. From the above we have to decide the
acceptance i.e, by considering the other example which is not in the language i.e., ends
with 'b' a b
A A A
?
B 

From the above the state 'B' does not have any move if we give the input as 'b'. So, it is
called DEAD configuration, means it will not lead us to any state 
Finally we end up with only to one state 'A' and 'A' is a non accepting state. Therefore,
'b' is rejected because we are not able to reach any of other state. SO ,it is rejected.

Let us say Q  { A, B} and   {a , b}

(A ,a ) 

> {A }
(A ,b ) >

(B ,a ) {B }

> > {A ,B }
(B ,b )

Q 2Q (set of all possible sets)

Therefore for NFA is  : Q    2 , DFA is  : Q    Q , because 'Q' is also a part of 2Q ,
Q

therefore we can say that Every DFA is NFA

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 2

 THEORY OF COMPUTATION
Example 41: Construct a NFA which accepts set of all strings over {a,b} such that set of all
strings that start with 'a'

According to the example we have to construct NFA for set all strings that start with 'a'.
  {a , b}
The language is L1  {a , aa, ab, aaa , aba,......... .......... } .
a,b
a
A > B

For Ex, Let us check for the given string 'ab', the above NFA is accepted or not

a b
A > B > B It is accepted

So the final state is 'B'

Let us take another Ex, for the given string 'ba', the above NFA is accepted or not
b
A >  It is not accepted, it reaches to Dead Configuration

Dear Configuration: It is nothing but, if we are in one state A on seeing a symbol 'b', if
we do not have any move, then this is called Dead Configuration.

NOTE: In DFA we have to complete the states, but in NFA we are not bother about
states on seeing some string, means from the above example we do not bother about
state 'A' on seeing about string 'b'

Let us discuss to construct the DFA for the same problem as we have constructed in DFA
examples as shown once again
a,b a,b
a a
A > B A > B
b b
>

>

a,b a,b

DFA NFA

Now observe the difference between the DFA & NFA for the same example, In NFA, the
Dead Configuration (dotted lines box) should not be there, means we do not need Dead
configuration in NFA.

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 3

 THEORY OF COMPUTATION
Example 42: Construct a NFA which accepts set of all strings over {a,b} such that set of all
strings that contains 'a'

The Language is L2={a,ab,ba,aa,aab,............}

b
a a,b
A > B

Example 43: Construct a NFA which accepts set of all strings over {a,b} such that set of all
strings ends 'a'

The Language is L3={a,aa,ba,aaa,aba,..................}

a,b
a
A > B

Example 44: Construct a NFA which accepts set of all strings over {a,b} such that set of all
strings starts with 'ab'

The Language is L4={ab,aba,abb,.........................}

a b a,b
A > B > C

Example 45: Construct a NFA which accepts set of all strings over {a,b} such that set of all
strings which contains 'ab'

The Language is L5={ab,aba,abb,abab,aaab,.........................}

a,b
a b a,b
A > B > C

Example 46: Construct a NFA which accepts set of all strings over {a,b} such that set of all
strings which ends with 'ab'

The Language is L6={ab,aab,bab,aaab,abab,..................}

a ,b
a b
A > B > C

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 4

 THEORY OF COMPUTATION
CONVERSTION OF NFA TO DFA

Construction of NFA is very much simpler or easier when compare to DFA. But which
one is powerful and easy. So NFA is easier.

But both NFA and DFA are equal in powerful, it means we can take a NFA and convert
into DFA and Vice-Versa NFA DFA & DFA NFA

We can say that both NFA & DFA are equal in powers i.e., NFA  DFA

But we know that every DFA is NFA. So we need not do the conversion of DFA to NFA,
only we can take the conversion of NFA to DFA

Example 47: Now we can explain by consider the following example, set of all strings
that start with 'a'

  {a, b}, L1 ={set of all strings start with 'a'} ={a,ab,aa,aaa,aab,aba,abb,..........}.

a,b
a
A > B This is called Transition Diagram

The above is NFA and now we want to convert into DFA . There are many methods to
convert NFA to DFA. But here we are using the method called "Subset Construction /
Subset Substitution".
Now we can explain the above example by using the 'Subset Construction'
 From the Transition Diagram we construct the State Transition Table(STT) as
follows for the above NFA.
a b

A B  It does not have any move

B B B

 By using the State Transition Table of NFA we construct the DFA which is easier

a b
A B D
B B B
D D D

 The above is the State Transition Table for DFA

 While converting STT of NFA to STT of DFA,  takes as D(Dead State in DFA)
 While constructing the table we take the states from the table only, it means we
started with state 'A' later we find B,D states, if any new state is found we use it in
the table

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 5

 THEORY OF COMPUTATION
 From the above STT of DFA we construct the State Transition Diagram(STD) of
DFA
a a,b
A > B

>
b

D a,b

 By observing the STD of DFA & NFA, In NFA the state 'A' is not complete but in
DFA, the state 'A' is complete

Example 48: Conversion of NFA to DFA for "all strings that ends with 'a'

The Language is L = {set of all strings ends with an 'a'}

= {a,aa,ba,aaa,aba,baa,.....................}. The NFA is
a,b
a
A > B

The State Transition Table for the above State Transition Diagram of NFA is as below

a b

A {A,B} {A}

B  

Now we convert the above into STT for DFA.

We shall start with initial state and keep on constructing the DFA
a b
A [AB] [A]
[AB] [AB] [A]

 If there are two states in DFA, then go to the both the states in NFA and see what
happens on transition on input 'a' and union them
 In DFA, We consider the two states of NFA as Single State i.e.,{A,B} are two states
can be taken as single state as [AB].
 Because in NFA, on seeing one transition from one state it will go to (move to)
more than one state.
 But in DFA, it should move to only one state that is why we take it as [AB] as
single state.

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 6

 THEORY OF COMPUTATION
Example 49: Conversion of NFA to DFA for "all strings in which second symbol from
RHS is 'a'

In DFA we have seen a problem that second symbol from LHS is 'a' i.e.,  a   . The
DFA as below The NFA for the above example is
a,b
a,b
a,b
a
A > B > C a,b a
> A > B > C
b
a,b NFA

DFA

Now we shall see what happens if the second symbol from RHS ia 'a'. First we construct
the NFA is always easy
The Language is L={ aa, ab, aaa, a ab,..........}
a,b
a a,b
A > B > C

NFA
State Transition Table for the above NFA State Transition Table of DFA for the above
State Transition Table of NFA

a b
a b
 [A] [AB] [A]
A {A,B} {A}
[AB] [ABC] [AC]
B {C} {C}
 [ AC ] [AB] [A]
C  
*[ABC] [ABC] [AC]

State Transition Diagram for the DFA from the above SST of DFA
b a
a a
A > AB > ABC

a
> >

b b
<

b
<

AC

DFA

Here the final state are of any state containing in 'C'. Because in NFA 'C' is the final state
Let us check by considering some examples

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 7

 THEORY OF COMPUTATION
bbbaa----AB--a----ABC--------- Accepted
bbbab----AB--b----AC---------- Accepted
Here after seeing any number of b's, if there is 'a', it goes to state AB and if we see
another 'a' it moves to state 'ABC'.ie., final state. So the given string is accepted

Here after seeing any number of b's, if there is 'a', it goes to state AB and if we see
another 'a' it moves to state 'ABC',i.e., final state. So the given string is accepted

Here after seeing any number of b's, if there is 'a', it goes to state AB and if we see
another 'b' it moves to state 'AC', i.e., final state. So the given string is accepted

Suppose If we are in state 'ABC', check whether the given string bbbaaaa is accepted or
not. It is accepted

The given string bbbbaaabb----------- Not Accepted, It moves to state A which is non final
state

Note: It is efficient to give DFA directly by considering all possibilities. So, We can
construct NFA and later convert to DFA is easy

Example 50: Conversion of NFA to DFA for "all strings in which third symbol from RHS
is 'a'

The Language is L={ _ _ a _ _ ,} third symbol from RHS is ‘a’ i.e., *  aaa, aab, aba, abb,
The NFA for the above example is
a,b
a a,b a,b
A > B > C > D

State Transition Table for the above NFA State Transition Table of DFA

a b a b
A {A,B} {A}  [A] [AB] [A]
B {C} {C} [AB] [ABC] [AC]
C {D} {D} [AC] [ABD] [AD]
*D   *[AD] [AB] [A]
[ABC] [ABCD] [ACD]
*[ABD] [ABC] [AC]
*[ACD] [ABD] [AD]
*[ABCD] [ABCD] [ACD]

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 8

 THEORY OF COMPUTATION

Note:
1. In NFA, if there are ‘n’ states, if we construct a DFA for the same NFA, we may
get 2n states in worst case in DFA
2. From the above example, for 4 states in NFA, we get 8 states, But in worst case it
may be 16 states.

Example 51: Construct a NFA which accepts set of all strings over {a,b} such that the
length of string
Exactly 2 Alteast 2
a,b
a,b a,b a,b a,b
A > B > C A > B > C

A tm o st 2

a,b a ,b
A > B > C

Question: What is the minimal no of states that are present in a finite automata which
accepts set of all strings of length ‘n’.
Answer: (n+1) states
By Observing for a given finite automata, no of states in DFA≥NFA for a given language.
L

n(DFA)  n(NFA)

Complementation of NFA
We have already seen the complementation of DFA. If DFA is complemented, the
language accepted is completed. But in case of NFA it is not true.

Example 52: Complementation of NFA to DFA for "set of each string starts with 'a' over
{a,b}
First we construct the NFA for set of each string starts with ‘a’ over {a,b}
The Language L1 ={a,aa,ab,aaa,.......} It is Infinite
a,b
a
M: A > B

Now we can construct the complementation to the above NFA by using the following
points
 Change the Final States of NFA into Non-Final States
 Change the Non-Final States of NFA into Final States
 And leave all the transitions as it is means don’t change the transition

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 9

 THEORY OF COMPUTATION
a,b
a
M: A > B

From the above complementation of NFA, the language L2 {  , a, aa, ab, aaa,......} this
language L2 is containing  . By observing the L1 and L2, the complemented NFA is not
giving the language in L1.

Note: In DFA, when the DFA is complemented, then accepting language is also
complemented.
In case of NFA, the language accepted by the complement of NFA may or may not be
complement of language accepted by NFA.

Question:
 What is the language accepted by the complement of NFA?
L={ set of all strings starts with ‘a’}
L ={set of all strings that does not start with ‘a’,
which means it starts with ‘b’ or }
 What is the complement of language accepted by NFA?
The answer is { }
Both questions are same

Minimization of FINITE STATE MACHINE (FSM)

Before moving to minimization FSM, we can understand about the states and
equivalence between the states.

EQUIVANCE BETWEEN TWO FSM

Assume p and q are two states, then can say that p and q are equivalent if p and q can be
replaced by a Single State.

Suppose  ( p , w)  F   ( q, w)  F , it means upon reading some string ‘w’, if p reaches to

Final State and q also reaches to Final State, then we can say the p and q are equivalent
and they can be replaced in a Single State.

Otherwise  ( p , w)  F   ( q, w)  F , it means upon reading some string ‘w’ if it reaches

to Non-Final state and if q also reaches to Non-Final state, then we can say that p and q
are equivalent and they can be replaced in a Single State.

If  ( p , w)  F   ( q, w)  F , it means upon reading some string ‘w’ if it reaches to Final

state and if q reaches to Non-final state, then we can say that p and q are not equivalent.
If  ( p , w)  F   ( q, w)  F , it means upon reading some string ‘w’ if it reaches to Non -
Final state and if q reaches to Final state, then we can say that p and q are not
equivalent.
Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 10
 THEORY OF COMPUTATION

Example: Find out whether the following Finite Automata are equivalent or not
a a
q1 b
q4

b b b b a a
a b

q2 q3 q5 a q6 b
a

DFA of X DFA of Y

States a b
(q1,q4) (q1,q4)reaching to FS (q2,q5)  reaching to NFS
(q2,q5) (q3,q6)  reaching to NFS (q1,q4)reaching to FS
(q3,q6) (q2,q7)  reaching to NFS (q3,q6)  reaching to NFS
(q2,q7) (q3,q6)  reaching to NFS (q1,q4)reaching to FS

By observing the above the two DFA’s X and Y are equivalent

Example: Find out whether the following Finite Automata are equivalent or not

c c

q1 c
q4
c
d d b d
c d c

q2 q3 q5 q6 d
d
c

DFA of P DFA of Q

States c d
(q1,q4) (q1,q4)reaching to FS (q2,q5)  reaching to NFS
(q2,q5) (q3,q7)  reaching to (q1,q6)q1 reaches to FS and
NFS q6 reaching to NFS.
By observing both states are not reaching
to same states. So, the given above two
DFA’s are not equivalent

So, the given above two DFA’s are not equivalent

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 11

 THEORY OF COMPUTATION

Minimization of FINITE STATE MACHINE (FSM)

Note:
 If |w|=0, then p, q are ‘0’ equivalent
 If |w|=1, then p, q are ‘1’ equivalent
 If |w|=2, then p, q are ‘2’ equivalent
 If |w|=n, then p, q are ‘n’ equivalent
If both states are equivalent for possible string length then both can be replaced by a
Single state.

Example 53: By apply the following steps, we can construct the minimization of DFA
Step1: Identify the initial state and final state
Step2: Remove the states that are not reachable from the initial state
Step3: Draw the State Transition Table
Step4: Try to separate and write the Non-final State and Final State to get ‘0’ equivalent
and continue the same process
Step5: Then find the nth equivalent sets for n=0 till the sets are not changing
Step6: Construct the new DFA

Example1: Conversion of DFA to NFA for the following DFA

a
a
q1 q3
a b

qo a b
a
b
q2 q4
b
b
Step1: Here q0 and q4 are initial and final states
Step2: All the states are in the above DFA are reaching from initial state. There is no state
which is not reaching from initial state
Step3: The State Transition Table is as follows
a b
[q0, q1, q2,q3] [q4]  ‘0’ equi
 q0 q1 q2
[q0, q1, q2] [q3] [q4]  ‘1’ equi
q1 q1 q3 [q0, q2] [q1] [q3] [q4]  ‘2’ equi
q2 q1 q2 [q0, q2] [q1] [q3] [q4]  ‘3’ equi

q3 q1 *q4
* q4 q1 q2

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 12

 THEORY OF COMPUTATION
Step4:
i) Separate the Non-final States as a group and Final States as group

[q0, q1, q2,q3] [q4] which is nothing but ‘0’ equivalence

ii) Find one equivalence: For one equivalence take any two states and check their states
when reading an input, if they are in the same group they are equivalent, otherwise not
equivalent separate the states.
Now compare q0 and q1

a b
q0 q1 q0 q2 By observing q1, q2 & q3 are in the same group. So they
a b
q1 q1 q1 q3 are equivalent

[q0, q1, ] [q4]

Now compare q0 and q2

a b
q0 q1 q0 q2 By observing q1 & q2 are in the same group. So they
a q2 b are equivalent
q2 q1 q2

[q0, q1, q2, ] [q4]

Now compare q0 and q3

a b By observing q1 , q2 & q4 are not in the same group.
q0 q1 q0 q2
b So, we can say that q3 is not ‘1’ equivalent. Therefore
q3 a q3 q4
q1 Write it separately.

[q0, q1, q2] [q3] [q4]  which is nothing but ‘1’ equivalence

iii) Find two equivalence: For two equivalence take any two states from the one
equivalence and check their states when reading an input, if they are in the same group
they are equivalent, otherwise not equivalent separate the states
Now compare q0 and q1
a b By observing q1 , q2 & q3 are not in the same group.
q0 q1 q0 q2
b So, we can say that q0 and q1 is not equivalent.
q1 a q1 q 1 q 3 Therefore Write it separately.

[q0, [q1, [q3] [q4]

Now compare q0 and q2
a b By observing q0 & q2 are in the same group. So they
q0 q1 q0 q2
are equivalent
a q2 b
q2 q1 q1

[q0, q2] [q1] [q3] [q4]  which is nothing but ‘2’ equivalence

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 13

 THEORY OF COMPUTATION

iv) Find three equivalence: For three equivalence take any two states from the two
equivalence and check their states when reading an input, if they are in the same group
they are equivalent, otherwise not equivalent separate the states
Now compare q0 and q2

a b
q0 q1 q0 q2 By observing q0 & q2 are in the same group. So
b
q2 a
q1 q2 q they are equivalent
1

[q0, q2] [q1] [q3] [q4]  which is nothing but ‘3’ equivalence

Step5: By Observing (iii) and (iv) there is no change of equivalence. Therefore, stop
finding of the equivalence and the last equivalence is the final of minimised states.

Step6: Construct the DFA by considering the above states

b a
a b b
q 0q 2 q1 q3 q4
a

a
b

Example2: Conversion of DFA to NFA for the following DFA

0 1

q0 0 1 q2 0
q1 q3
1
1
0 1
0
1 1 0
q4 q5 q6 q7
0
1

After solving by using above example

The minimization states are [q0,q4] [q1,q7] [q5] [q6] [q2]

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 14

 THEORY OF COMPUTATION

Example3: Conversion of DFA to NFA for the following DFA

b a
b

a b
q0 q1 q2

a b

q3

After solving the minimization states are [q0] [q1, q2]

Example4: Conversion of DFA to NFA for the following DFA

0 1
0 0

1 0,1
a c e

1 0
1
d

After solving the minimization states are [a] [b,c,d][e]

Example4: Conversion of DFA to NFA for the following DFA
b a b
b a q5
q0 q3 q4
b

a a b a a
a
b
q1 a
q2 q7 q6
b

The minimization states are [q0] [q1] [q2] [q3]

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 15

 THEORY OF COMPUTATION

MOORE MACHINE AND MEALY MACHINE

Till now we have seen the finite automata without Output i.e., DFA and NFA. Now we
will see finite automata with output means where there will take an input as well as keep
on writing output.

There are two types of machines under this category

Moore Machine: This machine has output on the states itself.
Mealy Machine: This machine has output on the transitions

Note:
a) Till now we have seen automata with no output those are language accepters
b) Now we will see language transducers means they will convert input to output

In order to discuss about the above two machines, we have to see the common part of
them.

FINITE AUTOMATA WITH OUTPUT

Moore Machine Common Part Mealy Machine

(Q, ,  ,q 0 , ,  ) a/1 b/0

a b Q - is a finite set of states
b/0
 - is input alphabet q0 q1
b
q0,1 q1,0  Q  Q
a
q 0 - start symbol a/1
  o/p Alphabet
 :Q  
 :Q     o/p function

Moore machine shows Moore machine shows

output on state itself so if output on transition
input ε then also we will get
one output

Output Alphabet: is the symbols which are supposed to printed.

Output Function: will determine what will be printed as output.

Both Moore and Mealy Machines are Deterministic. The only difference between the
Moore and Mealy machine is only  .
In Moore Machine,  is a function from Q   , which means for every state output is
associated. From the above example,

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 16

 THEORY OF COMPUTATION
i) For a State q0, is associated with a output as ‘1’ (q0  1)
ii) For a State q1, is associated with a output as ‘0’ ( q1  0)
In Mealy Machine, Output is associated like as, for a State for a given input, there will be
some output, which means for the above example
i) For a state q0, if the input is ‘a’, then the output will be ‘1’ (q0 , a )  1
ii) For a state q0, if the input is ‘b’, then the output will be ‘0’ (q0 , b)  0
iii) For a state q1, if the input is ‘a’, then the output will be ‘1’ ( q1 , a )  1
iv) For a state q1, if the input is ‘b’, then the output will be ‘0’ ( q1 , b)  0

Example 1: For a given Moore Machine, what happens if we give an input as ‘ab’

q0 a b
q0 q1

1 1 0
On seeing input ‘ab’ that particular Moore Machine has printed the output as ‘110’

Note: If we give string length ‘n’ as input, the output produced will be a string length of
(n+1). Because without seeing anything the state ‘q0’ is producing something output.

Example 2: For a given Mealy Machine, what happens if we give an input as ‘ab’
a b q
q0 q0 1

1 0
Initially we are at q0, upon seeing on ‘a’, it is going to print ‘1’. Here output is not
associated with this state that is why it will not print anything.

Note: If we give string length ‘n’ as input, the output produced will be a string length of
(n) only.

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 17

 THEORY OF COMPUTATION

Example 3: Construct a Moore Machine that takes a set of all strings over {a,b} as input
and prints ‘1’ as output for every occurrence of ‘ab’ as a substring.

Here the input alphabet is   {a , b} and the output is   {0,1}

If we see ab, it prints ‘1’
If we see abab, it prints ‘11’
If we see abbbab, it prints ‘11’
If we see ababab, it prints ‘111’

By observing, it is nothing but counting number of ab’s. In order to construct this we

have to consider the following three points

i) We can design the DFMachine for set of all strings starting with ‘ab’. But we
cannot see remaining ab’s

a b a,b
A > B > C

ii) We can design the DFMachine for set of all strings containing ‘ab’, we cannot
see ‘ab’ at the end
b a a,b
a b
A > B > C

iii) We can design the DFMachine for set of all strings ending ‘ab’, we can see ‘ab’
at the end
b a
a b
A > B > C
a
<
b
<
Whenever we see ab, we are reaching to state ‘C’. So state ‘C’ made with a
output ‘1’ and for remaining states we can give simply ‘0’ as output.
b a
a b
A,0 > B,0 > C,1
a
<
b
<
Let us check by giving any strings

a b a b a b
A B C A B C B C

0 0 1 0 0 1 0 1

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 18

 THEORY OF COMPUTATION

Example 4: Construct a Moore Machine that takes a set of all strings over {a,b} and
counts number of occurrence of a substring ‘baa’.

Here the input alphabet is   {a , b} and the output is   {0,1}  Assume that we may
take anything as output
To count no of occurrence of ‘baa’, we have to construct the DFA, that accepts set of all
strings ending with ‘baa’. Whenever count will be there, always ending will helps
because it will keep track of all baa’s
a b

a a
b C,0
A,0 B,0 D,1
b
b
a

Whenever ‘baa’ occurs, it prints the ‘1’ as output at state D.

Let us check by giving any strings
b a a b a a b a a
A B C D A B C D B C D
0 0 0 1 0 0 0 1 0 0 1

Example 5: Construct a Moore Machine that takes a set of all strings over {a,b} and
produces ‘A’ as o/p if i/p ends with ‘10’ or produces ‘B’ as o/p if i/p ends with ‘11’,
otherwise produces ‘C’.

Here the input alphabet is   {a , b} and the output is   { A, B, C}

If input produces ‘10’, then output is ‘A’ (10A). If input produces ‘11’, then output is ‘B’
(11B). Otherwise ‘C’.
Here we have to draw a DFA, where the string is going to ending with ‘10’ or ‘11’.
0 1
1 1
X,C Y,C Z,B

0 1 0 0 110

1001
W,A
101

Let us check by giving any strings

1 1 1 1 1 0
X Y Z Z X Y Z W

C C B B C C B A
N e e d n o t c a re
a b o u t th e se

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 19

 THEORY OF COMPUTATION

Example 6: Construct a Moore Machine that takes binary numbers as i/p and produces
residue modulo ‘3’ as o/p

Here the input alphabet is   {0,1}

Residue modulo means by taking the binary number abd divide with ‘3’, whatever the
remainder will get that should be print. So   {0,1, 2} these are possible remainders
when we divide any number by ‘3’
This is nothing but DFA which accepts set of all strings which are divisible by ‘3’.
Whenever a number is divisible by ‘3’, the number of states will be ‘3’. Let us say A,B
and C.
State A  corresponds the state with reminder ‘0’
State B  corresponds the state with reminder ‘1’
State C  corresponds the state with reminder ‘2’
It is better to construct the State Transition table for easy purpose

0 1
A A B
B C A
C B C
Now from the above STT of DFA, the Moore Machine can be constructed by adding 
to the STT of DFA

0 1 
A A B 0
B C A 1
C B C 2
The above is the STT of Moore Machine, by using this we can construct the STD of
Moore Machine
0
1
1 0
A,0 B,1 C,2
1 0

We can extend the above question as follows

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 20

 THEORY OF COMPUTATION
Example 7: Construct a Moore Machine that takes base ‘4’ numbers as i/p and produces
residue modulo ‘5’ as o/p

Here the input alphabet is   {0,1, 2,3}`  base 4 numbers

So   {0,1,2,3,4} these are possible remainders when we divide any number by ‘3’

0 1 2 3 
A A B C D 0
B E A B C 1
C D E A B 2
D C D E A 3
E B C D E 4

Complete it for your exercise.

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 21

 THEORY OF COMPUTATION
Example 8: Construct a Mealy Machine that takes binary numbers as i/p and produces
2’s complement of that number as o/p. Assume the string is read from LSB to MSB and
end carry is discarded

Mealy Machine is nothing but for every state for every input there will be output.
Here the input alphabet is   {0,1}`
  {0,1}  output as 2’s complement as binary numbers
First Let us try to find the 1’s complement for the given binary numbers ‘1011’
1 0 1 1  given binary number
0 1 0 0  1’s complement
The Mealy Machine for the 1’s complement is as follows
0/1
q0 1 q0 0 1 1
q0 q0 q0
q0
0 1 0 0
1/0

1’s complement is very easy to construct because whenever we see a ‘0’ we are going to
print ‘1’ and whenever we see a ‘1’ we are going to print ‘0’.
But 2’s complement is not very easy. For let us discuss about 2’s complement for taking
the following examples
Ex1: Ex2:
1 1 0 0  given binary number 1 1 1 0 1 1 0 0  given binary number
0 0 1 1  1’s complement 0 0 0 1 0 0 1 1  1’s complement
1 1
----------- -----------
0 1 0 0  2’s complement 0 0 0 1 0 1 0 0  2’s complement

By observing the above two examples, when reading from LSB to MSB, if there are
zero’s from LSB side leave them as zero’s and whenever we see the first ‘1’ leave it as ‘1’
and whatever is there after ‘1’ it is going to complemented.
0/0
0/1
1/1
q0 q1

1/0

Read from LSB

1 1 0 0 q0 0 q0 0 1 1
q0 q1 q1
0 0 1 1
1
0 0 1 0
0 1 0 0

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 22

 THEORY OF COMPUTATION
CONVERSTION OF MOORE MACHINE TO MEALY MACHINE

First we discuss about Moore Machine is powerful or Mealy Machine is powerful.

If we have to say that Moore is powerful than Mealy, then Moore should be solved
some problems which Mealy will not be able to solve.

If we have to say that Mealy is powerful than Moore, then Mealy should be solved some
problems which Moore will not able to solve
But both are actually equivalent in power Moore  Mealy
If we have to show that both are equivalent in power, we have to take a Moore
Machine, if we convert into Mealy Machine and we have to take Mealy Machine, if we
convert into Moore Machine, then we can say that both are equivalent in power.

We convert the Moore to Mealy Machine by two ways

a) By using STDaigram, simply by adding the output associated with that state to that
transition and remove the output associated to the State
b) By constructing the SST of Moore and convert into SST of Mealy

Example: Conversion of Moore to Mealy Machine for count number of a’s % 3.

Method1 b b b

a a will not count

q0,0 q1,1 q2,2

For the above given Moore Machine State Transition Diagram convert into Mealy
Machine State Transition Diagram, simply by adding the output associated with that state
to that transition and remove the output associated to the State
b/0 b/1 b/2

a/1 a/2
q0 q1 q2

a/0

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 23

 THEORY OF COMPUTATION
Method2:
 Construct the STT of Moore Machine
 Convert the SST of Moore Machine to STT of Mealy Machine by removing output
alphabet column on SST of Moore and add that output alphabet to the transition
of that particular state in the table

STT of Moore STT of Mealy

a b  a b
 q0 q1 q0 0  q0 (q1,1) (q0,0)
q1 q2 q1 1 q1 (q2,2) (q1,1)
q2 q0 q2 2 q2 (q0,0) (q2,2)

Example: Conversion of Moore to Mealy Machine for the string ending with ‘ab’

Method1:
Moore Machine for the string ending with ‘ab’
b a
a b
A,0 > B,0 > C,1
a
<
b
<
Mealy Machine for the string ending with ‘ab’

b/0 a/0
a/0 b/1
A > B > C
a/0
<
b/o
<

Method2:

STT of Mealy
STT of Moore
a b
a b 
A (B,0) (A,0)
A B A 0
B (B,0) (C,1)
B B C 0
C (B,0) (B,0)
C B A 1

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 24

 THEORY OF COMPUTATION

Example: Conversion of Mealy Machine to Moore Machine

0/Z2
q1 0/Z1
q2
0/Z1
1/Z1 1/Z1

q3
0/Z2

The following is the Moore Machine

q1 0
q2/Z1

q3/Z1

Now take q2 State and complete the transitions

0 0
q1 q2/Z1 q2/Z2

1 1

q3/Z1

Now try to complete the state q3/Z1 and q3/Z2

q1 0 0
q2/Z1 q2/Z2

1 1
0 0

q3/Z1 q3/Z2
1
1

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 25

 THEORY OF COMPUTATION

Now try to complete the state q2/Z2

0 0
q1 q2/Z1 q2/Z2 0

1 1
0 0
1

q3/Z1 q3/Z2
1
1

Example: Conversion of Mealy Machine to Moore Machine

0/0
0/1
1/1
A B

1/0

0
0 1
1 1
A,0 B,1 B,0
0

Dr. KAMALAKAR RAMINENI THEORY OF COMPUTATION Page 26