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 ∅ ≠ 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⟩ ⊑ ⟨m′, n′⟩ if (m < m′) or ((m = m′)∧n ≤ n′), where ≤ is the usual numerical order. Prove that the relation ⊑ 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 ̸= 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