

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 30
Reading
Material
Introduction
to Computer Theory
Chapter
11,12
Summary
Deciding
whether two languages are
equivalent or not, example, deciding
whether an FA accept any string or
not,
method 3, examples, finiteness of a
language
Example
Consider
two languages L1 and
L2, expressed by the
REs r1=a* and
r2=Y+aa*
respectively. To determine
whether L1 and L2
are
equivalent, let the corresponding FAs
be
a
a,b
a
r3+
a
b
FA1 p1±
p2
FA2 r1±
b
a,b
b
r2
As
discussed earlier, the FA corresponding to
the language (L1ČL2c)«(L1cČL2)
helps in this regard i.e.
if
this
FA
accepts any word then L1
and L2 are not equivalent other
wise L1 and L2 are
equivalent.
a
Following
are the FAs corresponding to
L1c and L2c
a,b
a
s3
a
FA2c
b
FA1c
q1
s1
q2+
b
a,b
b
s2+
FAs
corresponding to (FA1c « FA2)c and (FA2c « FA1)c may be as follows
a
a
(FA2c«FA1)c
(FA1c«FA2)c
q1 , r3
p1 , s3
a
a
q1 , r1


b
b
a,b
a,b
p1 , s1
b
b
q2 , r2
p2 , s2
Both
the FAs have no final
state, so these FAs accept
nothing. This implies that
their union will not
also accept
c
any
string. Hence FA corresponding to the
language (L1ČL2 )«(L1cČL2) accepts nothing. Thus both
the
languages
are equivalent.
Example
Following
is an FA, for which it is required to
decide whether it accepts any string or
not? Using steps
discussed
in method
2, the following FA can be
checked whether it accepts any
word or not.
88
Theory of
Automata
(CS402)
1
b
b
b
a,b
a
a
2
3
a
b
b
4+
a
5
6
a
1
b
b
b
a
a,b
a
2
3
a
b
b
a
4+
5
6
a
1
b
b
a,b
a
2
3
a
b
b
4+
a
6
5
a
1
b
a,b
a
2
3
a
b
b
a
4+
5
6
89
Theory of
Automata
(CS402)
1
b
a
2
3
a
b
b
a
4+
5
6
As no
final state of the FA is
marked, so the given FA
accepts no word.
Method
3
If the FA
has N states, then test
the words of length less than N. If no
word is accepted by this FA,
then it will
accept no
word.
Note: It is to be
noted that all the
methods discussed above, to determine whether an FA
accepts certain word,
are
effective procedures.
Example:
To determine whether the following FA
accepts certain word, using method 3,
all the strings of
length
less
than 4 (i.e. less
than the number of states of
the FA) are sufficient to be
tested
2
a
a
a
a
b
1
4+
b
b
3
b
i.e.
Y, a, b,
aa, ab, ba, bb,
aaa, aab, aba, abb,
baa, bab, bba, bbb are
required to be tested.
It can be
observed that the strings
aa, baa, aaa are
accepted by this FA, hence
the language accepted by
this FA
is not
empty.
Example
Consider
the following FA. To determine whether
this FA accepts some word,
all the strings of length
less than
4 (i.e.
less
than the number of states of
this FA) are to be
tested
a,b
a
b
a,b
b
4+
2
3
1
a
It can be
observed that none of the
strings L, a, b,
aa, ab, ba, bb,
aaa, aab, aba, abb,
baa, bab, bba, bbb,
is
accepted
by this FA. Thus the given
FA cannot accept any
word.
Observation
To find
whether a regular expression defines an
infinite language or not?
The following possibilities
are
required
to be checked.
If a
regular expression contains *
then it may define an
infinite language, with the
exception Y* as Y* = Y e.g.
(Y+aY*)(Y*+Y)* defines
finite language. While (Y*+aY*)* (Y*+Y)* defines an
infinite language.
90
Theory of
Automata
(CS402)
There
are so many ways to decide
whether an FA accepts a finite language
or an infinite. Following is a
theorem
in this
regard
Theorem
Let F be
an FA having N states
If F
accepts a word w s.t. N length(w)
< 2N
then F
accepts infinite
language.
If F
accepts an infinite language
then there are some words w
s.t. N length(w)
< 2N
The
first part can be proved, using
the pumping lemma version
II.
Remark
There is
an effective procedure to decide whether an FA
accepts finite or infinite
language. For a machine
with
N number of
states, the total number of strings to be
tested, defined over an
alphabet of m letters, is mN
+mN+1
+ mN+2
+... +m2N1. After testing
all these strings on the
machine, if any is accepted
then the machine
accepts
infinite
language other wise not. e.g.
for
machine of three states and
alphabet of two letters, 2 3 +2 4 +2 5 =
56
strings
are to be tested.
91
Table of Contents:

