Formal Languages and Automata Theory.

( Comp403 )
Chapter 2 The Theory of Automata

Definition of an Automata.
An Automaton is defined as a system where energy, materials and
information’s are transformed, transmitted and used for performing some
functions without direct help of man. Example automatic packing machine
and automatic photo printing machines.
I0 Automaton O0
I1 q1,q2…..…qn O1
In On

Fig. shows model discrete automaton

Input. At each of the discrete instants of time t1,t2,…., input values I1,I2….,
each of which can take a finite numbers of fixed values from input alphabets
, are applied to input side of the model shown in above fig.
Output. O1,O2,….OQ are the outputs of the model, each of which can take
finite numbers of fixed values from an output.
States. At any instants of time automaton can be in one of the states
Q1,Q2,…Qn.
State relation. The next stage of an automaton at any instant of time is
determined by the present state and the present input.
Output Relation. Output is related to either state only or to both the input
and state.
Note. An Automaton in which the output depends only on the input is called
an automaton without memory. An Automaton in which the output depends
on the states also is called an automaton with a finite memory. An Automaton
in which the output depends on the states of the machine is called a Moore
Machine. An Automaton in which the output depend on the current state
and the input at any instant of time is called a Mealy Machine.

Description of a Finite Automaton.

A finite automaton (DFA) can be represented by a 5-Tuple (K, , δ, q0,F)
where:
K is a finite non-empty set of states;
 is a finite non-empty set of an alphabet or symbols;
q0 in K is the starting state;
δ is a mapping function which maps K *  and usually direct transition
function; and
F  K is the set of accepting (final) states.

Transition Systems
A transition graph or a transition system is a finite directed labeled graph in
which each vertex or node represents a state and the directed edges indicate
the transition of a state and the edges are labeled with input/output. An
1|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
initial state represented by a circle with an arrow pointing towards it, the final
state by two concentric circles, and the other states are represented by one
circle.
Properties of Transition Function.
Property 1. δ(q, ) = q in a finite automaton. This means the state of the
system can be changed only by an input symbol.
Property 2. For all strings W and input symbols a.
δ(q, aw) = δ ( δ(q, a), w)
δ(q, wa) = δ ( δ(q, w), a)
This property gives the state after the automaton reads the first symbol of a
string aw and the state after the automaton reads a prefix of the string wa.
Example : prove that for any transition function δ and for any two input string
x and y. δ(q, xy) = δ ( δ(q, x), y)  2.1
Proof: By the method of induction on |y|. i.e. length of y. when |y|=1,y=a.
L.H.S. of (2.1) = δ(q, xa) = δ ( δ(q, x), a) by property 2.
= R.H.S. of (2.1)
Finite State Automata
Serial Adder.
Input = {00,01,10,11}
Output = {0,1}
Example. 100101
101110
1010011

10 01 11 01 00 11 00
q0 q0 q0 q1 q1 q0q1q0
1 1 0 0 1 0 1
Initial state is q0. Input is pair of binary numbers and output is either 0 or 1.
Start from q0, read 10 and output is 1, again go to q0, from q0, read 01 and
output is 1, again go to q0, from q0, read 11 and output is 0, again go to q1,
from q1, read 01 and output is 0, again go to q1, from q1, read 00 and output
is 1, again go to q0, from q0, read 11 and output is 0, again go to q1, from q1,
read 00 and output is 1, again go to q0. State q0 is a no carry state and q1 is a
carry state.
Parity Checker.
Input = { 0, 1 } = output. Where t is
time instant, I is an input, ss is a state
sequence and o is a output. Initial state
is a q0. The given string is 01101001.
This machine has check no of 1’s in the
input string. i.e. There are 4 ones in the
input so final output is 0 in the time
instant t=8. That is even parity
t 1 2 3 4 5 6 7 8
I 0 1 1 0 1 0 0 1

2|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
ss q0  q0  Q1  q0  q0  Q1  Q1  Q1  q0

O 0 1 0 0 1 1 1 0

One time Delay Machine.

Input = { 0, 1 } = output. Where t is time
instant, I is an input, ss is a state sequence
and o is an output. Initial state is a q0. The
given string is 01101001. Same input will be
get as output after the time instant t=2. So
we can say this machine is one time delay
machine. Following table show the process of
the machine.
t 1 2 3 4 5 6 7 8

I 0 1 1 0 1 0 0 0 0/1

ss q0  q0  Q1  q1  q0  Q1  q0  q0  q1

O 0 0 1 1 0 1 1 0 1

ACCEPTABILITY OF A STRING BY A FINITE AUTOMATON

Consider the finite state machine whose ={a,b}, K={q0,q1,q2,D},q0 in K is a
initial state, final state is q2 transition function δ is given in the table. Give the
entire sequence of state for the input string aaabb.
a B
 q0 q1 D
q1 q1 q2
* q2 D q2
D D D

The sequence of a’s followed by sequence b’s accepted by this machine. At

least one a and one b will be accepted. In the above fig. and table D is dead
state. Start from q0, read a and go to q1, from q1, read a and again go to q1,
from q1, read a and again go to q1, from q1, read b and go to q2, from q2,
read b and again go to q2, State q2 is a final state. The state sequence of given
input is q0q1q1q1q2q2. The string starting with b is not accepted by
the machine. The string end with a is not accepted by the machine.

Extend δ to δ1 : K *  *  K
δ1 (q,) = K for all q in K
x  *, a  , q  K
δ1(q, xa) = δ ( δ1(q, x), a)
δ1(q, a) = δ (q, a)
L(m) set of stings accepted.
T(m) = {x/x  + , δ (q0, x)  F}

3|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
Consider the finite state machine whose ={0,1}, K={q0,q1,q2, q3},q0 in K is a
initial state, final state is q0. transition function δ is given in the table. Give the
entire sequence of state for the input string 110101.

δ(q0, 110101) = δ(q1, 10101) = δ(q0, 0101)

= δ(q2, 101) = δ(q3, 01)
= δ(q1, 1) = δ(q0, )
= q0
Hence state sequence is given below
1 1 0 1 0 1
q0  q1  q0  q2  q3  q1 q0.

Initial state is q0. Input is either 0 or 1. Start from q0, read 1 and go to q1,
from q1, read 1 and go to q0, from q0, read 0 and go to q2, from q2, read 1
and go to q3, from q3, read 0 and go to q1, from q1, read 1 and go to q0, State
q0 is a final state.

Let consider the DFA ={a,b}, K={ q0 },q0 in K is a initial state, final state is q0.
Empty string is also accepted by this machine. If
initial state is a final state the empty string will
be accepted by the machine. Set of string
starting with a’s and b’s accepted by this
machine.
Languages L(m) = { x/x  * }

Let consider the DFA ={a,b}, K={q0,q1,D}, q0 in K is a initial state, final state
is q0.
Empty string is
a b also accepted
 * q0 q1 D by this
q1 D q0 machine. If
D D D initial state is a
final state the empty string will be accepted by
the machine. Sequences of ab’s accepted by
this machine. At least one ab’s will be
accepted. In the above fig. and table D is dead state. Start from q0, read a and
go to q1, from q1, read b and go to q0, same manner the machine will
accepted the string ababab. State q0 is a final state. The string starting with b

4|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
and ending with a will not accepted by the machine. Languages of the
machine. L(m) = { (ab)n / n >=0 }.
Consider the finite state machine whose ={a,b}, K={q0,q1},q0 in K is a initial
state, final state is q1.
A b Empty string will
 q0 q1 q1 not be accepted
* q1 q1 q1 by the machine.
Any string
starting with a’s and b’s will be accepted by
the machine. Languages of the machine.
L(m) = { x/x  + }.

Consider the finite state machine whose ={ a,b }, K={q0,q1,q2},q0 in K is a

initial state, final state is q0.
Any string
a b starting with
 * q0 q1 q1 a’s and b’s
q1 q2 q2 will be
q2 q0 q0 accepted by
the machine. But string length should
divisible by 3. Language of the machine is
L(m) = { x /x  *,|x| = 3K }. K is a
integer.
Consider the DFA whose ={ A,B,…,Z,0,1…,9 }, K={ q0,q1,q2,q3,q4,q5,q6 },q0
in K is a initial state, F = { q1,q2,q3,q4,q5,q6 }. Fortran Identifier maximum
length is 6.
Any type of
A-Z 0-9 string starting
 q0 q1 Ø with A-Z
* q1 q2 q2 followed by A-Z
* q2 q3 q3 or 0-9 and
* q3 q4 q4 string length
* q4 q5 q5 should be 1 to 6
* q5 q6 q6 character.
Languages L(m) = { x /x  A-Z and x  A-Z or 0-9,|x| <=6 }.

Consider the DFA whose ={ A,B,…,Z,0,1…,9 }, K={ q0,q1,D },q0 in K is a

initial state, F = { q1 }.

5|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata

Non Deterministic Finite State Automata.

A Non Deterministic Finite automaton (NFA) can be represented by a 5-Tuple
M=(K, , δ, q0,F) where:
K is a non-empty set of states;
 is a non-empty set of an alphabet or symbols;
q0 in K is the starting state;
δ is a mapping from K *  into finite subsets of K.
transition function δ : K *   2K.
F  K is the set of accepting (final) states.
Extend δ to δ1 : K *  *  2K.
δ1 (q,) = q for all q in K
Q is a subset of K
δ(Q, a) = U δ (q, a)
qK
δ1(q, xa) = { p/p is in δ(Q, x) where Q = δ1(q, a) }
L(m) set of stings accepted.
T(m) = {x/x  * , δ (q0, x) contains a state from F}

Consider the NFA whose ={a,b}, K={ q0,q1,q2 },q0 in K is a initial state, final
state is q2 transition function δ is given in the table. To check whether the
given string is aaabb accepted by the machine or not.
Initial state q0. Two choose are
there reading a from q0 either
it’s go to q0 or q1. Similarly
Two choose are there reading b
from q1 either it’s go to q1 or
q2. final state is q2. The string
sequence of a’s followed by
sequence of b’s will be
accepted by the machine. The
string staring with b and
ending a are not accepted by
the machine. The state
sequence is q0 q0q0 q1 
q1  q2 for the input aaabb.
a b The initial state q0. Reading a from q0 and go to q0,
 q0 q0,q1 Ø again a is reading from q0 and go to q0, again a is
q1 Ø q1,q2 reading from q0 and go to q1, again b reading from
* q2 Ø Ø q1 and go to q1 and finally b reading from q1 and
go to q2,

Consider, for example, the

nondeterministic automaton

6|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
whose transition diagram is given below.
The input string is 00101. Initial state q0. The final state is q2. Transition
graph is given beside. Reading 0 from q0 and go to q0, again 0 is reading from
q0 and go to q0, again 1 is reading from q0 and go to q0, again 0 is reading from
q0 and go to q1 and finally 1 is
reading from q1 and go to q2, Input
string is accepted by this machine.
The state sequence diagram is given
below and state table also given
beside for the input.

The Equivalence of DFA and NFA

Let M=(K, , δ, q0,F) be a NFA an Equivalent DFA. M1 = (K1, , δ1, q01,F1)
Is constructed as follows K1 = 2K.
q01 = [q0] is a initial state.
F1 is the set of all subset of K containing an element of F
δ1([qo,q1,q2,….,qi], a) = δ([qo,q1,q2,….,qi], a)
= δ(qo, a) U δ(q1, a) U δ(q2, a) U……. U δ(qi, a)

Any string is accepted by NFA can be accepted by a DFA. Method is called as

subset.

Consider the NFA whose ={a,b}, K={ q0,q1,q2 },q0 in K is a initial state, final
state is q2 transition function δ is given in the table. To check whether the
given string is aaabb accepted by
a b
 q0 {q0,q1} {Ø}
q1 {Ø} {q1,q2}
* q2 {Ø} {Ø}
the machine or not.
NFA State Table
a b
[q0] [q0,q1] [Ø]
[q0,q1] [q0,q1] [q1,q2]
* [q1,q2] [Ø] [q1,q2]
[Ø] [Ø] [Ø] NFA Equivalent DFA State table
NFA Transition Diagram and state sequence.

7|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
Language of the machine L(m) = { am,
bn / n,m >=1}. The state diagram is
given beside . Initial state q0.
Reading a from q0 and go to [q0,q1],
again reading a from [q0,q1] and go
to [q0,q1], again reading a from
[q0,q1] and go to [q0,q1], and reading
b from [q0,q1] and go to [q1,q2],
again reading b from [q1,q2], and go
to [q1,q2]. That is a final state. The
string sequence of a’s followed by sequence of b’s will be accepted by the
machine. The string staring with b and ending a are not accepted by the
machine. The state sequence is q0 [q0,q1] [q0,q1] [q0,q1]  [q1,q2] 
[q1,q2] for the input aaabb.

Consider the set of strings over  = {0,1} which ending with either 00 or 11.
0 1
 q0 {q0,q1} {q0,q3}
q1 {q2} {Ø}
* q2 {Ø} {Ø}
q3 {Ø} {q4}
* q4 {Ø} {Ø}
NFA State Table
0 1
[q0 ] [q0,q1] [q0,q3]
[q0,q1] [q0,q1,q2] [q0,q3]
[q0,q3] [q0,q1] [q0,q3,q4]
*[q0,q1,q2] [q0,q1,q2] [q0,q3]
*[q0,q3,q4] [q0,q1] [q0,q3,q4]
NFA Equivalent DFA State table DFA State Diagram

Initial state is [q0 ]. The given input string is 10100. Reading 1 from q0 and
go to [q0,q1], again reading 0 from [q0,q1] and go to [q0,q1,q2], again reading 1
from [q0,q1,q2] and go to [q0,q3], again reading 0 from [q0,q3] and go to [q0,q1]
and finally reading 0 from [q0,q1] and go to [q0,q1,q2]. It is a final state. So
given string is accepted by machine.

Minimization of Finite Automata

Consider a DFA over . Two states are Equivalent iff for any string x in *.
δ(p, x) and δ(q, x) are both is final state or both not in final state.

If P and Q are distinguishable, if a string x / δ(p, x)  F. and if a string x /

δ(Q, x)  F. one of them may be in Final state and another may not be in final
state. X is called the distinguishable string sequence.
8|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata

If P and Q are two states, p reads a and go to r, similarly q reads a and go to s

r = δ(p, x) and s = δ(q, x). if p and q are Equivalent, means automatically r
and s are equivalent. r and s are both is final state or both not in final state.

If r and q are distinguishable, if a string a / δ(p, a)  F. and if a string a /

δ(Q, a)  F. one of them may be in Final state and another may not be in final
state. a is called the distinguishable string sequence. Automatically, P and Q
will be a distinguishable.

Consider ={ a, b } construct a machine at least one a will be accepted.

These two automata will be equivalent
machine. Both will be accepted same
type of string. Atleast one a will be
accepted by this machine. First machine
q1 and q2 states are Equivalent. Both q1
and q2 will be final state F.
So we can merge the q1 and q2. First
machine is not a minimization
automata. But second one is
minimization automata. In second
machine reduced number of state.

Consider ={ 0, 1 } From the given automata construct a minimization

automata.
There are six states available in this
machine. Take all the states make a partition
further and further until can’t make a
partition. Out of six three will be final state
q3,q4,q5 make it one group rest of them
(q0,q1,q6) make it another group. Sequence
of zeros followed by 1 and followed by zeros
will be accepted. One alone also
accepted. This is not a
minimization automata. One
successor of q0, q1 is final
state. But one successor of q6
is not a final state. So q0 and
q1 make it one partition and q6
make it another partition. Zero
successor of Q3,q4,q5 is q5
only and one successor of
Q3,q4,q5 is q6 only. So we
can’t make partition.

9|Page
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
A DFA with output.
Serial Adder.
Input = {00,01,10,11}
Output = {0,1}
Example. 100101
101110
1010011

10 01 11 01 00 11 00
q0 q0 q0 q1 q1 q0q1q0
1 1 0 0 1 0 1
sInitial state is q0. Input is pair of binary numbers and output is either 0 or 1.
Start from q0, read 10 and output is 1, again go to q0, from q0, read 01 and
output is 1, again go to q0, from q0, read 11 and output is 0, again go to q1,
from q1, read 01 and output is 0, again go to q1, from q1, read 00 and output
is 1, again go to q0, from q0, read 11 and output is 0, again go to q1, from q1,
read 00 and output is 1, again go to q0. State q0 is a no carry state and q1 is a
carry state.
A FSA with output M=(K,,Δ,δ,,q0) where
K is a finite set of states,
 is a finite set of input symbols,
Δ is a finite set of output symbols,
δ is transition function K *   K,
 is a output function,
q0 in K is a initial state.
There are two type of machines are available Moore Machine and Mealy
Machine. An Automaton in which the output depends on the states of the
machine is called a Moore Machine. An Automaton in which the output
depends on the input at any instant of time is called a Mealy Machine.

Consider ={0,1} and output alphabets Δ = { y, n} construct Mealy Machine

any string ending with 2 zero’s or ending with 2 ones.
Mealy Machine  : K *   Δ
Input string is 001011. Initial state is q0,
reading 0 from q0 and goes to q1, output is n,
reading 0 from q1 and goes to q1, output is y,
reading 1 from q1 and goes to q2, output is n,
reading 0 from q2 and goes to q1, output is n,
reading 1 from q1 and goes to q2, output is n,
reading 1 from q2 and goes to q2, output is y.
Input and output table is given below.
Input 0 O 1 0 1 1
Output N y n n N y
Final output is y, so string ending with 2 ones
was accepted by the machine. The given input size is six and output size is
also six.

10 | P a g e
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
Consider ={0,1} and output alphabets Δ = { 0, 1, 2, 3, 4} construct Moore
Machine with string 10001. Moore Machine  : K  Δ.
The input string is 100. It’s start from
q0, reading 1 from q0 and goes to q1,
output is 1, reading 0 from q1 and
goes to q2, output is 2, reading 0 from
q2 and goes to q4. Final output is 4.
Input string binary value is 100 and
equivalent decimal value is 4.
1 0 0 N
q0  q1  q2  Q4 N+1
0 1 2 4 N+1
The given input size is 3 (N) but state
sequence size and output size are 4.
That is N+1. Moore Machine are
depends only on states. Now we will
see the input string 10001. It’s start from q0, reading 1 from q0 and goes to q1,
output is 1, reading 0 from q1 and goes to q2,output is 2, reading 0 from q2
and goes to q4, output is 4, reading 0 from q4 and goes to q3, output is 3,
reading 1 from q3 and goes to q2. Final output is 2. The input string binary
value is 10001 and equivalent decimal value 17. Input value is divide by 5
and get remainder is 2. That is the final output of given input.

Construct Moore Machine equivalent Mealy Machine

Consider ={0,1} and output alphabets Δ = { 0, 1, 2, 3, 4} construct Moore
Machine equivalent Mealy Machine with string 10011.
The input string 10001. It’s start from q0, reading 1 from q0 and goes to q1,
output is 1, reading 0 from q1 and goes to q2,output is 2, reading 0 from q2
and goes to q4, output is 4, reading 0 from q4 and goes to q4, output is 4,
reading 1 from q4 and goes to q4. Final output is 4. The input string binary
value is 10011 and equivalent decimal value 19. Input value is divide by 5
and get remainder is 4. That is the final output of given input.

Input 1 O 0 1 1
output 1 2 4 4 4
The given input size is 5 (N) and output
size is also 5 (N).

Construct Mealy Machine equivalent Moore Machine

Mealy Machine M=(K, , Δ, δ, , q0)
Moore Machine M=(K * Δ, , Δ, δ1, 1, [q0, b] )
δ1([q, b], a) = [δ (q, a),  (q0, a)]
11 | P a g e
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata
1 ( [q0, b] ) = b

Input string is 100. Initial state is p0,n], reading 1 from [p0,n] and goes to
[p2,n], output is n, reading 0 from [p2,n] and goes to [p1,n], output is n, reading
0 from [p1,n] and goes to [p1,y], output is y. Size (N) of input is equal to size (N)
of the output. Input and output table is given below.
Input 1 O 0
output N N Y

12 | P a g e
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata

Assignment questions
1. Find all subsets of A={1,2,3,4,5,6} 2.Marks
2. 1. Let A = {a, b, c} , B = {1, 2, 3, 4} .and C= {b,c,5} Then
write all A*B*C (2 Marks)

3. NDFA state table is given to find

A b
a. NDFA state diagram ( 1 Mark)
 q0 q0, q1 q2
b. DFA state diagram ( 1 Mark)
q1 q0 q1
c. DFA state Table ( 1 Mark) Ø
d. DFA state sequence ( 1 Mark) * q0, q1
e. NDFA state sequence ( 1 Mark) q2

3. Consider ={0,1} and output alphabets Δ = { 0, 1, 2, 3, 4, 5, 6 }

i. Construct Moore Machine with string 10101101. (1.5

mark)
ii. Construct Mealy Machine equivalent Moore Machine. (2
mark)
iii. Construct Mealy Machine equivalent Moore Machine with
string 001101. (1.5 mark)

13 | P a g e
Formal Languages and Automata Theory. ( Comp403 )
Chapter 2 The Theory of Automata

1
0 0
Q1,1
Q0,0

Q3,3
1
0 1

1
Q2,2 Q5,5

0
1

Q4,4 1
Q6,6

4. Consider = {a,b} and output alphabets Δ = { 1, 2, 3, 4 }

construct Moore Machine any string start with ‘a’ or ‘b’ and
ending with two ‘a’s or two ‘b’s.(2 mark)

Note Total marks 15, Neatness have a value

14 | P a g e