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 = {ai bj |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