COMP 330 Winter 2021 Assignment 2
Due Date: 4th February 2021
Prakash Panangaden 21st January 2021
There are 5 questions for credit. There are four questions at the end. The first of them requires some algebra. The second is a bit harder than the usual homework but not impossible; it is worth looking at. Don’t even look at the third one, it is impossible. The fourth is a puzzle. If you can’t do it, it does not mean anything about how well you are understanding the material. If you like mathematical puzzles you might enjoy this one. The homework is due on myCourses at 5pm.
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 ̸= 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).
Question 3[20 points]
Show that the following languages are not regular by using the pumping lemma.
1. {anbman+m|n, m ≥ 0},
2. {x|x = xR,x ∈ Σ∗}, where xR 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
1. {x ∈ {a, b, c}∗||x| is a square.} Here |x| means the length of x.
2. {a2nbn}.
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 wherej=i2+a mod5.
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.
Extra Question 1[0 points]
LetM beanyfinitemonoidandleth:Σ∗ →M beamonoidhomomorphism. LetF ⊆M beany 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]
Extra Question 2[0 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, Of course, these are only examples and my definition of Nk(A) is perfectly valid when A is an infinite
set. Prove that if L is regular then N2(L) is regular. What happens to Nk(L)?
Spiritual growth[0 points] In extra question 1, 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.
Pure puzzle[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.
2
0