

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 7
Reading
Material
Chapter 5,
6
Introduction
to Computer Theory
Summary
FA corresponding to
finite languages(using both methods),
Transition graphs.
FA
corresponding to finite languages
Example
Consider
the language
L = {Λ, b,
ab, bb}, defined
over Σ ={a, b}, expressed by
Λ + b + ab + bb OR Λ + b (Λ + a + b).
The
language L may be accepted by
the FA as shown aside
a,b
y
a
a,b
a
b
4+
3
1±
b
b
5+
2+
It is to be
noted that the states x
and y are called
Dead
States, Waste Baskets or
Davey John Lockers, as
the
a,b
a
moment
one enters these states
there is no way to leave
it.
Note
x
It is to be
noted that to build an FA
accepting the language
having less number
a,b
of
strings, the tree structure
may also help in this regard,
which can be observed
in the
following transition diagram for
the
4
Language
L, discussed in the above
example
a
3
a,b
b
a
a,b
5+
a,b
1±
8
a,b
6
b
a
a,b
2+
a,b
b
7+
x
a,b
b
a
a
Example
a
a
b
3+
b
4
2
Consider
the language
1
5+
L = {aa,
bab, aabb, bbba}, defined
over Σ ={a, b},
b
expressed
by aa + bab + aabb +
bbba
b
b
a
6
9+
8
7
OR aa (Λ +
bb) + b (ab + bba)
a
The
above language may be
accepted by the FA
a
as shown
aside
b
10
a,b
a
b
a,b
y
11+
a,b
20
Theory of
Automata
(CS402)
Example
Consider
the language L = {w belongs to
{a,b}*: length(w) ≥2 and w
neither ends in aa nor
bb}.
The
language L may be expressed by
the regular expression
(a+b)*(ab+ba)
This
language may be accepted by
the following FA
21
Theory of
Automata
(CS402)
a
b
4+
2
a
b
a
1
a
b
b
b
a
5+
3
Note
It is to be
noted that building an FA corresponding
to the language L, discussed in
the above example, seems
to
be quite
difficult, but the same can
be done using tree structure along
with the technique discussed
in the book
Introduction
to Languages and Theory of
Computation, by J. C.
Martin
so that
the strings ending in aa,
ab, ba and bb should end in
the states labeled as aa,
ab, ba and bb,
respectively;
a
as shown in
the following FA
aa
a
a
b
b
a
a
ab
Λ
a
b
ba
b
a
b
a
b
b
b
bb
Example
Consider
the language FA corresponding to r1+r2 can be determined
as
L = {w
belongs to {a,b}*: w
does not end in aa}.
The
language L may be expressed by
the regular expression Λ + a + b +
(a+b)*(ab+ba+bb). This
language may
a
be
accepted by the following
FA
aa
a
a
b
b
a
a
ab
Λ
a
b
ba
b
a
b
b
a
b
b
Method 5
(Transition Graph)
bb
Definition:
A
Transition graph (TG), is a collection of
the followings
Finite
number of states, at least one of
which is start state and
some (maybe none) final
states.
Finite
set of input letters (Σ)
from which input strings
are formed.
Finite
set of transitions that show
how to go from one state to
another based on reading specified substrings
of
input
letters, possibly even the
null string (Λ).
22
Table of Contents:

