COMP 330 Winter 2021
Assignment 1
Due Date: 21st January 2021
Prakash Panangaden
7th January 2021
Please attempt all questions. There are 5 questions for credit and two other questions for people
who know some algebra, and one really difficult question for your spiritual growth. The homework
is due on myCourses at 5pm.
The extra questions at the end should not be handed in, but discussed privately with me if you
want. You will get no extra credit or other benefit related to your grade for doing it; it is
for your spiritual growth. If they make no sense to you do not worry about it.
Question 1[20 points] Fix a finite alphabet Σ and let ∅ 6= L ⊆ Σ∗. We define the following relation
R on words from Σ∗:
∀x, y ∈ Σ∗, xRy if ∀z ∈ Σ∗, xz ∈ L iff yz ∈ L.
Prove that this is an equivalence relation.
Question 2[20 points] Consider, pairs of natural numbers 〈m,n〉 where m,n ∈ N. We order them
by the relation 〈m,n〉 v 〈m′, n′〉 if (m < m′) or ((m = m′)∧n ≤ n′), where ≤ is the usual numerical
order. Prove that the relation v is a partial order.
Question 3[20 points] Give deterministic finite automata accepting the following languages over
the alphabet {0, 1}.
1. The set of all words ending in 00. [6 points]
2. The set of all words ending in 00 or 11. [6 points]
3. The set of all words such that the second last element is a 1. By “second last” I mean
the second element counting backwards from the end1. Thus, 0001101 is not accepted but
10101010 is accepted. [8 points]
1The proper English word is “penultimate.”
1
Question 4[20 points] Suppose that L is a language accepted by a DFA (i.e. a regular language)
show that the following language is also regular:
lefthalf(L) := {w1|∃w2 ∈ Σ∗ such that w1w2 ∈ L and |w1| = |w2|}.
[Hint: use nondeterminism.]
Question 5[20 points]
1. Give a deterministic finite automaton accepting the following language over the alphabet
{0, 1}: The set of all words containing 100 or 110. [5 points]
2. Show that any DFA for recognizing this language must have at least 5 states. [15 points]
Extra Question 1. Do not submit[0 points] Recall that a well-ordered set is a set equipped
with an order that is well-founded as well as linear (total). For any poset (S,≤) and monotone
function f : S → S, we say f is strictly monotone if x < y implies that f(x) < f(y); recall that
x < y means x ≤ y and x 6= y. A function f : S → S is said to be inflationary if for every x ∈ S
we have x ≤ f(x). Suppose that W is a well-ordered set and that h : W →W is strictly monotone.
Prove that h must be inflationary.
Extra question 2. Do not submit[0 points] The collection of strings Σ∗ with the operation
of concatenation forms an algebraic structure called a monoid. A monoid is a set with a binary
associative operation and with an identity element (necessarily unique) for the operation. Every
group is a monoid but there are many monoids that are not groups because they do not have
inverses; a natural example is the non-negative integers. A monoid homomorphism is a map
between monoids that preserves the identity and the binary operation. Let Σ be any finite set and
let M be any monoid. Show that any function f : Σ → M can be extended in a unique way to a
monoid homomorphism from Σ∗ →M . This is an example of what is called a universal property.
Spiritual growth[0 points] Suppose that L is a language accepted by a DFA (i.e. a regular lan-
guage) show that the following language is also regular:
LOG(L) := {x|∃y ∈ Σ∗ such that xy ∈ L and |y| = 2|x|}.
2