

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 29
Reading
Material
Introduction
to Computer Theory
Chapter
10, 11
Summary
Example
of prefixes of a language, Theorem: pref(Q in R) is
regular, proof, example, Decidablity,
deciding
whether
two languages are regular or
not ?, method 1, example, method 2,
example
Example
Let Q
and R be expressed by ab*a
and (ba)* respectively i.e.
Q={aa,aba,abba, ...} and
R={Y, ba,
baba, bababa, ...}. aba is
the only word in Q which
can make a word in R,
because the words in R
don't
contain the double letter. Thus pref(Q in R) =
{b, bab, babab, ...}, which
can be expressed by b(ab)*
or
(ba)*b.
Remark
It may be
noted that the language R
cannot be factorized with the help of
language Pref(Q in R) i.e.
Pref(Q in
R)Q is not equal to R in general.
However the following
theorem shows that the
language pref(Q in R)
is
regular if R is regular, no matter whether
the language Q is regular or
not.
Theorem
Statement
If R is
regular language and Q is
any language (regular/ nonregular),
then Pref(Q in R) is regular.
Proof
Since R
is regular there exists an FA
that accepts this language.
Choose a state, say, s of
this FA and see
whether
this
state can trace out a
path ending up in a final state
while running words from Q.
If this state traces out a
path
ending up in a
final state for any of
the words of Q, mark this
state with certain colour.
Repeat
this process for remaining
states of the machine. If at
least one state of this
machine is marked then it
can
be shown
that the language Pref(Q in
R) is nonempty. Now build a new FA
with some marked states
by
considering
the initial state that of
original FA and final states
which are marked. The
machine, thus obtained
accepts
exactly the language Pref(Q
in R). Thus Pref(Q in R) being accepted
by an FA is regular.
Remark
There is
a problem in deciding whether a state of
FA should be marked or not when the
language Q is infinite.
This
proof just gives non constructive
method to prove that Pref(Q
in R) is regular.
Example
Consider
the languages Q={aba, abb}
and R = {w OE {a,b}*:
length(w) ≥ 2, w ends
in either ab or ba}, where
R
may be
accepted by the following
FA
a
b
4+
2
a
b
a
1
a
b
b
b
a
5+
3
It can be
observed that the string aba
from Q make the words of R
and hence the states
1,2,3,4 and 5 can
easily
be
marked. Thus from the given
FA, making the states 1, 2
and 3 to be final as well,
the resulting FA will
accept
the
language pref(Q in R).
Moreover it can be observed that
pref(Q in R) can be expressed by
(a+b)*, which is
the RE
corresponding to the resulting FA as
well.
Decidability
Effectively
solvable problem
84
Theory of
Automata
(CS402)
A problem
is said to be effectively solvable if
there exists an algorithm
that provides the solution in
finite
number of
steps e.g.
finding
solution for quadratic equation is effectively
solvable problem, because
the
quadratic
formula provides an algorithm
that determines the solution in a
finite number of arithmetic
operations,
(four
multiplications, two subtractions, one
square root and one
division).
Decision
procedure
If an
effectively solvable problem
has answer in yes or no,
then this solution is
called
decision
procedure.
Decidable
problem
A problem
that has decision procedure is called
decidable problem e.g.
the
following problems
The
two regular expressions
define the same
language.
The
two FAs are
equivalent.
Determining
whether the two languages
are equivalent or not
?
If L1 and L2
are
two regular languages, then
they can be expressed by
FAs. As shown earlier, L1c , L2c , L1Č L2 ,
L1« L2 are regular languages
and the methods have already
been developed to build
their corresponding FAs. It
can be
observed that (L1Č L2c ) « ( L1c Č L2 ) is regular language that
accepts the words which are
in L1 but not
in L2 or else in L2 but
not in L1
. The
corresponding FA cannot accept any word
which is in both L1
and L2 i.e. if
L1 and L2
are
equivalent, then this FA
accepts not even null string.
Following are the methods
that determine
whether a
given FA accepts any
words
Method
1
For FA
corresponding to (L1ČL2c ) « ( L1cČ L2 ), the regular expression
can be determined that defines
the
language
accepted by this FA. From
that regular expression one
can determine whether this regular
expression
defines
any word or not? Following
are the steps to be
followed
Remove
all *s from the regular
expression.
Separate
the right part of + and the
plus itself.
The
regular expression thus obtained if
contains atleast one word
then the language is not
empty otherwise the
language
is empty.
Example
For
(a+Y)(a*b+ba*)(a*+Y)* to be
the regular expression of (L1ČL2c ) « ( L1cČ L2 ), it is required to
find
whether
this language accepts any
string or not?
After
removing all *s the RE will
be (a+Y)(ab+ba)(a+Y)
After
separating the right part
from + and the + itself
the RE will be aaba
As this
language contains atleast
aaba as its word, so this
language is not
empty.
Remark
Sometimes,
while determining regular
expression for a given FA,
it is impossible to write its regular
expression
a
b
e.g.
a
FA1
2
1
b
a,b
a,b
FA2
1
2
a,b
a,b
a,b
3+
FA3
2
1
Method
2
To
examine whether a certain FA accepts
any words, it is required to seek
the paths from initial to
final state.
But in large FA
with thousnads of states and
millions of directed edges, without an
effective procedure it is
impossible
to find a path from initial
to final state. Following
are the steps of this
procedure
85
Theory of
Automata
(CS402)
Mark
the initial state.
For
every marked state follow
each edge that leads
out of it and marked the
concatenating states and
delete these
edges.
Repeat
step 2 until no new state is
marked.
If any of
the final states are
marked then the FA accepts
some word, otherwise
not.
Example
Suppose
it is required to test the
FA, which is given below,
whether it accepts any string or not?
Applying
method 2
as
b
a
a
a
b
b
6+
4
5
3
a
b
a,b
a
b
1
2
b
a
a
a
b
b
6+
4
3
5
a
b
a
a,b
b
1
2
b
a
a
a
b
b
4
5
6+
3
a
b
a,b
1
2
b
a
a
b
a
b
6+
3
4
5
a
b
b
a
a
b
4
6+
5
3
a
b
2
1
1
2
86
Theory of
Automata
(CS402)
b
a
b
6+
4
5
3
a
1
2
This FA
accepts no string as after applying
method 2, the final state is
not marked.
87
Table of Contents:

