CS 390 Solutions to Unit 7 Exercises
p. 114
3.11 This is going to be proven by mathematical induction on n.
Basis Step: L0 =
{ 
}.
By the definition of regular language { }
is regular. Hence L0 is regular.
Inductive Step: Assume that Ln is regular. --- Induction Hypothesis
We are going to prove that Ln+1 is regular.
By the
recursive definition of Ln,
Ln+1 = LnL.
Since Ln and Lare regular by the
definition of regular language, their concatenation LnL is
regular. Hence Ln+1 is regular.
p.118
3.37 Let us first see an example of what the question means: Consider for example
the regualr expression r = a3b2a.
Substitute regular expressions s and t for symbols a
and b, respectively, in r.
Then s3t2s is obtained and it is also
a regular expression. This question asks to prove that that is always the case.
A regular expression r is constructed from basic regular expressions
, a and b by using union, concatenation
and Kleene star operations, where we are assuming without loss of generailty that
= { a, b }. So follow the sequence of operations used to generate
r using regular expressions s and t in place of a
and b, respectively. Then since union, concatenation and Kleene star of regular expressions
are regular, the result is a regular expression.
For example, to generate r = a3b2a
we may first obtain a3 by applying concatenation twice as
(aa)a. Then obtain b2
by concatenating b with itself. Then concatenate a3
with b2. Then finally concatenate a3b2
with a to obtain a3b2a.
Now by using the same sequence of concatenations on regular expressions s and
t in place of a and b, respectively,
a3b2a is obtained. This is a regular expression
since concatenation of regular expressions is a regular expression.