

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 3
Reading
Material
Chapter
4
Introduction
to Computer Theory
Summary
RE,
Recursive definition of RE, defining
languages by RE, { x}*, {
x}+, {a+b}*, Language of strings
having
exactly
one a, Language of strings of even
length, Language of strings of odd length, RE defines
unique
language
(as Remark), Language of strings having
at least one a, Language of strings
having at least one a
and
one b,
Language of strings starting with aa and
ending in bb, Language of
strings starting with and
ending in
different
letters.
Regular
Expression
As
discussed earlier that a* generates Λ, a, aa, aaa, ...
and a+ generates a, aa,
aaa, aaaa, ..., so the
language L1
= {Λ, a,
aa, aaa, ...} and L2 = {a, aa, aaa,
aaaa, ...} can simply be
expressed by a*
and a+, respectively.
a* and a+
are called
the regular expressions (RE)
for L1 and L2 respectively.
a+, aa* and a*a generate L2.
Note
Recursive
definition of Regular
Expression(RE)
Step 1:
Every letter of Σ including Λ is a
regular expression.
Step 2:
If r1 and r2 are regular expressions
then
(r1)
r1 r2
r1 + r2 and
r1*
are
also regular
expressions.
Step 3:
Nothing else is a regular
expression.
Method 3
(Regular Expressions)
Consider
the language L={Λ, x, xx,
xxx,...} of strings, defined
over Σ = {x}.
We can
write this language as the
Kleene star closure of alphabet Σ or
L=Σ*={x}* .
This
language can also be
expressed by the regular
expression x*.
Similarly
the language L={x, xx,
xxx,...}, defined over Σ =
{x}, can be expressed by the
regular expression x+.
Now
consider another language L,
consisting of all possible
strings, defined over Σ =
{a, b}. This language
can
also be
expressed by the regular
expression (a + b)*.
Now
consider another language L, of
strings having exactly one
a, defined over Σ = {a, b},
then it's regular
expression
may be b*ab*.
Now
consider another language L, of
even length, defined over Σ =
{a, b}, then it's
regular expression may
be
((a+b)(a+b))*.
Now
consider another language L, of
odd length, defined over Σ =
{a, b}, then it's
regular expression may
be
(a+b)((a+b)(a+b))*
or ((a+b)(a+b))*(a+b).
Remark
It may be
noted that a language may be
expressed by more than one
regular expression, while
given a regular
expression
there exist a unique
language generated by that
regular expression.
Example
Consider
the language, defined
over
Σ = {a , b} of
words having at least one a,
may be expressed by a regular
expression (a+b)*a(a+b)*.
Consider
the language, defined over Σ
= {a, b} of words having at
least one a and one b,
may be expressed by a
regular
expression (a+b)*a(a+b)*b(a+b)*+
(a+b)*b(a+b)*a(a+b)*.
Consider
the language, defined over Σ
={a, b}, of words starting
with double a and ending in double b
then its
regular
expression may be
aa(a+b)*bb
Consider
the language, defined over Σ
={a, b} of words starting
with a and ending in b
OR
starting
with b and ending in a, then
its regular expression may
be a(a+b)*b+b(a+b)*a
11
Table of Contents:

