COMP 330

Assignment 2

There are 5 questions for credit and one for your spiritual growth (Q6) and

one for pure fun (Q7). The homework is due in class at the beginning of

the class. There are a couple of alternate questions; you should read them

even if you do not plan on answering them. If question 6 makes no sense to

you do not let it worry you. Have a look at question 7, it is a pure puzzle.

If you don’t get it, it does not mean that you do not grasp the material. If

you like mathematical puzzles you might enjoy this one.

Question 1[20 points]

Give regular expressions for the following languages over {a, b}:

1. {w|w contains an even number of occurrences of a}

2. {w|w contains an odd number of occurrences of b}

3. {w| does not contain the substring ab}

4. {w| does not contain the substring aba}

Try to make your answers as simple as possible. We will deduct marks if

your solution is excessively complicted.

Question 2[20 points]

Suppose that you have a DFA M = (S, Σ, s0, δ, F). Consider two distinct

states s1, s2 i.e. s1 6= s2. Suppose further that for all a ∈ Σ δ(s1, a) =

δ(s2, a). Show that for any nonempty word w over Σ we have δ

∗

(s1, w) =

δ

∗

(s2, w).

1

Alternate Question 2[20 points]

Let M be any finite monoid and let h : Σ∗ → M be a monoid homomorphism. Let F ⊆ M be any subset (not necessarily a submonoid) of M. Show

that the set h

−1

(F) is a regular language. This means you have to describe

an NFA (or DFA) from the given M, F and h[8 points]. Show that every

regular language can be described this way.[12 points]

Question 3[20 points]

Show that the following languages are not regular by using the pumping

lemma.

1. {a

n

b

ma

n+m|n, m ≥ 0},

2. {x|x = x

R, x ∈ Σ

∗}, where x

R means x reversed; these strings are

called palindromes. An example is abba, a non-example is baba.

Question 4[20 points] Show that the following languages are not regular

by using the pumping lemma.

1. {x ∈ {a, b, c}

∗

||x| is a square.} Here |x| means the length of x.

2. {a

2n

b

n}.

Question 5[20 points] We are using the alphabet {0, 1}. We have a DFA

with 5 states, S = {s0, s1, s2, s3, s4}. The start state is s0 and the only

accepting state is also s0. The transitions are given by the formula

δ(si

, a) = sj where j = i

2 + a mod 5.

Draw the table showing which pairs of states are inequivalent and then

construct the minimal automaton. Remember to remove useless states right

from the start, before you draw the table. I am happy with a drawing of

the automaton.

Alternate Question 5[20 points] We define the Hamming distance between two strings w, x of the same length to be the number of places where

they differ. If the strings have different lengths we say that their Hamming

distance is infinite. We write is as H(x, y). For example, H(000, 010) = 1

and H(0000, 1001) = 2. Given a set of words A and a positive integer k we

define the new set Nk(A) as follows

Nk(A) = {x|∃y ∈ A such that H(x, y) ≤ k}.

For example N1({000, 111}) = {000, 001, 010, 001, 111, 110, 101, 011} and

N2({000}) = {000, 001, 010, 100, 110, 101, 011}. Of course, these are only

2

examples and my definition of Nk(A) is perfectly valid when A is an infinite

set. Prove that if A is regular then N2(A) is regular. What happens to

Nk(A)? [You don’t have to answer this last question.]

Question 6[0 points] In alternate question 2, we showed how one could

have defined regular languages in terms of monoids and homomorphisms

instead of in terms of DFA. Given a regular language L, we can define an

equivalence relation on words in Σ∗ as follows:

x ≡L y = ∀u, v ∈ Σ

∗

, uxv ∈ L ⇐⇒ uyv ∈ L.

It is easy to see that this is a congrence relation (with respect to concatenation). If we quotient by this equivalence relation we get a monoid called

the syntactic monoid of the language L. The syntactic monoid is finite iff

L is regular. Now what can you say about the language if the monoid happens to be a group? What if it is not only not a group but contains no

subgroup? Yes, a monoid that is not a group could have a submonoid which

is a group.

Question 7[0 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.

3