COMP 598  Assignment 1

COMP 598 
Assignment 1

Question 1[10 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. 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.
Question2[10 points] We defined the notion of acceptance of a language L by a DFA in class. We
also defined the notion of acceptance of a language by a finite monoid. Show that these two notions
are equivalent.
Question 3[10 points] Recall that a well-ordered set is a set equipped with an order that is wellfounded 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.
Question 4[10 points] Give deterministic finite automata accepting the following languages over
the alphabet {0, 1}.
1. The set of all words ending in 00. [2 points]
2. The set of all words ending in 00 or 11. [3 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
1The proper English word is “penultimate.”
1
10101010 is accepted. [5 points]
Question 5[10 points] Suppose that L is a language accepted by a DFA (i.e. a regular language)
show that the following language is also regular:
middle(L) := {v ∈ Σ
∗
|∃u, w ∈ Σ
∗
such that uvw ∈ L and |u| = |v| = |w|}.
Question 6[10 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. [1 point]
2. Show that any DFA for recognizing this language must have at least 5 states. [9 points]
Question 7[10 points] Suppose that L is a language accepted by a DFA (i.e. a regular language)
show that the following language is also regular:
LOG(L) := {x|∃y ∈ Σ
∗
such that xy ∈ L and |y| = 2|x|
}.
This is very tedious to write out in detail so I am happy with a description of the idea. Just
because it is an informal description does not mean that it is vague or unclear.
Question 8[10 points] Show that the following languages are not regular by using the pumping
lemma.
1. {a
2n
b
n}.
2. {x ∈ {a, b, c}
∗
||x| is a square.} Here |x| means the length of x.
Question 9[10 points] Suppose that L is a language accepted by a DFA (i.e. a regular language)
show that the following language is not necessarily regular:
outer(L) := {uw ∈ Σ
∗
|∃v ∈ Σ
∗
such that uvw ∈ L and |u| = |v| = |w|}.
You have to give me a specific L which is regular and prove that outer(L) is not regular.
Question 10[10 points] Design an NFA K with n states, over a one-letter alphabet, such that K
rejects some strings, but the shortest string that it rejects has length strictly greater than n.
2