

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 4
Reading
Material
Chapter 4,
5
Introduction
to Computer Theory
Summary
Regular
expression of EVENEVEN language,
Difference between a* + b* and
(a+b)*, Equivalent
regular
expressions;
sum, product and closure of
regular expressions; regular
languages, finite languages
are regular,
introduction
to finite automaton, definition of
FA, transition table, transition
diagram
An
important example
The
Language EVENEVEN
Language of
strings, defined over Σ={a,
b} having even number of a's
and even number of b's.
i.e.
EVENEVEN
= {Λ, aa, bb,
aaaa,aabb,abab, abba, baab,
baba, bbaa, bbbb,...}, its
regular expression can
be
written
as (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
Note
It is
important to be clear about
the difference of the
following regular
expressions
r1 = a*+b*
r2 = (a+b)*
Here r1 does not generate any string
of concatenation of a and b, while
r2 generates such
strings.
Equivalent
Regular Expressions
Definition
Two
regular expressions are said
to be equivalent if they generate
the same language.
Example
Consider
the following regular
expressions
r1 = (a + b)* (aa +
bb)
r2 = (a + b)*aa + ( a + b)*bb
then both regular expressions
define the language of
strings ending in aa or
bb.
Note
If r1 = (aa + bb) and r2 = ( a + b) then
r1+r2 = (aa + bb) + (a +
b)
r1r2 = (aa + bb) (a +
b)
= (aaa +
aab + bba + bbb)
(r1)* = (aa + bb)*
Regular
Languages
Definition
The
language generated by any
regular expression is called a regular
language.
It is to be
noted that if r1, r2 are regular expressions,
corresponding to the languages L1 and L2
then
the languages generated by r1+ r2, r1r2( or r2r1)
and r1*( or r2*)
are also regular
languages.
Note
It is to be
noted that if L1 and
L2 are expressed by
r1and r2, respectively then the
language expressed by
r1+ r2, is the language
L1 + L2 or L1 « L2
r1r2, , is the
language L1L2, of strings obtained by prefixing
every string of L1
with
every string of L2
r1*, is the language L1*, of strings obtained by concatenating
the strings of L, including
the null string.
Example
If r1 = (aa+bb) and r2 =
(a+b) then the language of
strings generated by r1+r2, is also a
regular language,
expressed
by (aa+bb) + (a+b)
If r1 = (aa+bb) and r2 =
(a+b) then the language of
strings generated by r1r2, is also a
regular language,
expressed
by
(aa+bb)(a+b)
If r = (aa+bb)
then the language of strings
generated by r*, is also a
regular language, expressed by
(aa+bb)*
12
Theory of
Automata
(CS402)
All
finite languages are
regular
Example
Consider
the language L, defined over
Σ = {a,b}, of strings of length 2, starting
with a, then
L = {aa,
ab}, may be expressed by the
regular expression aa+ab.
Hence L, by definition, is a regular
language.
Note
It may be
noted that if a language
contains even thousand words,
its RE may be expressed, placing ` + '
between
all
the words.
Here the
special structure of RE is not
important.
Consider
the language L = {aaa, aab,
aba, abb, baa, bab,
bba, bbb}, that may be
expressed by a RE
aaa+aab+aba+abb+baa+bab+bba+bbb,
which is equivalent to
(a+b)(a+b)(a+b).
Introduction
to Finite Automaton
Consider
the following game board
that contains 64
boxes
There
are some pieces of paper.
Some are of white colour
while others are of black
colour. The number of
pieces of
paper are 64 or less. The
possible arrangements under which
these pieces of paper can be
placed in the
boxes,
are finite. To start the
game, one of the
arrangements is supposed to be initial
arrangement. There is a
pair of
dice that can generate
the numbers 2,3,4,...12 .
For each number generated, a unique
arrangement is
associated
among the possible
arrangements.
It shows
that the total number of transition rules of
arrangement are finite. One
and more arrangements can
be
supposed
to be the winning arrangement. It
can be observed that the
winning of the game depends
on the
sequence
in which the numbers are
generated. This structure of
game can be considered to be a
finite automaton.
Method 4
(Finite Automaton)
Definition
A Finite
automaton (FA), is a collection of the
followings
Finite
number of states, having one
initial and some (maybe
none) final states.
Finite
set of input letters (Σ)
from which input strings
are formed.
Finite
set of transitions i.e. for
each state and for
each input letter there is a transition
showing how to move
from
one state to another.
Example
Σ =
{a,b}
States:
x, y, z where x is an initial state and z
is final state.
Transitions:
At state
x reading a, go to state z
At state
x reading b, go to state y
At state
y reading a, b go to state y
At state
z reading a, b go to state z
These
transitions can be expressed by
the following table called transition
table
13
Theory of
Automata
(CS402)
Old
States
New
States
Reading
a
Reading
b
x
z
y
y
y
y
z+
z
z
Note
It may be
noted that the information
of an FA, given in the previous
table, can also be depicted
by the following
diagram, called
the transition
diagram, of the
given FA
a,b
y
b
x
a,b
a
Z+
Remark
The
above transition diagram is an FA accepting
the language of strings,
defined over Σ = {a, b},
starting
with
a. It may
be noted that this language
may be expressed by the
regular expression a(a +
b)*
14
Table of Contents:

