comp2022 final exam (s2, 2022)
C:\Documents and Settings\Dennis\Desktop\Exam Typing
Instructions.doc
Copyright By PowCoder代写 加微信 powcoder
Page 2 of 4
01/27 Semester 2, 2005 Page X of XY
Faculty of ECONOMICS & BUSINESS
ECON2002 – INTERMEDIATE MICROECONOMICS
Duration: 2h30m
Reading time: 10 mins
SEAT NUMBER: _______________________________
FULL NAME: _______________________________
SID: _______________________________
INSTRUCTIONS TO CANDIDATES
Answer each Section in a separate book……
Etc etc etc
Paper Code: This
no. can be found
on the Spec sheet.
This information is only necessary if
the paper is NOT TO BE REMOVED
FROM EXAM ROOM.
CONFIDENTIAL EXAM PAPER
This paper is not to be removed from the exam venue.
Computer Science
EXAMINATION
Semester 2 – Main, 2022
comp2022 Models of Computation
EXAM WRITING TIME: 3 hours
READING TIME: 10 minutes
EXAM CONDITIONS:
This is an OPEN book examination. You are allowed to use passive information
sources (i.e., existing written materials such as books and websites); however,
you must not ask other people for answers or post questions on forums; always
answer in your own words. You must not reveal the questions to anyone else.
All work must be done individually in accordance with the University’s “Aca-
demic Dishonesty and Plagiarism” policies.
INSTRUCTIONS TO STUDENTS:
1. Type your answers in your text editor and submit a single PDF via Canvas; all
prose must be typed. Figures/diagrams can be rendered any way you like (hand
drawn, latex, etc), as long as they are perfectly readable and part of the submitted
2. Start by typing your student ID at the top of the first page of your submission. Do
not type your name.
3. Submit only your answers to the questions. Do not copy the questions.
4. Start each of the five problems on a new page.
5. If the required level of justification is not stated, you should briefly justify your
For examiner use only:
Problem 1 2 3 4 5 Total
Out of 12 14 12 6 6 50
page 1 of 6
https://sydney.edu.au/students/academic-dishonesty.html
https://sydney.edu.au/students/academic-dishonesty.html
comp2022 final exam (s2, 2022)
Problem 1. These questions are about Regular Languages. They are worth a
total of 12 marks. If the required level of justification is not stated, you should
briefly justify your answer.
[2 marks]Show that if S, T are regular expressions then there is a regular expression
for L(S) ∩ L(T).
[2 marks]Give an NFA for the language of strings over alphabet 0, 1 that have 001
as a substring. You may draw the NFA or type the transition relation. No
additional explanation is needed.
[4 marks]Give a regular expression for the language {w ∈ {0, 1}∗ : w ̸= 01}. No
additional explanation is needed.
[4 marks]Fix Σ = {0, 1}. Consider the operation del that maps a string u to the string
in which every 0 is deleted. So, e.g., del(0) = ϵ, del(01101) = 111, del(1) =
1, and del(ϵ) = ϵ. For a language L ⊆ Σ∗, let del(L) = {del(u) : u ∈ L}.
Explain why if L is regular, then del(L) is regular.
page 2 of 6
comp2022 final exam (s2, 2022)
Problem 2. These questions are about Turing Machines and Complexity. They
are worth a total of 14 marks. If the required level of justification is not stated,
you should briefly justify your answer. If you are describing a TM, give a high-
level description unless otherwise specified.
[4 marks]Let M be a decider over input alphabet {0, 1}. Give a high-level description
of a TM that decides the language L(M) ∩ L(0∗).
[2 marks]Explain why the non-decidable languages are closed under complement.b)
[4 marks]We know that every context-free language is in P. Explain why if L1, L2 are
context-free languages, then L1 ∩ L2 is in P.
[4 marks]Fix Σ = {0, 1}. Consider the operation del that maps a string u to the string
in which every 0 is deleted. So, e.g., del(0) = ϵ, del(01101) = 111, del(1) =
1, and del(ϵ) = ϵ. For a language L ⊆ Σ∗, let del(L) = {del(u) : u ∈ L}.
Show that if L is decidable, then del(L) is recognisable.
page 3 of 6
comp2022 final exam (s2, 2022)
Problem 3. These questions are about Propositional Logic. They are worth a
total of 12 marks. If the required level of justification is not stated, you should
briefly justify your answer.
[2 marks]Are the formulas p ∧ p and p ∨ p logically equivalent? Give a short expla-
nation/justification of your answer.
[2 marks]Using the equivalence laws from the Table provided with the exam, show
that ((A ∧ B) ∧ C) → A ≡ ⊤.
[2 marks]Is it true that if the formula F ∨ G is valid then either F is valid or G is
valid? Give a short explanation/justification of your answer.
[2 marks]Write a CNF formula over variables p, q, r that says that the number of true
variables is even. No additional explanation is needed.
[4 marks]Prove the following in Natural Deduction:
(p ∨ q), (r → ¬p) ⊢ (q → p) → ¬r
Type your answer in a table or as a sequence of lines. No marks will be
awarded for proofs that do not use the rules taught in this course and
summarised in the Table provided with the exam.
page 4 of 6
comp2022 final exam (s2, 2022)
Problem 4. These questions are about Predicate Logic. They are worth a total
of 6 marks. If the required level of justification is not stated, you should briefly
justify your answer.
[4 marks]Consider the units of study (UoS) domain, that includes the UoS COMP2022,
COMP2922, and INFO1103 (amongst others), and the following predicates:
1. prerequisite(x, y) is a binary predicate expressing that x is a pre-
requisite for y.
2. prohibition(x, y) is a binary predicate saying that x is a prohibition
Use this to write the following statements in predicate logic:
1. COMP2922 is a prohibition of COMP2022.
2. Every UoS that is a pre-requisite for COMP2022 is also a pre-requisite
for COMP2922.
3. INFO1103 has no pre-requisite.
4. If two UoS have the same pre-requisites then they have the same pro-
hibitions.
No additional explanation is needed.
[2 marks]Prove the following in Natural Deduction:
∀x(P(x) → Q(x)), ∃xP(x) ⊢ ∃xQ(x)
Type your answer in a table or as a sequence of lines. No marks will be
awarded for proofs that do not use the rules taught in this course and
summarised in the Table provided with the exam.
page 5 of 6
comp2022 final exam (s2, 2022)
Problem 5. These questions are about Context-free Grammars. They are worth
a total of 6 marks. If the required level of justification is not stated, you should
briefly justify your answer.
[4 marks]Consider the following grammar:
S → AS | SB | ϵ
A → Aa | ϵ
B → bB | ϵ
Describe the language of the grammar, and show that the grammar is
ambiguous.
[2 marks]Fix Σ = {0, 1}. Provide a context-free grammar for the language
{u0v1w : |v| = |u|+ |w|}
For instance, taking u = 01, w = 11, v = 1100 we get that u0v1w =
0101100111 is in the language. No additional explanation is needed.
page 6 of 6
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com