COMP 330 Autumn 2021
Assignment 3 Solutions and Grading Guide
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.
For the first and the fourth they get zero for the wrong answer regardless of what they wrote as
“justification.” If they give a wrong or badly written justification take a point off for the first and
2 points off for the fourth. The second question is tricky. If they have the wrong answer they lose
4. If their justification of the wrong answer is reasonable they should get the 3 marks. If they
got the right answer and gave a garbled or incorrect explanation they lose 3 marks. For the third
case, take 2 points off for a wrong asnwer and more points off depending on how unreasonable
the “justification” is.
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.
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.
If they do not understand which choices are up to them and which choices are up to the adversary
they get zero. They have to get the basic logic right. If they choose a starting string not in
the language they lose half the marks. If they do not argue the last part correctly they lose 5
points.
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.
2
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.
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.
This is conceptually tricky. It is essential that they explain their steps clearly. Rambling, incoherent
writing should be penalized with half the marks deducted. They lose two marks for not answering
the question at the end. If they do not get that proving the positive direction of the pumping
lemma involves inverting who makes the choices they lose 8 marks.
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 one can never have an a followed by a b.
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.
3
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)∗.
If they thought that ab had to be a consecutive substring they should lose 5 point as this will
force them to use more than 5 states. If they interpreted it as “once you see an a you cannot
see a b later on” then they should be marked for correctness as follows: They lose 10 points
for a wrong automaton with fewer than 5 states. They lose 2 points for not giving the regular
expression. They lose 15 points for a wrong automaton with more than 5 states. They lose 3
points for not showing the dead state. They lose all points (i.e. 18) for giving an NFA.
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
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.
They must explicitly show the equivalence classes and prove that they are all distinct. They do
NOT have to show every possible class.
1Did I ever mention the importance of reading the quantifer?
4