The University of Melbourne Practice Exam Paper
School of Computing and Information Systems
COMP30026 Models of Computation
Reading Time: 15 minutes Exam Duration: 3 hours
This paper has 14 pages, including this front page.
Calculators:
No calculators are permitted.
Examiners’ use:
Enrolment number (student number):
Authorised Materials:
This is a closed book exam. Electronic devices, including calculators and laptop computers are not permitted.
Instructions to Invigilators:
Students will provide answers in the exam paper itself. The exam paper must remain in the exam venue and must be returned to the examiner.
Instructions to Students:
This is not an actual exam paper. It is a practice paper which has been put together to show you the format that you can expect in the exam. Many aspects of this paper’s contents do not necessarily reflect the contents of the actual exam paper: The selection of topics, the number of questions or sub-questions, the perceived difficulty of individual questions, and the distribution of weights are all aspects that may be different. Hence, when preparing for the exam, you should cover the entire syllabus and not focus only on topics or question types used in this practice paper.
There are 9 questions. As in the exam, you should attempt them all. Of course your answers must be readable. Any unreadable parts will be considered wrong. You will find some questions easier than others; in the actual exam you should allocate your time accordingly. Marks are indicated for each question, adding to a total of 70.
The actual exam paper will be printed single-sided, so you will have plenty of space for rough work on the flip sides. Only what you write inside the dedicated boxes will be marked. Page 14 is overflow space, in case you need more writing space for some question.
123456789
Page 2 of 14
Question 1
A. Let ψ = (P ⇒Q)⇒R and ρ = P ⇒(Q⇒R). Using only propositional variables and
the connective ⇒, give a propositional formula φ such that • ψ |= φ
• ψ ̸≡ φ • φ |= ρ • φ ̸≡ ρ
B. The MacGuffin movie theatre has six showtimes per week. They prefer to show as many different films as possible. For the coming week they must choose amongst four films to show, namely p, q, r, and s. The distributors, however, pose many restrictions. The following conditions must be satisfied:
• Either both of r and s must be shown, or neither can be shown. • If neither r nor s is shown then p cannot be shown either.
• If q is shown then one, but not both, of r and s must be shown. • If r and s are both shown then q must be shown.
Tick the correct statement:
MacGuffin can show several different films that week
MacGuffin must show the same film all week, but has choice of which film to show MacGuffin must show the same film all week, with no choice of which film to show MacGuffin cannot show films that week
The conditions that have been posed are unsatisfiable
[COMP30026] [please turn over . . . ]
(8 marks)
Question 2
(8 marks)
Consider the closed first-order predicate logic formulas F, G, and H:
F : ∀xP(x,x)
G : ∀x ∀y (P(x,y)⇒P(y,x))
H : ∀x (P(x,x)∨∃y (¬P(y,x)))
A. Show that F ∧ G is satisfiable but not valid.
B. Determine whether F ∨ G is valid. Justify your answer.
C. Recall that φ |= ψ says that ψ is a logical
consequence of φ. Tick the most appropriate
statement from the list on the right:
[COMP30026]
[please turn over . . . ]
Page 3 of 14
G |= H H |= G G≡H None of the above
Question 3
Consider the following predicates:
(8 marks)
• C(x), which stands for “x is a cat”;
• D(x), which stands for “x is a dog”;
• M(x), which stands for “x is a mouse”;
• P (x), which stands for “x is a pasta dish”;
• E(x, y), which stands for “x eats y”;
• L(x, y), which stands for “x likes y”;
• F (x, y), which stands for “x is a friend of y”;
Page 4 of 14
A. Express, as a formula in first-order predicate logic (not clausal form), the statement “If a dog eats pasta dishes then no cat is a friend of that dog.”
B. Turn the following closed formula into clausal form:
∀x ∀y M(x) ∧ ∀z (D(z) ⇒ L(x, z)) ⇒ M(y) ⇒ ¬L(y, x)
[COMP30026] [please turn over . . . ]
Page 5 of 14
C. Using c for “Garfield” and b for “Harold”, we can express various statements about cats, mice and men in clausal form, as follows:
Garfield is a cat who likes pasta dishes: Garfield is a friend of Harold:
Harold likes anyone who likes Garfield: Whatever Garfield likes, he eats:
Cats like mice:
Friendship is mutual:
If you are a friend of somebody, you like them:
{C(c)},{¬P(x),L(c,x)} {F (c, b)}
{L(b, x), ¬L(x, c)} {¬L(c, x), E(c, x)}
{L(x, y), ¬C(x), ¬M(y)} {¬F (x, y), F (y, x)}
{¬F (x, y), L(x, y)}
Provide a proof by resolution to show that Harold likes himself, given the assumptions
expressed in the table.
[COMP30026] [please turn over . . . ]
Page 6 of 14
Question 4
A. For each of the following six strings, indicate (with a tick in the box) if the string is an
element of the language (ab)∗(ba)∗:
abba abbbba ababba
abaab bababa baab
B. Draw a DFA which recognises (ab)∗(ba)∗. Make sure your automaton is complete and
deterministic.
C. The class of regular languages is closed under intersection, so the language L = a∗b∗∩b∗a∗ is regular. Write a regular expression for L, making it as simple as you can.
[COMP30026] [please turn over . . . ]
(8 marks)
Question 5
Consider this NFA N:
Page 7 of 14
a b3b 1 2
ε4ε a
(8 marks)
5 b
A. Assuming N’s alphabet is {a,b}, use the subset construction method to transform N to an equivalent DFA. Label the DFA’s states so that it is clear how you obtained the DFA from the NFA.
B. Give the simplest possible regular expression for L(N), the language recognised by N:
C. Let G be the context-free grammar ({S, T }, {a, b}, R, S) with set R of rules
S→aSa T→aT S→bSb T→bT S→T T→ε
and let G′ be the context-free grammar ({S′}, {a, b}, R′, S′) with set R′ of rules S′ →aS′b
S′ → ε Give a regular expression for L(G) ∪ L(G′).
[COMP30026] [please turn over . . . ]
Question 6
(8 marks)
Page 8 of 14
A. Use generalised induction to show that every integer greater than 17 can be written as a sum of 4s and 7s. That is, for every n > 17, there exist non-negative integers i and j such that n = 4i + 7j.
[COMP30026] [please turn over . . . ]
Page 9 of 14
B. Let G be the following ambiguous context-free grammar:
S → ε|Saaaa|Saaaaaaa
Describe a string that demonstrates the ambiguity of G, that is, a string which has two different parse trees.
C. Find an unambiguous context-free grammar equivalent to G. You may use the result in part A even if you didn’t answer that part.
[COMP30026] [please turn over . . . ]
Page 10 of 14
Question 7
A. Let F and G be sets of sets. Using the membership predicate ∈ together with quantifiers,
we can express set relation in logical form. For example, F ⊆ G becomes ∀x (∃y (y ∈ F ∧ x ∈ y) ⇒ ∀z (z ∈ G ⇒ x ∈ z))
Give a logical translation of F ⊆ G.
B. Show that, for all languages L and M, (L \ M)∗ ̸⊆ (L∗ \ M∗).
C. Give an example of languages L and M for which (L∗ \ M∗) ⊆ (L \ M)∗ fails to hold.
[COMP30026] [please turn over . . . ]
(8 marks)
Question 8
(8 marks)
Page 11 of 14
Let Nn = {0, 1, 2, . . . , n}. Assume that functions are given as binary relations (or, when we represent functions in Haskell, as lists of pairs). The following are two example functions from N6 to N6:
g1 = {(5, 5), (2, 3), (4, 5), (0, 0), (1, 0)}
g2 = {(5, 5), (2, 3), (4, 5), (3, 4), (0, 0), (1, 0), (6, 0)}
Afunctionf:X→Xisidempotentifff(x)=f(f(x))forallx∈X.Notethatg1 isnot total, and g2, while a total function, is not idempotent.
For this question you can make use of functions from Haskell’s Prelude, as well as functions from the List library, including, if needed, sort and nub (the latter removes duplicates from a list).
A. Write a Haskell function
isTotalFct :: Int -> [(Int,Int)] -> Bool
so that ‘isTotalFct n r’ decides whether the binary relation r represents a total function from Nn to Nn.
[COMP30026] [please turn over . . . ]
Page 12 of 14
B. Write a Haskell function
isIdempotent :: Int -> [(Int,Int)] -> Bool
so that ‘isIdempotent n r’ decides whether r is idempotent. For this part you can assume that r is known to be a total function from Nn to Nn.
[COMP30026] [please turn over . . . ]
Question 9
(6 marks)
Page 13 of 14
Construct a Turing machine M (over alphabet {a,b}) which will decide the language A consisting of all strings of length 4 or greater, having a as their fourth last symbol. More
formally,
A=w w∈{a,b}∗ haslength4ormore, and the fourth last symbol in w is a
For example, abba and bbaaab are in A, but baba and aaa are not. You should present the Turing machine as a state diagram. You can leave out its reject state, with the understanding that missing transitions are transitions to the reject state. However, indicate clearly the initial state q0 and the accept state qa.
[COMP30026] [end of exam]
Overflow space
Page 14 of 14
Use this page if you ran out of writing space in some question. Make sure to leave a pointer to this page from the relevant question.