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