计算机代写｜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 xi for 1 ≤ i ≤ n. The meaning of xi being true is that i ∈ X. Write a formula ΦG in CNF over the variables x1, x2, · · · , xn 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 = (F1 ∧ F2) then check if both F1 and F2 are satisfifiable. If they are,then return “Satisfifiable”, else return “Unsatisfifiable”.

3. If F = (F1 ∨ F2) then check if either F1 or F2 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.