

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 10
Reading
Material
Chapter 6,
7
Introduction
to Computer Theory
Summary
Examples
of GTG accepting the
languages of strings: containing aa or
bb, beginning with and
ending in same
letters,
beginning with and ending in
different letters, containing aaa or
bbb,
Nondeterminism,
Kleene's theorem (part I, part
II, part III), proof of
Kleene's theorem part I
Example
Consider
the language L of strings,
defined over Σ = {a,b}, containing
double a
or double b. The
language L
can be
expressed by the following
regular expression (a+b)* (aa + bb) (a+b)*
The
language L may be accepted by
the following GTG.
Example
Consider
the Language L of strings, defined
over Σ = {a, b}, beginning
with and ending in same
letters.
The
language L may be expressed by
the following regular
expression (a+b)+ a(a + b)*a + b(a + b)*b.
This
language may be accepted by
the following GTG
Example
Example
Consider
the language L of strings
of, defined over Σ = {a,
b}, beginning
and ending in different
letters.
a(a +
b)*b + b(a + b)*a
The
language L may be expressed by
RE
The
language L may be accepted by
the following GTG
The
language L may be accepted by
the following GTG as
well
Example
Consider
the language L of strings,
defined over Σ = {a, b},
having
triple a or triple b. The
language L may be
expressed
by RE (a+b)*
(aaa +
bbb) (a+b)*
This
language may be accepted by
the following GTG
28
Theory of
Automata
(CS402)
Nondeterminism
TGs
and GTGs provide certain relaxations
i.e.
there
may exist more than one
path for a certain string or
there
may not
be any path for a certain string,
this property creates nondeterminism
and it
can also help in
differentiating
TGs or GTGs from FAs.
Hence an FA is also called a Deterministic
Finite Automaton (DFA).
Kleene's
Theorem
If a
language can be expressed
by
FA
or
TG
or
RE
then
it
can also be expressed by other
two as well.
It may be
noted that the theorem is
proved, proving the
following three parts
Kleene's
Theorem Part I
If a
language can be accepted by an FA
then it can be accepted by a TG as
well.
Kleene's
Theorem Part II
If a
language can be accepted by a TG
then it can be expressed by an RE as
well.
Kleene's
Theorem Part III
If a
language can be expressed by a RE
then it can be accepted by an FA as
well.
Proof(Kleene's
Theorem Part I)
Since
every FA can be considered to be a TG as
well, therefore there is nothing to
prove.
29
Table of Contents:

