Monash University Faculty of Information Technology
FIT2014 Theory of Computation FINAL EXAM
2nd semester, 2013
Instructions:
10 minutes reading time.
3 hours writing time.
No books, calculators or devices. Total marks on the exam = 120.
Working Space
Question 1 (4 marks)
You are hunting a mouse in your wardrobe.
Suppose we have three propositions, C, H and S, with the following meanings:
C: The mouse is in your coat. H: The mouse is in your hat. S: The mouse is in your shoe.
Use C, H and S to write a proposition, in Conjunctive Normal Form, that is True precisely when the mouse is in one of these three locations: your coat, your hat or your shoe.
Question 2 (4 marks)
Suppose you have the predicates computer and utm with the following meanings: computer(X): X is a computer.
utm(X): X can simulate any Turing machine.
(a) Write a universal statement in predicate logic with the meaning:
“Everything that can simulate any Turing machine is a computer.”
(b) What additional fact would you need to know, to be able to use this statement (and nothing else) to prove that the object myPhone is a computer? (Express this fact as an atomic sentence in predicate logic.)
Question 3 (4 marks)
(a) Write down all strings of at most 8 letters, over alphabet {a,b}, that match the regular expression (((ab) ∪ (ba))a)∗.
(b) Give an NFA with at most 7 states that recognises the language described by this regular expression.
Question 4 (3 marks)
A language over alphabet {a,b} is said to be cofinite if it contains all strings over that alphabet except for some finite number of strings. Prove that every cofinite language is regular.
Question 5 (7 marks)
Given the following NFA, convert it to a Finite Automaton that recognises the same language.
Represent the FA by filling in the table below.
state Start
Question 6 (3 marks)
Suppose you have, at your disposal, algorithms to convert NFAs to FAs, FAs to Regular Expressions and Regular Expressions to NFAs.
Explain how you would design and implement a lexical analyser to recognise tokens that match a particular regular expression. (In this explanation, do not give code, but do explain where the code comes from.)
Question 7
Use the Pumping Lemma to prove that the language {ambn :m
Question 9
Consider the following Context-Free Grammar
Prove by induction that every string of the form ambn, where m ≥ 0 and n ≥ 0, can be generated by this grammar.
Working Space
Question 10
Consider the following Context-Free Grammar.
(1) (2) (3) (4) (5) (6)
(a) a derivation, and (b) a parse tree,
S → aBa B → BB B→Q B→R Q→q R→r
for the string aqrqa, labelling each step in the derivation on its right by the number of the rule used. Use the spaces below for your answers.
(a) Derivation:
(b) Parse tree:
Question 11 (5 marks)
Given the following Context-Free Grammar:
S→A (1) A → AbA (2) A→a (3)
complete the following diagram to give a Pushdown Automaton for the language generated by the grammar.
ε, ε → $ ε, ε → S ε, $ → ε 1234
Question 12 (4 marks)
State two important results that can be proved using the Chomsky Normal Form for Context- Free Grammars.
Question 13 (6 marks) The 2’s complement of a binary string is formed as follows. Flip each bit (i.e., change 0 to 1, and 1 to 0) until you get to the last 1. Keep that last 1, and all 0s after it, unchanged.
For example, if the string is 0110100, then its 2’s complement is 1001100. Draw a Turing machine to compute the 2’s complement of any binary string.
Question 14 (4 marks)
(a) State the Church-Turing thesis.
(b) Give two reasons why the Church-Turing thesis is widely accepted.
Question 15 (4 marks)
For each of the following decision problems, indicate whether or not it is decidable.
Decision Problem
Input: a Turing machine M.
Question: Does M eventually halt, if the input is the number 17?
Input: a Turing machine M, and a string w.
Question: If M is run with input w, does it halt in at most 17 steps?
Input: a Turing machine M.
Question: Does M have at least 17 states?
Input: a Turing machine M.
Question: Is the language recognised by M finite?
your answer
(tick one box
in each row)
Undecidable
Undecidable
Undecidable
Undecidable
Question 16 (10 marks)
The Venn diagram on the next page shows several classes of languages. For each language (a)–(j) in the list below, indicate which classes it belongs to, by placing its corresponding letter in the correct region of the diagram.
If a language does not belong to any of these classes, then place its letter above the top of the diagram.
{anbn :n>0} {anbncn : n > 0}
{anbncndn : n > 0}
The set of all graphs containing a Hamiltonian circuit.
The set of all graphs containing no circuit.
The set of all correctly formed arithmetic expressions that only use positive integers
(g) The set of all (encodings of) Turing machines that eventually halt, when given them- selves as input.
(h) The set of all (encodings of) Turing machines that loop forever, when given themselves as input.
(i) The set of all strings that have ever caused any real computer to eventually halt.
(j) The set of all Context-Free Grammars that define an empty language.
and the symbols + and −.
recursively enumerable (r.e.)
Context-Free
Question 17
Prove that the following problem is undecidable. Input: a Turing machine M, and a string x.
Question: If M is run on input x, does it eventually accept x? You may use the fact that the Halting Problem is undecidable.
Question 18 (5 marks)
Let L be a recursively enumerable (r.e.) language. We saw in lectures that there is an enumerator that enumerates L. Here is an attempt at constructing an “enumerator” for L.
Let M be a Turing machine whose set of accepted strings is L. Construct another Turing machine E which does the following.
For each string w = ε, a, b, aa, ab, . . ., in turn (i.e., sequentially): {
Simulate the execution of M on input w. If M accepted w, then output w. Continue to the next iteration.
(a) What is wrong with this attempt at an enumerator?
(b) Indicate briefly what would need to be done to fix it. (You don’t need to say in detail how to fix it, but just indicate in general terms what to do.)
Question 19 (4 marks)
Suppose M is a Turing machine with time complexity O(n3), and that U is a Universal Turing Machine that can simulate any t-step Turing machine computation in at most t4 steps.
Find an upper bound, in big-O notation and with proof, of the time taken by U to simulate the computation by M on an input of size n.
Question 20 (4 marks)
Prove that the class of regular languages is a subset of the class P.
Question 21 (2 marks)
Suppose that a particular decider has polynomial time complexity. When inputs are suffi- ciently large, what happens to its running time when the length of the input is doubled?
Choose one of the answers (a)–(g) below, by circling the appropriate letter.
If more than one answer holds, you must choose the strongest (i.e., most precise) correct answer.
(a) (b) (c) (d) (e) (f) (g)
It is raised to at most a constant power.
It is increased by at most a constant factor.
It is increased by at most a constant amount. It is at most squared.
It is at most doubled.
It increases by at most 2.
It doubles after two years, according to Moore’s Law.
Question 22 (4 + 6 + 7 + 2 + 2 = 21 marks)
Consider the language NO MONOCHROMATIC TRIANGLE, which consists of all graphs G such that we can assign colours to the edges of the graph so that (i) each edge is either Black or White, and (ii) there is no triangle (i.e., cycle of length 3) in the graph which is monochromatic (i.e., all its edges have the same colour).
(a) Prove that the language NO MONOCHROMATIC TRIANGLE is in NP.
Now, let W be the following graph.
(b) Construct a Boolean expression EW in Conjunctive Normal Form such that the satis- fying truth assignments for EW correspond to solutions to the NO MONOCHROMATIC TRIANGLE problem on the above graph W (i.e., they correspond to colourings of the edges of W which have no monochromatic triangle).
(c) Give a polynomial-time reduction from NO MONOCHROMATIC TRIANGLE to SAT- ISFIABILITY.
(d) State the Cook- .
(e) Given the facts stated so far in this question:
What else, if anything, would you need to prove, in order to show that NO MONOCHRO- MATIC TRIANGLE is NP-complete?
END OF EXAMINATION