

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 9
Reading
Material
Chapter
6
Introduction
to Computer Theory
Summary
TGs
accepting the languages:
containing aaa or bbb,
beginning and ending in
different letters,
beginning
and ending in same letters,
EVENEVEN, a's occur in even
clumps and ends in
three or
more b's, example showing
different paths traced by one
string, Definition of
GTG
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 TG
a
2
4
a
a
a,b
a,b
1
6+
b
b
b
3
5
OR
OR
Example
Consider
the language L of strings,
defined over Σ = {a, b},
beginning
and ending in different
letters.
The
language L may be expressed by RE
a(a + b)*b + b(a +
b)*a
The
language L may be accepted by
the following TG
25
Theory of
Automata
(CS402)
Example
Consider
the Language L of strings of length
two or more, defined
over Σ = {a, b}, beginning
with and
ending in
same letters.
The
language L may be expressed by
the following regular
expression a(a + b)*a + b(a +
b)*b
This
language may be accepted by
the following TG
Example
Consider
the EVENEVEN
language,
defined over Σ = {a, b}. As
discussed earlier that EVENEVEN
language
can be expressed by a regular
expression (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
The
language EVENEVEN
may be
accepted by the following
TG
Example
Consider
the language L, defined over
Σ={a, b}, in which a's
occur only in even clumps
and that ends in
three or
more b's. The
language L can be expressed by
its regular expression
(aa)*b(b*+(aa(aa)*b)*) bb
OR
(aa)*b(b*+( (aa)+b)*) bb.
The
language L may be accepted by
the following TG
Example
Consider
the following TG
26
Theory of
Automata
(CS402)
Consider
the string abbbabbbabba. It may be
observed that the above string
traces the following three
paths,
(using
the states)
(a)(b)
(b) (b) (ab) (bb)
(a) (bb) (a)
()(4)(4)(+)(+)(3)(2)(2)(1)(+)
(a)(b)
((b)(b)) (ab) (bb) (a)
(bb) (a)
()(4)(+)(+)(+)(3)(2)(2)(1)(+)
(a)((b)
(b)) (b) (ab) (bb)
(a) (bb) (a)
()
(4)(4)(4)(+) (3)(2)(2)(1)(+)
Which
shows that all these
paths are successful, (i.e.
the
path starting from an initial
state and ending in a
final
state).
Hence
the string abbbabbbabba is accepted by
the given TG.
Generalized
Transition Graphs
A
generalized transition graph (GTG) is a collection of
three things
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.
Directed
edges connecting some pair of
states labeled with regular
expression.
It may be
noted that in GTG, the
labels of transition edges are
corresponding regular expressions
27
Table of Contents:

