Last name (please print)
First name (please print)
Student Number
western university
department of computer science
CS3331 – Foundations of Computer Science – Fall 2015 – Midterm Exam
Instructor: Dr. Lucian Ilie
Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165
This exam consists of 5 questions (11 pages, including this page), worth a total of 100 marks. No other materials
are allowed, such as cheat-sheets (or any other sheets), books, or electronic devices. All answers are to
be written in this booklet. Scrap work (not marked!) may be done on the back of each page or on pages 7–11. The
exam is 120 minutes long and comprises 30% of your final mark.
(1) 20pt
(2) 20pt
(3) 20pt
(4) 20pt
(5) 20pt
Grade
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 2
1. (20pt)
(a) Construct a NDFSM M1 equivalent with the regular expression ((a
∗ ∪ b∗)a)∗.
(b) Construct a DFSM M2 equivalent with M1.
(c) Minimize M2.
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 3
2. (20pt) Give a decision procedure for each of the following problems; argue that your procedure is correct:
(a) Given two regular languages R1 and R2, is it true that there are finitely many strings that belong to both
languages?
(b) Given a regular language R and a context-free language C, both over the alphabet {a, b}, is it true that C
contains exactly 2 strings that
– consist only of a’s and
– are not in R?
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 4
3. (20pt) Indicate whether each of the following statements is true or false; explain your answer:
(a) Given an infinite regular language R, any expression α such that L(α) = R must contain at least one
occurrence of the Kleene ‘∗’ operator.
(b) Every infinite regular language is the complement of a finite regular language.
(c) Every context-free grammar that generates the language {w(aa)∗wR | w ∈ {a, b}∗} is ambiguous.
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 5
4. (20pt) For each of the languages below, prove whether it is regular or context-free:
(a) L1 = {anbm | n,m ≥ 0, n 6= m}.
(b) L2 = {apaqap | p, q ≥ 0, p is prime}.
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 6
5. (20pt) Given the grammar G for balanced parentheses:
S → SS
S → (S)
S → ()
(a) Is G in Chomsky normal form? Prove your answer.
(b) Is G ambiguous? Prove your answer.
(c) Is it true that any grammar in Chomsky normal form is unambiguous? Prove your answer.
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 7
(scrap work)
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 8
(scrap work)
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 9
(scrap work)
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 10
(scrap work)
CS3331 – Midterm Exam – Tuesday, Nov. 3, 2015, 3:30 – 5:30pm, B&G165 11
(scrap work)