COMP 330  Assignment 2

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