ZeePedia buy college essays online


Theory of Automata

<<< Previous finiteness of a language Next >>>
 
img
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
img
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
img
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
img
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 +... +m2N-1. 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