CS 390 Solutions to Unit 6 Exercises
pp. 112 - 113
3.1 (a) 001 and 011 are the only ones.
All strings of length shorter than 3 are in the language.
3.3 Note that in this question you can treat r and s
as if they were a single symbol.
3.3 (a) (r + s)*.
Note that this is the set of all strings that are constructed from the strings of
r and s.
(e) (r + s)*.
(r + s)*rs(r +
s)*
is the set of strings containing at least one rs. If a string
does not contain rs, then it is in r*,
s* or s*r*. Hence
it is in s*r*.
Hence together
(r + s)*rs(r +
s)*
and s*r* cover all the strings generated
from the strings of r and s.
3.4 (11 + 111)* represents all the strings consisting of 1's
except 1.
(111*)* also represents all the strings consisting of 1's except 1
because
(1) it contains strings 11 and 111. Hence all the strings including the empty string
consisting of 1's except 1 are included in it.
(2) Since all the strings of (111*)* consist of 1's and if
they are nonempty their length is at least 2. Thus they are all included in
(11 + 111)*.
Hence (111*)* = (11 + 111)*.
3.8 (a) (001)*(11)*.
All the strings of L are generated from the empty string by prepending any number
of 001's and appending any number of 11's.
3.9 (a) 1*01*01*.
Two 0's can be separated by any number of 1's and they can be preceded and/or followed
by any number of 1's.
3.9 (g) (1 + 01 )*(
+ 0 + 00)( 10 + 1 )*.
The one occurrence of 00 can be preceded or followed by any number of 1's.
If 0's are to precede or follow the 00, then they must be separated from each other
by at least one 1. Hence we need 01 in front of the 00 and 10 after that.
3.10 (b) ( 0 + 1 )* is the set of strings of length 3
consisting of 0's and 1's. Hence (( 0 + 1 )3)* is the
set of strings whose length is a multiple of 3.
To obtain the strings of
(( 0 + 1 )3)*(
+ 0 + 1 ) ,
0 or 1 is appended or nothing is appended at the end of those strings.
Hence (( 0 + 1 )3)*(
+ 0 + 1 )
is the set of strings of 0's and 1's whose length is 3n or 3n + 1,
where n is a natural number.