CS 3800 Spring 2020
W. Schnyder 2/8/2020
Homework 5
(due Friday, February 14)
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: 2.2 (for Tuesday), 2.3 (for Friday).
1. [8 Points] Use the Pumping Lemma to show that the following languages are not regular.
In each case, carefully describe the string that will be pumped and explain why pumping
it leads to a contradiction.
(a) {w wR | w ∈ {a, b}∗ }
Solution: Suppose that L = {w wR | w ∈ {a, b}∗ } is regular and let p ≥ 1 be its
pumping constant.
String w = ap bbap belongs to L and has length |w| ≥ p. Therefore w = xyz where
(1)y 6= ε, (2) |xy| ≤ p, (3) xy n z ∈ L for all n ≥ 0.
By (2) y is within the run of a’s on the left.
By (3) xy 0 z ∈ L
By (1) removing y decreased the number of a’s on the left. The resulting string
therefore has the form at bbap with t < p and does not belong to L. This contradicts
(3)!
(b) {w w | w ∈ {a, b}∗ }
(w stands for w with each occurrence of a replaced by b, and vice versa.)
Solution: Suppose that L = {w w | w ∈ {a, b}∗ } is regular and let p ≥ 1 be its
pumping constant.
String w = ap bp belongs to L and has length |w| ≥ p. Therefore w = xyz where
(1)y 6= ε, (2) |xy| ≤ p, (3) xy n z ∈ L for all n ≥ 0.
By (2) y is within the run of a’s on the left.
By (3) xy 0 z ∈ L
By (1) removing y decreased the number of a’s on the left. If the resulting string
is of odd length, then it clearly cannot belong to L. If it is of even length, then its
right half consists only of b’s, but its left half now has a’s and b’s. Such a string
cannot belong to L. This contradicts (3)!
Page 1 of 7
, CS 3800 Spring 2020
W. Schnyder 2/8/2020
2. [4 Points] Let Σ = {a} and consider the language
L = {at | t is a prime number }
Use the pumping Lemma to prove that L is not regular. Carefully describe the string
that will be pumped and explain why pumping it leads to a contradiction.
Solution: Suppose, for contradiction, that L = {at | t is a prime number } is regular and
let p be its pumping constant.
Let t0 be any prime number with t0 ≥ p and consider the word w = at0 . As w ∈ L and
|w| ≥ p, word w can be written as w = xyz such that
(1) y 6= ε (2) |xy| ≤ p (3) xy n z ∈ L for all n ∈ N
By (3), |xy n z| is a prime number for every choice of n ∈ N. Below, we show this not to
be the case, and that thus the initial assumption that L is regular is false.
We don’t know what x, y, z are, but we can show that whatever they are, there is a choice
of n such that |xy n z| isn’t a prime number. Note first that |xy n z| = |xz| + n|y|. We
distinguish two cases.
• Case 1: |xz| ≤ 1. Choosing n = 0, we have |xy 0 z| = |xz| ≤ 1. This isn’t a prime
number, as prime numbers are at least 2.
• Case 2: |xz| ≥ 2. Choosing n = |xz|, we have |xy n z| = |xz| + n|y| = |xz| + |xz||y| =
|xz|(1 + |y|). From (1) follows that 1 + |y| ≥ 2 and thus that |xy n z| is the product
of two integers greater than 1. Therefore |xy n z| isn’t a prime number.
Note that this proof used properties (1) and (3) of w above, but it didn’t need property
(2): |xy| ≤ p.
3. [12 Points] For each of the following languages, either prove that it is regular, or prove
that it isn’t.
(a) {w ∈ {a, b}∗ | w has an equal number of aa’s and bb’s}
For example, aaaabbabbb is in this language since it has
3 aa’s and 3 bb’s, and aabbaaabb is not in the language
as it has 3 aa’s but only 2 bb’s.
Solution: The language L = {w ∈ {a, b}∗ | w has an equal number of aa’s and bb’s}
is not regular.
In fact, suppose (for contradiction) that L is regular and let p ≥ 1 be its pumping
constant.
String w = ap bp belongs to L as it has the same number p − 1 of aa’s and bb’s.
Furthermore, it has length |w| ≥ p. Therefore w = xyz where
(1)y 6= ε, (2) |xy| ≤ p, (3) xy n z ∈ L for all n ≥ 0.
By (2) y is within the run of a’s on the left.
By (3) xy 0 z ∈ L
By (1) removing y decreases the number of a’s on the left. The resulting string
therefore has less aa’s than bb’s and does not belong to L. This contradicts (3)!
Page 2 of 7
W. Schnyder 2/8/2020
Homework 5
(due Friday, February 14)
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: 2.2 (for Tuesday), 2.3 (for Friday).
1. [8 Points] Use the Pumping Lemma to show that the following languages are not regular.
In each case, carefully describe the string that will be pumped and explain why pumping
it leads to a contradiction.
(a) {w wR | w ∈ {a, b}∗ }
Solution: Suppose that L = {w wR | w ∈ {a, b}∗ } is regular and let p ≥ 1 be its
pumping constant.
String w = ap bbap belongs to L and has length |w| ≥ p. Therefore w = xyz where
(1)y 6= ε, (2) |xy| ≤ p, (3) xy n z ∈ L for all n ≥ 0.
By (2) y is within the run of a’s on the left.
By (3) xy 0 z ∈ L
By (1) removing y decreased the number of a’s on the left. The resulting string
therefore has the form at bbap with t < p and does not belong to L. This contradicts
(3)!
(b) {w w | w ∈ {a, b}∗ }
(w stands for w with each occurrence of a replaced by b, and vice versa.)
Solution: Suppose that L = {w w | w ∈ {a, b}∗ } is regular and let p ≥ 1 be its
pumping constant.
String w = ap bp belongs to L and has length |w| ≥ p. Therefore w = xyz where
(1)y 6= ε, (2) |xy| ≤ p, (3) xy n z ∈ L for all n ≥ 0.
By (2) y is within the run of a’s on the left.
By (3) xy 0 z ∈ L
By (1) removing y decreased the number of a’s on the left. If the resulting string
is of odd length, then it clearly cannot belong to L. If it is of even length, then its
right half consists only of b’s, but its left half now has a’s and b’s. Such a string
cannot belong to L. This contradicts (3)!
Page 1 of 7
, CS 3800 Spring 2020
W. Schnyder 2/8/2020
2. [4 Points] Let Σ = {a} and consider the language
L = {at | t is a prime number }
Use the pumping Lemma to prove that L is not regular. Carefully describe the string
that will be pumped and explain why pumping it leads to a contradiction.
Solution: Suppose, for contradiction, that L = {at | t is a prime number } is regular and
let p be its pumping constant.
Let t0 be any prime number with t0 ≥ p and consider the word w = at0 . As w ∈ L and
|w| ≥ p, word w can be written as w = xyz such that
(1) y 6= ε (2) |xy| ≤ p (3) xy n z ∈ L for all n ∈ N
By (3), |xy n z| is a prime number for every choice of n ∈ N. Below, we show this not to
be the case, and that thus the initial assumption that L is regular is false.
We don’t know what x, y, z are, but we can show that whatever they are, there is a choice
of n such that |xy n z| isn’t a prime number. Note first that |xy n z| = |xz| + n|y|. We
distinguish two cases.
• Case 1: |xz| ≤ 1. Choosing n = 0, we have |xy 0 z| = |xz| ≤ 1. This isn’t a prime
number, as prime numbers are at least 2.
• Case 2: |xz| ≥ 2. Choosing n = |xz|, we have |xy n z| = |xz| + n|y| = |xz| + |xz||y| =
|xz|(1 + |y|). From (1) follows that 1 + |y| ≥ 2 and thus that |xy n z| is the product
of two integers greater than 1. Therefore |xy n z| isn’t a prime number.
Note that this proof used properties (1) and (3) of w above, but it didn’t need property
(2): |xy| ≤ p.
3. [12 Points] For each of the following languages, either prove that it is regular, or prove
that it isn’t.
(a) {w ∈ {a, b}∗ | w has an equal number of aa’s and bb’s}
For example, aaaabbabbb is in this language since it has
3 aa’s and 3 bb’s, and aabbaaabb is not in the language
as it has 3 aa’s but only 2 bb’s.
Solution: The language L = {w ∈ {a, b}∗ | w has an equal number of aa’s and bb’s}
is not regular.
In fact, suppose (for contradiction) that L is regular and let p ≥ 1 be its pumping
constant.
String w = ap bp belongs to L as it has the same number p − 1 of aa’s and bb’s.
Furthermore, it has length |w| ≥ p. Therefore w = xyz where
(1)y 6= ε, (2) |xy| ≤ p, (3) xy n z ∈ L for all n ≥ 0.
By (2) y is within the run of a’s on the left.
By (3) xy 0 z ∈ L
By (1) removing y decreases the number of a’s on the left. The resulting string
therefore has less aa’s than bb’s and does not belong to L. This contradicts (3)!
Page 2 of 7
