CMPT 364 — Final Exam
2019–2020 T2
Thursday April 23, 2020, 5pm – Friday April 24, 5pm (all SK time)
/72 marks
Academic Integrity Commitment Statement
Please read the following rules, and sign the Academic Integrity Commitment Statement at the bottom.
Rules:
• The exam will be open book.
• Any materials available on Moodle (notes, videos, assignments) may be used. No other resources are allowed including anything found or searched for on the web, or materials given to you from anyone else. The Moodle Forums cannot be used (nor can any other forum), either to ask questions to me, or between people.
• The exam is to be completed individually. Collaboration is not allowed. Specifically, you are not allowed to discuss or share the questions or potential answers with anyone, including other students in this course. Please report any concerns about unpermitted collaboration to the instructor at any time.
• Please hand in your exam in the usual way that assignments are handed in, on Moodle, in the section called “Exam Handin”. This will close Friday at 5pm, as 24 hours is more than enough. If something is not working technically, then please email your completed exam to me at mcquillan@cs.usask.ca.
• You can either type in your responses, or you could handwrite, convert to a PDF, and hand that in. I’m totally ok with handwriting as long as it’s legible. Please no jpegs or non-PDF image files. I want one PDF containing all the solutions, plus one PDF with this signed form (or one combined PDF).
• Despite the 24 hours, I will be targeting 3 hours as a reasonable time to complete it (assuming that all the work and preparation from the course has been properly done beforehand).
• I will make myself available on Zoom at the following times: Thursday, 5:00–5:30, 7:30–8:30, Friday, 10:00–11:00, 4:00–5:00. I have enabled “waiting room” on Zoom, and I will only let people in from the waiting room one person at a time. Therefore, the questions and answers will be private and individual. You can also email me questions. https://zoom.us/j/390156775?pwd=Z1Q3ZURJZnd5bS91SzVYUjFCZzZ4dz09
I acknowledge that I have followed the rules outlined by my instructor above, and those of the University of Saskatchewan Academic Misconduct Policy.
Name: Student #: Date #:
1
1. (13 marks) Consider the following DFA M = (Q,Σ,δ,q0,F) with Σ = {0,1},Q = {q0,q1,q2,q3},F = {q0}, and δ(q0,0) = q1,δ(q0,1) = q2,δ(q1,0) = q3,δ(q1,1) = q0,δ(q2,0) = q0,δ(q2,1) = q3,δ(q3,0) = q3, δ(q3, 1) = q3.
(a) Draw a transition diagram for M.
(b) Provide a language description for the language accepted by M.
(c) Prove that L(M) is equal to the language you obtained in part b.
2. (8 marks) Consider the following language over {a, b, c, 0, 1, 2} (the ‘or’ is inclusive as usual, 0 is even,
and also divisible by 3):
L= {wm| w∈{a,b,c}∗, eithermis0ifthenumberofa’sinwiseven,or
m is 1 if the number of b’s is odd, or m is 2 if the number of c’s is divisible by 3}. (a) Construct an ε-NFA (ε transitions optional) accepting L.
(b) Construct a regular expression accepting L (does not have to be with algorithmic conversion).
3. (10 marks) Convert the following DFA to a regular expression by following the algorithm described in class. Show all your work. You only need to provide the regular “sub” expressions if they will help you find the finished regular expression. You also need to simplify. Simplify each subexpression using any law discussed in class (including those derived on the board). To summarize, those were 1) (ε+R)∗ =R∗,2)S·R∗ =R∗ (andR∗·S=R∗)ifL(S)⊆L(R∗)andε∈S,and3)S+R=R(and R + S = R) if L(S) ⊆ L(R).
a
q1
b
a
c
q0
c
b
2
4. (12 marks) Consider a new model that is like a DFA but with an additional bounded memory. A DFA
with n-bit Boolean store is a tuple M = (Q, Σ, δ, q0, F ), where Q, Σ, q0, F are just like DFAs, but nn
δ is a function from Q×Σ×{0,1}×···×{0,1} to Q×{0,1}×···×{0,1}. An example of such a transition, where n = 3, would be δ(q, a, 0, 0, 0) = (p, 0, 0, 1). Furthermore, define δˆ just like for DFAs; that is,
• δˆ(q,ε,b1,…,bn) = (q,b1,···,bn) for all q ∈ Q,bi ∈ {0,1},1 ≤ i ≤ n; and
• δˆ(q,wa,b1,…,bn) = δ(p,a,c1,…,cn) where δˆ(q,w,b1,…,bn) = (p,c1,…,cn), for all q ∈ Q,bi ∈
{0, 1}, 1 ≤ i ≤ n.
Lastly, the language accepted by M,
n
∗ ˆ
L(M) = {w | w ∈ Σ ,δ(q0,w,0,…,0) = (qf,b1,…,bn),qf ∈ F,bi ∈ {0,1},1 ≤ i ≤ n}.
(a) Construct an algorithm that could be used to show that the languages accepted by n-bit Boolean store DFAs are equal to the family of regular languages (proof of correctness not necessary — just the algorithm).
(b) Assuming that part a) is correct, prove that the language {0i1j2k | i ≥ 0,j ≥ k ≥ 0} cannot be accepted by any DFA with n-bit Boolean store.
5. (5 marks) Consider the context-free grammar G = ({S, R, T }, {a, b}, P, S), where P contains:
• S→R|T,
• R→aRb|ε,
• T → aaT b | ε.
(a) Describe the language this generates?
(b) Convert it to a PDA accepting the same language by using the algorithm described in the notes — show all your work.
6. (10 marks) Consider the PDA M = ({p, q}, {0, $}, {Z0, X}, δ, p, Z0, {q}), where
• δ(p,0,Z0)={(p,XZ0)}, • δ(p,0,X)={(p,XX)}, • δ(p,$,X)={(q,X)},
• δ(q,0,X)={(q,ε)}.
(a) What language does it accept by final state?
(b) Create a context-free grammar that accepts L(M) (using any method you choose to construct it).
(c) Draw a parse tree using your grammar that gives a yield of 000$00.
7. (6 marks) Prove that the following language is not context-free: L = {x$v$x | x, v ∈ {a, b}∗}.
8. (8 marks) Let b(i) be the number i in binary without any leading zeros (i.e. 101 is the number for 5, but not 0101). Construct a multitape Turing machine accepting the language:
{b(1)#b(2)# · · · #b(i)# | i ≥ 1}.
Please add comments to the transitions of your Turing machine to make it easier to follow how it works.
3
9. (6 marks) Say that we already know the following problem is NP-complete, called the Hamiltonian Path Problem: Given an undirected graph G = (V,E), is there a path in G that uses every vertex exactly once?
Now consider the following problem, which we call the Source-Sink Hamiltonian Path Problem: Given an undirected graph G = (V, E) and two vertices s and t in V , does there exist a path from s to t that goes through each vertex of the graph exactly once?
What steps would be needed in order to prove that the Source-Sink Hamiltonian Path Problem is NP-complete (by using the Hamiltonian Path Problem)? You do not need to prove it. But anywhere where an algorithm is needed, say what the inputs and outputs are, and indicate what proofs would be needed.
4