CS 341: Foundations of Computer Science II
Prof. Marvin Nakayama
Homework 1
1. Answer the questions below for the sets of strings:
C = {ε, aab, baa},
D = {bb, aab},
E = {ε},
F = ∅.
Except for parts (c) and (h), write out any sets with the elements in string order,
i.e., shorter strings appear before longer strings, and strings of the same length are in
alphabetical order. For any infinite sets, list only the first 8 elements in string order,
but be sure to also indicate that the set is infinite by including 3 dots after listing the
first 8 elements. For any set S of strings, we define
S ∗ = { x1 x2 · · · xk | k ≥ 0 and each xi ∈ S },
S + = { x1 x2 · · · xk | k ≥ 1 and each xi ∈ S },
where the concatenation of k = 0 strings is the empty string ε.
(a) What is D ∪ C ?
(b) What is C ∪ F ?
(c) What is C × D ?
(d) What is C ∩ D ?
(e) What is D ◦ C ?
(f) What is C ◦ E ?
(g) What is D ◦ D ◦ D ?
(h) What is P(C), the power set of C ?
(i) What is D − C ?
(j) What is C + ?
(k) What is F ∗ ?
(l) Is E ⊆ C ?
(m) Is D ⊆ C ?
(n) For this part, we first need some definitions.
1
The reverse of a string w, written wR , is the same string with the symbols
written in reverse order. For example, (cat)R = tac.
A collection of objects is closed under some operation if applying that oper-
ation to members of the collection returns an object still in the collection.
For example, the set N = {0, 1, 2, 3, . . .} is closed under the function
f (x) = x2 since the square of any nonnegative integer always results in
a nonnegative integer.√However, N is not closed under square root since, for
example, 3 ∈ N but 3 6∈ N .
Which of C, D, and E are closed under reversal? Explain your answers.
2. Let w be a string of symbols and let the language T be defined as adding w to the
language S; i.e., T = S ∪ {w}. Suppose further that T ∗ = S ∗ .
(a) Is it necessarily true that w ∈ S? If this is necessarily true, give a proof. If this
is not necessarily true, give a counterexample.
(b) Is it necessarily true that w ∈ S ∗ ? If this is necessarily true, give a proof. If this
is not necessarily true, give a counterexample.
3. For each of the following parts, give an example satisfying the given conditions. Give
a brief explanation for each of your examples.
(a) Give an example of a set S of strings such that S ∗ = S + .
(b) Give an example of a set S of strings such that S ∗ 6= S + .
(c) Give an example of a set S of strings such that S = S ∗ .
(d) Give an example of a set S of strings such that S 6= S ∗ .
(e) Give an example of a set S of strings such that S ∗ is finite.
4. Suppose we define a restricted version of the Java programming language in which
variable names must satisfy all of the following conditions:
A variable name can only use Roman letters (i.e., a, b, . . . , z, A, B, . . . , Z) or
Arabic numerals (i.e., 0, 1, 2, . . . , 9); i.e., underscore is not allowed.
A variable name must start with a Roman letter: a, b, . . . , z, A, B, . . . , Z
The length of a variable name must be no greater than 8.
A variable name cannot be a keyword (e.g., if). The set of keywords is finite.
Let L be the set of all valid variable names in our restricted version of Java.
(a) Let L0 be the set of strings satisfying the first 3 conditions above; i.e., we do
not require the last condition. How many strings are in L0 ? You can just give a
general formula for your answer; you do not need to give a single number.
(b) Prove that L is finite, where L is the set of strings satisfying all four conditions.
5. Let S be any set of strings. Prove that S ∗ = S + if and only if ε ∈ S.
