# 计算机代写｜Comp2022 Models of Computation final exam (s2, 2021)

**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 PDF.

2. Start by typing your student ID at the top of the fifirst page of your submission. Do **not **type your name.

3. Submit only your answers to the questions. Do **not **copy the questions. Start each of the fifive problems on a new page.

4. If the required level of justifification is not stated, you should brieflfly justify your answer.

**Problem ****1****. **These questions are about Propositional Logic. If the required level

of justifification is not stated, you should brieflfly justify your answer.

Is it the case that the formulas *p **→ *(*p **→ **q*) and *q **→ *(*q **→ **p*) are logically [2 marks] equivalent?

a) Using the equivalences from the tables provided with the exam, show that [3 marks]

((*p **∨ *(*q **∨ **r*)) *∧ *(*r **∨ ¬**p*)) *≡ *((*q **∧ ¬**p*) *∨ **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.

b)[4 marks] Prove the following consequent in natural deduction:

*b **→ **d*, *d **→ **a*, *c **` **a **∨ *(*b **→ ¬**c*)

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.

c)An undirected graph *G *= (*V*, *E*) is called *bipartite *if there is a subset *X **⊆ **V *[3 marks] such that every edge in *G *has one endpoint in *X *and the other not in *X*.

Say *V *= *{*1, 2, *· · · *, *n**}*. To encode the problem of deciding if a graph is bipartite or not, you introduce variables *x**i *for 1 *≤ **i **≤ **n*. The meaning of *x**i *being true is that *i **∈ **X*. Write a formula Φ*G *in CNF over the variables *x*1, *x*2, *· · · *, *x**n *that expresses that the graph is bipartite, i.e., Φ*G *is satisfifiable if and only if *G *is bipartite.

What is wrong with the following recursive algorithm deciding whether a [2 marks] given propositional formula *F *in NNF is satisfifiable or not:

1. If *F *is an atom or the negation of an atom, return ”Satisfifiable”.

2. If *F *= (*F*1 *∧ **F*2) then check if both *F*1 and *F*2 are satisfifiable. If they are,then return “Satisfifiable”, else return “Unsatisfifiable”.

3. If *F *= (*F*1 *∨ **F*2) then check if either *F*1 or *F*2 are satisfifiable. If at least one is, then return “Satisfifiable”, else return “Unsatisfifiable”.

**Problem ****2****. **These questions are about Context-free Languages. If the required level of justifification is not stated, you should brieflfly justify your answer.

[4 marks]

Consider the following CFG in CNF:

*S **→ **AX **| **AB **| **e *

*T **→ **AX **| **AB *

*X **→ **TB *

*A **→ **a *

*B **→ **b *

1. State the variables and terminals of the grammar.

2. Which variables derive the string *aabbb*?

3. The CYK algorithm computes a 2D-array *Table *where *Table*(*i*, *j*) are the variables that derive the substring starting at position *i *and ending at position *j*. In order to compute *Table*(2, 5), which entries of the table are directly needed to be checked/computed?

a)Explain why if *L *is a regular language then *L *is generated by an unam- [2 marks] biguous context-free grammar.

b)Write a context-free grammar for the following language: the set of strings [4 marks] of the form *u*#*v *where *u*, *v **∈ {**a*, *b**} **∗ *and *|**u**| *= *|**v**| *and the reverse of *u *is not equal to *v*.