CS 3800 - Homework 4 Solutions (All Answers are Correct)

CS 3800 Spring 2020
W. Schnyder 2/1/2020

Homework 4
(due Friday, February 7)

Instructions: This homework is to be submitted on GradeScope as a single pdf (not in parts) by
11:59 pm on the due date. You may either type your solutions in a word processor and print to
a pdf, or write them by hand and submit a scanned copy. Do write and submit your answers as
if they were a professional report. There will be point deductions if the submission isn’t neat (is
disordered, difficult to read, scanned upside down, etc. . . .).
Begin by reviewing your class notes, the slides, and the textbook. Then do the exercises below.
Show your work. An unjustified answer may receive little or no credit.
Read: 1.4 (for Tuesday), 2.1 (for Friday).

1. [18 Points] For each of the following statements, state whether it is true or false. Explain.
(a) baa ∈ a∗ b∗ a∗ b∗
Solution: true via a0 b1 a2 b0
(b) a∗ ∪ b∗ = (a ∪ b)∗
/ a∗ ∪ b ∗
Solution: false as ab ∈
(c) (a∗ b∗ )∗ = (a ∪ b)∗
Solution: a ∈ a∗ b∗ and b ∈ a∗ b∗ thus (a ∪ b) ⊆ a∗ b∗ and therefore (a ∪ b)∗ ⊆ (a∗ b∗ )∗ .
As (a∗ b∗ )∗ ⊆ (a ∪ b)∗ , there follows that the two sets are equal.
(d) b∗ a∗ ∩ a∗ b∗ = a∗ ∪ b∗
Solution: true. Each string belonging to b∗ a∗ ∩ a∗ b∗ has either only a’s or only b’ so
b∗ a∗ ∩ a∗ b∗ ⊆ a∗ ∪ b∗ . Furthermore a∗ ⊆ εa∗ ∩ a∗ ε ⊆ b∗ a∗ ∩ a∗ b∗ and b∗ ⊆ b∗ ε ∩ εb∗ ⊆
b∗ a∗ ∩ a∗ b∗ . Thus a∗ ∪ b∗ ⊆ b∗ a∗ ∩ a∗ b∗ .
(e) a∗ b∗ ∩ c∗ d∗ = ∅
Solution: false as a∗ b∗ ∩ c∗ d∗ = {ε}
(f ) abcd ∈ (a (cd)∗ b)∗
Solution: false as every b in a string of (a (cd)∗ b)∗ must either be at the end of this
string or must be followed by an a.

2. [8 Points] Let Σ = {a, b}. Write regular expressions for the sets
(a) All strings in Σ∗ with no more than three a’s.
Solution: Several solutions are possible. One, not the shortest, is
b∗ ∪ (b∗ a b∗ ) ∪ (b∗ a b∗ a b∗ ) ∪ (b∗ a b∗ a b∗ a b∗ )
(b) All strings in Σ∗ with a number of a’s divisible by 3.
Solution: Let L = {w ∈ Σ∗ | the number of a’s in w is divisible by 3} and L1 =
{w ∈ Σ∗ | w has exactly three a’s}.
Then L = (L1 )∗ ∪ b∗ and L1 = b∗ a b∗ a b∗ a b∗ , thus L = (b∗ a b∗ a b∗ a b∗ )∗ ∪ b∗ . One
may simplify (not required) and obtain L = (b∗ a b∗ a b∗ a)∗ b∗ = b∗ (a b∗ a b∗ a b∗ )∗

Page 1 of 7

, b DFA1 DFA7
0 0 0 0
q2 b
1 0 0,1 1 0 0,1
a CS 3800 Spring 2020
W. Schnyder 1 1 1 1 2/1/2020
b
a, b
q2 b strings having 00 or 11 strings without 00 or 11
DFA11 sipser 1.16b
a
3. [8 Points] Rewrite each of the following regular expressions as a simpler regular expression
describing the same 1language. 1(For full credit simplify as much as possible). a
{1, 2} {1, 2
(a) ∅∗ ∪ a∗ ∪ b∗ ∪ (a ∪ b)0∗ 0 0
0,1

Solution: (a ∪ b)∗ 1 b
DFA2 divisibility by 3 ∗ a
(b) ((a a) b) ∪ bDFA8 strings with 000 substring
Solution: ((a∗ a) b) ∪ b = (a+ b) ∪ (εb) = (a+ ∪ ε)b = a∗ b ∅ {2,
s
(c) (a∗ b)∗ ∪ (b∗ a)∗ a, b
0 1
FA4 empty string 0,1 Solution: 1 0
∗ ∗ ∗
0,1
(a b) = {ε} 0∪ {w ∈
q0 {a, b} | wq1ends withq b} 1
2
∗ ∗ ∗
(b a) = {ε} ∪ {w ∈ {a, b} | w ends with a}
Therefore (a∗ b)∗ ∪ (b∗ a)∗1= (a ∪ b)∗0
0 (d) (a ∪ b)∗ a (a ∪ b)∗ DFA9 divisibility by 3
1
Solution: (a ∪ b)∗ a (a ∪ b)∗ = {w ∈ {a, b}∗ | w has an a in it somewhere} =
0,1 ∗ ∗ DFA10
b a (a ∪ b)
1
{q0,q1diagram
4. [4 Points] Draw the state } {q0,q1,q2} a, b a, b the language described
a, b of a three-state NFA recognizing
∗ ∗ ∗
by ((a ∪ c) (b ∪ c) c b ).
1 Solution:
0
1
0 a, c b, c b
1 ε c
DFA6 begin/end with 1

NFA5 reverse words
M N
5. [4 Points] Use the procedure from class (described in the proof of Lemma 1.55 in the text)
to convert the expression a∗ ∪ (ab)∗ to a NFA.
Sipser 1.28b
Solution:
ε

0,1 ε a
ε ε ε
ε

ε
ε a ε b



6. [10 Points] Use the method from class (Lemma 1.60) to convert the following finite au-
tomata to regular expressions. In each case first construct the corresponding GNFA
(without ∅ labeled edges), then strip states one by one in numerical order (strip state 1
first, then state 2, . . . ). Show your work, including the diagrams after each stripping.
(a)

Page 2 of 7