COMP 330 Winter 2021
Assignment 2 Solutions
Prakash Panangaden
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}
Solution
• (b∗ab∗ab∗)∗ + b∗
• (a∗ba∗)(ba∗ba∗)∗
• b∗a∗
• b∗a∗(bbb∗a∗)∗b∗. Another equivalent expression is b∗+b∗aa∗(bbb∗aa∗)∗b∗.
The last one is quite tricky. An a can be followed by two or more b’s but
not by a single b if you want more a’s later.
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).
Solution We proceed by induction on the length of the word. The base
case is when w has length 1, i.e. it is a single letter. This means we must
show:
∀a ∈ Σ, δ∗(s1, a) = δ∗(s2, a).
1
From the definition of δ∗ this becomes just
∀a ∈ Σ, δ(s1, a) = δ(s2, a).
But this was given to us in the problem so the base case is immediately
verified.
The inductive hypothesis is that
∀w ∈ Σ∗, |w| < n implies δ∗(s1, w) = δ∗(s2, w).
Now we consider a word of the form wa where w has length n− 1 and a is
any letter in Σ.
δ∗(s1, wa) = δ(δ
∗(s1, w), a) = δ(δ
∗(s2, w), a) = δ
∗(s2, wa).
The first equation follows from the definition of δ∗, the second follows from
the inductive hypothesis and the last from the definition of δ∗. This verifies
the inductive case; we are done.
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.
Solution
1. The demon picks a number p. I pick the string apba(p+1). Whatever
the demon tries to do he is forced to pick y to consist of a nonempty
string that consists exclusively of as, because |xy| ≤ p and |y| > 0,
say that y = al. Now I choose i = 3. The new string is a(p+2l)ba(p+1)
which is not in the language since 2l 6= 1. My strategy is sure to work
because I have taken into account anything that the demon might do.
2. Suppose the demon picks the number p. I choose the string apbbap
which is a palindrome. Now the demon tries to divide it up into x, y, z
with |xy| ≤ p, |y| > 0, in such a way that xyiz a palindrome for all
i ≥ 0. It must be the case that x = ak for some k ∈ {0, …, p − 1},
y = aj for some j ∈ {1, …, p} and z = albbap for some l ∈ {0, …, p−1}.
Now I choose i = 2 and we see that xy2z = ap+jbbap, which is not a
palindrome, since j > 0. Therefore, this language is not regular.
2
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. {a2nbn}.
Solution
1. The demon picks some p. I choose the string ap
2
which has length p2
which is indeed a square. Now the demon has to pick y to consist of
a’s exclusively because there are no other letters in the string. Let
|y| = q > 0 and q ≤ p. Now I choose i = 2. Then we get ap
2+q as the
pumped string. This string has length p2 + q. Now q ≤ p < 2p + 1,
hence p2 + q < p2 + 2p+ 1 = (p+ 1)2. Thus p2 + q cannot be a square
since it is strictly less than the next square after p2. Thus, I win and
the language is not regular.
2. The demon picks some p. I pick a2pbp. The demon is forced to pick y
consisting exclusively of a’s and |y| ≤ p; let |y| = q > 0. I pick i = 0
so the “pumped” string is a2p−qbp and clearly this string is not in the
language.
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.
Solution Here is the original automaton:
3
s0start s1 s2 s3 s4
1
0
1
0 0
1
1
0
0
1
It is clear from this picture that s3 is an unreachable state so we remove it
right away.
Here is the table:
s4 /
s2 / x
s1 / x 2
s0 / x x x
s0 s1 s2 s4
After running the algorithm the pairs that cannot be equivalent are marked
with an X. The diagonal is marked with a / and of course we do not need
to do anything above the diagonal. There is only one pair left unmarked.
According to the algorithm, these states are equivalent. This means that s1
and s4 can be lumped together to give a 3-state machine. The minimized
machine is shown below:
s0start s14 s2
1
0
1
0
0
1
4