COMP 330 Winter 2021
Mid-term Examination
School of Computer Science
McGill University
Answers due by 13th February 2021 8:00am
This examination is open book. You have 60 minutes. There are 3 questions
on two pages. Please write your answers in a pdf file and upload it. The
upload will be under the assignments tab. Automata pictures can be hand
drawn.
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 sub-
string 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. [20]
• 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 no more than 3 states including the dead
state (if there is one). [20]
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 = {aibj |i− j = 2, i, j > 0}.
1
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.
2. If L is a non-regular language and R is a regular language then L∩R
cannot be regular.
3. For every regular language there is a unique minimal NFA.
4. When we run the minimization algorithm on a DFA we cannot be sure
that it will always terminate.
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.
2