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 Ai is regular. [5] i=1
• 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.
•Thisisalsofalse. IfAisΣ∗ andBisanythingatall,otherthan∅thenAB=Σ∗ 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 ̸= 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≥0andifi=1thenj=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 wordinLmustbeginwithexactlyonea,andsoifitisalsoinF theni=j. Butweknow 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 thecasewherel=0,sow=bjck. Thenchoosex=εandy=bifthefirstletterisab,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.
Nextconsiderthecasewherel=1,sow=abjcj. Againletx=ε,y=a,andz=bjcj. Then pumping results in a string of the form anbjcj, which is clearly in F.
Nextconsiderthecasewherel=2,sow=aabjck. Nowwecan’tchoosex=εandy=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.
start q0 b q1 a q2
b
aaa b
q3
a,b
b
q4
2. Give a regular expression for this language. Solution b(bb)∗(aa)∗.
Question 5[20 points] Consider the language L = {anbm|n ̸= 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 ̸≡L aj for i ̸= 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 ordertocheckthatx̸≡L yweneedtofindonestringzsuchthatxz∈Landyz̸∈Lor viceversa. Inourcase,wehavex=ai andy=aj soconsiderz=bi. Clearlyxz=aibi ̸∈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