COMP 330 Winter 2021
Assignment 3 Solutions
Prakash Panangaden
March 14, 2021
Question 1[20 points] Are the following statements true or false? Prove your answer in
each case. We have some fixed alphabet Σ with at least two letters. In the following A and
B stand for languages, i.e. subsets of Σ∗.
• If A is regular and A ⊆ B then B must be regular. [3]
• If A and AB are both regular then B must be regular. [7]
• If {Ai|i ∈ N} is an infinite family of regular sets then
∞⋃
i=1
Ai is regular. [5]
• If A is not regular it cannot have a regular subset. [5]
Solutions
• Certainly not! Any finite set is regular so we can take B to be any non-regular language
and A to be a finite subset of B.
• This is also false. If A is Σ∗ and B is anything at all, other than ∅ then AB = Σ∗
which is regular but I can choose B to be nastily non-regular.
• This is also false. I can take Ai = {aibi} which is regular because it is finite but the
union over all i is our basic example of a non-regular set {anbn|n ≥ 0}.
• Certainly not, see part 1.
Question 2[20 points]
Show that the following language is not regular using the pumping lemma.
{anb2n|n > 0}
Solution I will format the answer in the form of the game against the demon.
1. Demon chooses some pumping length p > 0.
1
2. I choose apb2p.
3. The demon’s choice of x, y is constrained by the requirement that |xy| ≤ p and |y| > 0.
Thus, y has to consist exclusively of a’s and cannot be the empty string: y = ak for
some p ≥ k > 0.
4. I choose i = 2, so I get my pumped string to be ap+kb2p and since 2p + 2k 6= 2p we
have a pumped string that is not in the language.
This shows that we have a winning strategy against the demon and the language is therefore
not regular.
Question 3[20 points] Show that the language
F = {aibjck|i, j, k ≥ 0 and if i = 1 then j = k}
is not regular. Show, however, that it satisfies the statement of the pumping lemma as I
proved it in class, i.e. there is a p such that all three conditions for the pumping lemma are
met. Explain why this does not contradict the pumping lemma.
Solution: First, I will show that F is not regular. Obviously we cannot use the pumping
lemma directly, but we can use the closure properties of regular languages to massage the
language first so that we get something to which we can apply the pumping lemma. If F
were regular, than the intersection of F and any regular language would also be regular. We
know that L = {abicj|i, j ≥ 0} is a regular language, and clearly L∩F = {abncn}, since any
word in L must begin with exactly one a, and so if it is also in F then i = j. But we know
that {abncn} is not regular by an easy variation of the example done in class, so F must not
be regular.
Next I will show that F satisfies the pumping lemma. This is also done with games but
we are using the pumping lemma not its negation so the quantifiers, and hence the moves,
are reversed. You choose p, the demon chooses a word, you choose x, y, z subject to the
constraints and the demon chooses i.
Let p = 2. Then the demon gives you a word w from F , of the form albjck. First, consider
the case where l = 0, so w = bjck. Then choose x = � and y = b if the first letter is a b, or
y = c otherwise. Let z be the rest of the word. If y = b, then z = bj−1ck, and pumping results
in a string of the form bnbj−1ck, which is clearly in F for any n. If y = c, then z = ck−1. So
pumping results in a string of the form cnck−1 which is also clearly in F .
Next consider the case where l = 1, so w = abjcj. Again let x = �, y = a, and z = bjcj.
Then pumping results in a string of the form anbjcj, which is clearly in F .
Next consider the case where l = 2, so w = aabjck. Now we can’t choose x = � and y = a,
because if we do, then xy0z = abjck is not necessarily in our language. So choose y = aa.
2
Then pumping cannot result in a string of the form abjck, because we either pump down
and have no a’s, or we pump up and have more than one a. So pumping results in strings
which are still in our language.
Finally, consider the case where l > 2. Again choose x = � and y = a. If we pump down, we
remove only one a, so our string still has at least two a’s, and j and k don’t have to match.
If we pump up, the string is clearly still in our language. This proves that the language
satisfies the pumping lemma.
This does not contradict the pumping lemma because the pumping lemma claims that all
regular languages are “pumpable,” which is not the same as claiming that all languages that
are “pumpable” must be regular. Logically, p⇒ q is not the same as q → p.
Question 4[20 points] Let D be the language of words w, over the alphabet {a, b} such that
w has an even number of a’s and an odd number of b’s and does not contain the substring
ab. By this I mean that once you see an a you can never have a b later on.
1. Give a DFA with only five states, including any dead states, that recognizes D.
Solution Once you see an a you can never have a b later on. If your first letter is an a
it has to be rejected because there is now no way to get a b and the word has to have
at least one b. The picture is here.
q0start q1 q2
q3 q4
b
a
b a
a
b
a, b
a
b
2. Give a regular expression for this language.
Solution b(bb)∗(aa)∗.
Question 5[20 points] Consider the language L = {anbm|n 6= m}; as we have seen this is not
regular. Recall the definition of the equivalence ≡L which we used in the proof of the Myhill-
Nerode theorem. Since this language is not regular ≡L cannot have finitely many equivalence
classes. Exhibit explicitly, infinitely many distinct equivalence classes of ≡L.
Solution Let me clear up some misconceptions. First, the relation ≡L is defined between
all pairs of strings, not just strings in L. Second, we require either that both xz and yz are
3
in L or that neither of them are in L; some of you seem to think that the defining condition
states that both xz and yz must be in L. Third this condition has to hold for all z ∈ Σ∗ not
just one z1.
I claim that ai 6≡L aj for i 6= j. Recall what the relation ≡L means. It has a universal
quantifier in the definition, so the negated version has an existential quantifier in it. In
order to check that x 6≡L y we need to find one string z such that xz ∈ L and yz 6∈ L or
vice versa. In our case, we have x = ai and y = aj so consider z = bi. Clearly xz = aibi 6∈ L
and yz = ajbi ∈ L. Thus the equivalence classes [ai] are different for every i and I have now
shown you infinitely many distinct equivalence classes.
1Did I ever mention the importance of reading the quantifer?
4