COMP 330 Winter 2021 Mid-term Examination Solutions
Prakash Panangaden February 4, 2021
Question 1[40 points] In this question the alphabet is fixed as {a, b}.
• Write a regular expression for the language of strings containing a’s only when they occur as part of a block of consecutive a’s of even length. Thus the legal strings cannot contain an a by itself or a substring of 3 or 5 or 7 . . . consecutive a’s. Thus baabbb is accepted, so is aabaabaaaabbaabbaa and so is bbbbbbb which has no consecutive pair of a’s. However baaab is not allowed as this has three consecutive a’s nor is bababaab or baaaaab.
Solution: b∗((aa)∗b∗)∗. The a’s have to appear in pairs, but there can be any number (including 0) of b’s before the pair of a’s. This pattern can be repeated any number of times. Finally there could be a block of b’s at the end. There are other correct answers as well.
• Design a DFA (not an NFA) for this language. A picture is preferred. You must show the dead state if there is one. For full credit your machine must have 3 states including the dead state (if there is one).
Solution:
b
a
start s0
a s1 b
s2 a,b
Question 2[40 points] Show, using the pumping lemma, that the following language is not regular.
The alphabet is Σ = {a, b}. I prefer answers formatted as a game against the demon. L = {arbt|r − t = 2, r, t > 0}.
Solution:
1
The demon chooses some pumping length p. The angel chooses ap+2bp as the string w. The demon has to choose x, y, z in such a way that the length of xy is less than p. This means that the string y has to be part of the initial block of a’s. The demon has no choice. So we have y = ak where 0 < k ≤ p. The angel chooses i = 2 so the new string is xyyz = ap+2+kbp. But the difference is now p + 2 + k − p = 2 + k ̸= 2, so the pumped string is not in the language and so, the language cannot be regular. Question 3[20 points] Are the following statements true or false? No explanations are required. We have some fixed alphabet that we are working with. 1. If L is a non-regular language and R is a regular language then L∩R must be regular. FALSE 2. If L is a non-regular language and R is a regular language then L ∩ R cannot be regular. FALSE 3. For every regular language there is a unique minimal NFA. FALSE 4. When we run the minimization algorithm on a DFA we cannot be sure that it will always terminate. FALSE 5. If L1 is an infinite regular language and L2 is a finite language then the DFA to recognize L1 must have more states that the DFA to recognize L2. FALSE 2