

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 2
Reading
Material
Chapter
3
Introduction
to Computer Theory
Summary
Kleene
Star Closure, Plus operation, recursive
definition of languages, INTEGER,
EVEN, factorial,
PALINDROME,
{anbn},
languages of strings (i)
ending in a, (ii) beginning
and ending in same letters,
(iii)
containing aa or bb
(iv) containing exactly one
a
Kleene
Star Closure
Given Σ,
then the Kleene Star Closure of
the alphabet Σ, denoted by Σ*, is the collection of all
strings defined
over Σ,
including Λ.
It is to be
noted that Kleene Star Closure
can be defined over any
set of strings.
Examples
If Σ =
{x}
Then
Σ* = {Λ, x, xx, xxx,
xxxx, ....}
If Σ =
{0,1}
Then
Σ* = {Λ, 0, 1, 00,
01, 10, 11, ....}
If Σ =
{aaB, c}
Then
Σ* = {Λ, aaB, c,
aaBaaB, aaBc, caaB, cc,
....}
Note
Languages
generated by Kleene Star Closure of set
of strings, are infinite
languages. (By infinite
language, it is
supposed
that the language contains
infinite many words, each of
finite length).
PLUS
Operation (+)
Plus
Operation is same as Kleene Star Closure
except that it does not
generate Λ (null string),
automatically.
Example
If Σ =
{0,1}
Then
Σ+ = {0, 1, 00,
01, 10, 11, ....}
If Σ =
{aab, c}
Then
Σ+ = {aab, c, aabaab,
aabc, caab, cc, ....}
Remark
It is to be
noted that Kleene Star can
also be operated on any string
i.e.
a* can be considered to be all
possible
strings
defined over {a}, which
shows that a* generates Λ, a, aa, aaa,
...
It may
also be noted that a+ can be considered to be all
possible non empty strings defined
over {a}, which
shows
that a+ generates a, aa,
aaa, aaaa, ...
Recursive
definition of languages
The
following three steps are
used in recursive definition
Some
basic words are specified in the
language.
Rules
for constructing more words
are defined in the
language.
No
strings except those
constructed in above, are allowed to be
in the language.
Example
Defining
language of INTEGER
Step
1:
1 is in INTEGER.
Step
2:
If x is in
INTEGER
then x+1
and x1 are also in
INTEGER.
Step
3:
No
strings except those
constructed in above, are allowed to be
in INTEGER.
Example
9
Theory of
Automata
(CS402)
Defining
language of EVEN
Step
1:
2 is in EVEN.
Step
2:
If x is in
EVEN
then x+2
and x2 are also in
EVEN.
Step
3:
No
strings except those
constructed in above, are allowed to be
in EVEN.
Example
Defining
the language
factorial
Step
1:
As 0!=1,
so 1 is in factorial.
Step
2:
n!=n*(n1)!
is in factorial.
Step
3:
No
strings except those
constructed in above, are allowed to be
in factorial.
Defining
the language PALINDROME,
defined over Σ =
{a,b}
a and b
are in PALINDROME
Step
1:
if x is palindrome,
then s(x)Rev(s) and xx will
also be palindrome, where s belongs to
Σ*
Step
2:
Step
3:
No
strings except those
constructed in above, are allowed to be
in palindrome
Defining
the language {anbn }, n=1,2,3,... , of strings
defined over Σ={a,b}
ab is in {anbn}
Step
1:
if x is in
{anbn}, then
axb is in {anbn}
Step
2:
No
strings except those
constructed in above, are allowed to be
in {anbn}
Step
3:
Defining
the language L, of strings
ending in a , defined over
Σ={a,b}
Step
1:
a is in
L
if x is in L
then s(x) is also in L, where s
belongs to Σ*
Step
2:
Step
3:
No
strings except those
constructed in above, are allowed to be
in L
Defining
the language L, of strings
beginning and ending in same
letters , defined over Σ={a,
b}
Step
1:
a and b
are in L
(a)s(a)
and (b)s(b) are also in
L,
where s
belongs to Σ*
Step
2:
Step
3:
No
strings except those
constructed in above, are allowed to be
in L
Defining
the language L, of strings
containing aa or bb , defined
over
Σ={a,
b}
Step
1:
aa and bb
are in L
s(aa)s
and s(bb)s are also in
L,
where s
belongs to Σ*
Step
2:
No
strings except those
constructed in above, are allowed to be
in L
Step
3:
Defining
the language L, of strings
containing exactly one a, defined
over
Σ={a,
b}
Step
1:
a is in
L
s(aa)s is
also in L, where s
belongs to b*
Step
2:
Step
3:
No
strings except those
constructed in above, are allowed to be
in L
10
Table of Contents:

