Computer Science
EXAMINATION
Models of Computation
EXAM WRITING TIME: 3 hours
READING TIME: 10 minutes
计算机科学代考 Using the equivalences from the tables provided with the exam, put the following formula into conjunctive normal form: (p ∨ ¬q) → (¬r ∧ s).
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: 计算机科学代考
- 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
- Start by typing your student ID at the top of the first page of your submission.Do not type your name.
- Submit only your answers to the questions. Do not copy the questions. Start each of the five problems on a new page.
- If the required level of justification is not stated, you should briefly justify your answer.
For examiner use only:
| Problem | 1 | 2 | 3 | 4 | 5 | Total |
| Marks | ||||||
| Out of | 13 | 11 | 14 | 8 | 4 | 50 |
Problem 1. These questions are about Propositional Logic. If the required level of justification is not stated, you should briefly justify your answer.
a)Is it the case that the formulas p (p q) and p (p q) are logically equivalent?[2 marks]
b)Using the equivalences from the tables provided with the exam, put the following formula into conjunctive normal form: (p ∨ ¬q) → (¬r ∧ s). Youmay type your answer in a table or as a sequence of lines, or you may draw the table and insert it into your pdf. No marks will be awarded for proofs that do not use the rules taught in this course and summarised in the tables provided with the exam.[3 marks] 计算机科学代考
c)Prove the following consequent in naturaldeduction:
s → ¬r, (¬s ∧ r) → m € (s ∨ ¬m) → ¬r
You may type your answer in a table or as a sequence of lines, or you may draw the table and insert it into your pdf. No marks will be awarded for proofs that do not use the rules taught in this course and summarised in the tables provided with the exam.[4 marks]
d)Write a formula in CNF over variables x1, x2, x3, that expresses that x1+x2 + x3 is even, i.e., that the number of variables assigned true is even. [2 marks] 计算机科学代考
e)The following algorithm transforms a formula F in CNF into a formula Fj. What is the syntactic and semantic relationship between F and Fj? In other words, what does the following algorithmachieve?
Given a formula F in CNF, return the formula Fj that is formed by simul- taneously replacing every by , and every by , and every literal by its negation (thus atoms x are replaced by x, and literals x are replaced by x).[2 marks]
Problem 2. These questions are about Context-free Languages. If the required level of justification is not stated, you should briefly justify your answer.
a)Explain how to check if c is derivable by a given CFG. [1 mark]
b)Given a CFG for L, show how to construct a CFG for L+. Recall that L+ is defined to beLL∗.[2 marks]
c)Considerthe language generated by the following context-free grammar
G: [4 marks]
S → AT | c
T → TA | TB | c
A → a B → b
Is the grammar G ambiguous? 计算机科学代考
Give a short English description of the language L(G). Is the language L(G) regular?
d)Give a CFG that generates the following language, and give a brief justifi- cation of eachrule: [4 marks]
{u#v#w : u, v, w ∈ {a, b}∗, |v| ≥ |u| + |w|}
Problem 3. These questions are about Regular Languages. If the required level of justification is not stated, you should briefly justify your answer. 计算机科学代考
a)Isit the case that every NFA has more than one run on every string? [1 mark]
b)Consider the DFA M with states Q = 0, 1, 2 ,Σ = a, b , q0 = 0, F = 1 , and δ is as follows: [3 marks]
| a | b | |
| 0 | 0 | 1 |
| 1 | 2 | 0 |
| 2 | 2 | 2 |
Give a short English description of L(M) and a regular expression for L(M). No additional justifications are needed.
c)A left-linear grammar G is a CFG whose rules are of the form A a and A Ba where A, B are variables and a is a terminal or c (you saw in tutorials that left-linear grammars only generate regular languages). Apply the following transformation to the grammar: keep every rule of the form A a, but replace every rule of the form A Ba by A aB. Call the resulting grammar H. What is the relationship between L(G) and L(H)? Give a detailed justification of your answer (e.g., comparing derivations in G with those inH).[3 marks]
d)What is wrong with the following argument that claims to show that every regular language is recognised by an NFA with exactly one accepting state and noc-transitions: [3 marks] 计算机科学代考
- Since L is regular, it is recognised by some DFA M, say with accepting statesF.
- Build an equivalent NFA N by adding a new state q to M, add c– transitionsfrom every state in F to q, and make q be the only accepting state.
- Remove c-transitions from N using the method taught in lectures.
e)Show that if L ⊆ Σ∗ is regular then also Lj = {uvR : uv ∈ L} ⊆ Σ∗ is Here vR is the reverse of the string v. For instance, if abcd ∈ L (for a, b, c, d ∈ Σ) then abcd, abdc, adcb, dcba ∈L‘.[4 marks]
Problem 4. These questions are about Turing Machines. If the required level of justification is not stated, you should briefly justify your answer. 计算机科学代考
a)Is every language inNP?[1 mark]
b)Is the set of regular expressions over Σ = {a, b}Turing-decidable?[2 marks] 计算机科学代考
c)Let L be the set of encodings (G, K) of undirected graphs G = (V, E) and K ∈ N such that V can be partitioned into K non-empty pieces, each of which is a clique of G. Show that L ∈NP. [2 marks]
d)Let L be the set of encodings N, w where N is an NFA without c transi- tions such that N accepts w. Show that L is inP. [3 marks]
Problem 5. These questions are about Predicate Logic. No additional explana- tion is needed. 计算机科学代考
Consider the domain of geographical regions, that includes the regions A, B and C (amongst others), and the following predicates:
- in(x, y)is a binary predicate expressing that region x is inside region y.
- eq(x,y) is a binary predicate saying that x and y are the same region.
- border(x, y) is a binary predicate saying that the regions x and y share a border.
Use this to write the following statements in predicate logic:
a)Everyregion that borders A or B is inside the region C. [1 mark] 计算机科学代考
b)Every region borders some other region. [1 mark]
c)Iftwo regions share a border then one is inside the other. [1 mark]
d)Ifa region has every other region inside it, that region is C.[1 mark]
