of Information Technology Faculty of Information Technology
Monash University
FIT2014 Theory of Computation FINAL EXAM
2nd semester, 2014
Instructions:
10 minutes reading time.
3 hours writing time.
No books, calculators or devices. Total marks on the exam = 120.
Working Space
Page 2 of 24
Question 1 (4 marks)
Use De Morgan’s Laws to prove that ¬((P ∧ Q) ∧ (¬P ∧ ¬Q)) is a tautology.
You may use other principles of propositional logic too, if you wish. But your proof must make significant use of De Morgan’s Laws.
Official use only
Page 3 of 24
Question 2 (6 marks)
Suppose you have predicates algorithm and TuringMachine with the following meanings, where variable X represents an arbitrary function:
algorithm(X): there is an algorithm for X. TuringMachine(X): there is a Turing machine for computing X.
(a) Write a universal statement in predicate logic with the meaning:
“Every function with an algorithm can be computed by a Turing machine.”
(b) By what name is this assertion usually known?
(c) What reasons are there for believing that this assertion is true?
Question 3 (3 marks)
Give a regular expression for the language of all strings over alphabet {a,b} whose first and last letters are different.
Official use only
Page 4 of 24
Question 4 (4 marks)
Let L be the language of nonempty strings over {a,b} that can start and finish with any letter but all other letters must be a. Draw a Finite Automaton to recognise L.
Question 5 (3 marks)
When converting a Nondeterministic Finite Automaton (NFA) to an equivalent Finite Au- tomaton (FA), how do you determine which states in the NFA are combined to form the single Start state in the FA?
Official use only
Page 5 of 24
Question 6
The following table describes a Finite Automaton with three states.
Find another FA that is equivalent to this one and has only two states. Write your two-state FA in the second table below.
YOUR ANSWER:
state a b Start 1 2 3 213 Final 3 1 2
Official use only
Page 6 of 24
Question 7 (4 marks)
Explain why the class of regular languages over the alphabet {a,b} is closed under in- terchange of a and b.
Definition:
If L is any language over the alphabet {a,b}, then the interchange of a and b forms a new language as follows: take every string in L, and replace every a by b and every b by a, simultaneously. So, for example, the string abb becomes baa.
Official use only
Page 7 of 24
Question 8 (7 marks)
Consider the following Context-Free Grammar. Its non-terminals are S and L.
(a) a derivation, and (b) a parse tree,
S→L (1) L → haL (2) L → aL (3) L→h (4)
for the string ahahaah .
Label each step in the derivation on its right by the rule used. Use the spaces below for
your answers.
Official use only
Page 8 of 24
Working Space
Page 9 of 24
Question 9 (3 marks)
Give a regular grammar for the language of positive integers represented in binary with leading bit 1. (The leading bit is the most significant bit, i.e., the leftmost bit.)
Question 10
Given the following Context-Free Grammar:
T → aTb T → aT T→b
(1) (2) (3) (4) (5)
complete the following diagram to give a Pushdown Automaton for the language generated by the grammar.
ε, ε → $ ε, ε → S ε, $ → ε 1234
Official use only
Page 10 of 24
Question 11 (10 marks)
This question uses the same grammar as the previous question.
Let L be the language generated by this grammar.
(a) Prove by induction that every string of the form ambn, where m ≥ n − 1 and n ≥ 1, belongs to L.
(b) Prove or disprove: some string in L has a derivation, using this grammar, that is neither a leftmost derivation nor a rightmost derivation.
Official use only
Page 11 of 24
Working Space
Page 12 of 24
Question 12
Recall that the Fibonacci numbers, Fn, are defined recursively as follows:
Fn = Fn−1+Fn−2 forn≥3.
The first few numbers in the sequence are 1,1,2,3,5,8,13,21,34,…
Note that the Fibonacci numbers are (after the first term) an increasing sequence of positive integers.
The language FIBONACCI is defined to be the set of all strings of the letter a whose length is a Fibonacci number. So,
FIBONACCI={aFn : n∈N}.
(a) Prove that the difference, Fn − Fn−1, between two consecutive Fibonacci numbers
increases as n increases, i.e., Fn − Fn−1 > Fn−1 − Fn−2 for all n ≥ 5.
(b) Using (a), prove that the language FIBONACCI is not context-free.
Official use only
Page 13 of 24
Question 13
Consider the following Turing machine.
Trace the execution of this Turing machine, writing your answer in the spaces provided on the next page.
The lines show the configuration of the Turing machine at the start of each step. For each line, fill in the state and the contents of the tape. On the tape, you should indicate the currently-scanned character by underlining it, and you should show the first blank character as ∆ (but there is no need to show subsequent blank characters).
To get you started, the first line has been filled in already.
Page 14 of 24
At start of step 1:
At start of step 2:
At start of step 3:
At start of step 4:
At start of step 5:
At start of step 6:
At start of step 7:
At start of step 8:
At start of step 9:
At start of step 10:
At start of step 11:
At start of step 12:
Official use only
Page 15 of 24
Question 14 (5 marks)
For each of the following decision problems, indicate whether or not it is decidable.
You may assume that, when Turing machines are encoded as strings, this is done using the Code-Word Language (CWL).
Decision Problem
Input: a Turing machine M, and a positive integer k. Question: Does M accept some input string of at most k letters?
Input: a Turing machine M, and a positive integer k. Question: Does the encoding of M have at least k letters?
Input: a Turing machine M, and a positive integer k. Question: When M is given an encoding of itself as input, does the computation go for at least k steps?
Input: a Turing machine M.
Question: Does M eventually print an encoding of M on the tape and then halt?
Input: a Turing machine M, and a string w. Question: Does M reject w?
your answer
(tick one box
in each row)
Undecidable
Undecidable
Undecidable
Undecidable
Undecidable
Official use only
Page 16 of 24
Working Space
Page 17 of 24
Question 15 (12 marks)
The Venn diagram on the right shows several classes of languages. For each language (a)–(l) in the list below, indicate which classes it belongs to, and which it doesn’t belong 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.
You may assume that, when Turing machines are encoded as strings, this is done using the Code-Word Language (CWL).
(a) The set of all graphs, encoded as adjacency matrices.
(b) The set of all 2-colourable graphs. (A graph is 2-colourable if each vertex can be coloured Black or White in such a way that adjacent vertices receive different colours.)
(c) The set of all 3-colourable graphs. (Definition is like 2-colourable, except now the available colours are Red, White and Black.)
(d) The set of all satisfiable Boolean expressions in Conjunctive Normal Form with at least two literals in each clause.
EQUAL, the set of all strings over alphabet {a,b} with an equal number of a’s and b’s. The set of all strings of parentheses such that the parentheses are correctly matched.
The set of all strings in which every letter is next to an identical letter.
The set of all Finite Automata that define the empty language. The set of all Turing Machines with polynomial time complexity.
reject or loop forever.
The set of all Turing machines which, when given themselves as input, eventually either
(k) The set of all Turing machines whose language of accepted strings is regular. (l) The set of all Turing machines that have ever been written.
Page 18 of 24
recursively enumerable (r.e.)
Context-Free
Official use only
Page 19 of 24
Question 16 (7 marks)
Prove that the following problem is undecidable.
Input: a Turing machine M and a positive integer t.
Question: Is there a string x which, if given as input to M, causes it to eventually erase everything on the tape (i.e., overwrite every letter by Blank), after which it never writes any other symbol?
You may use the fact that the halting problem is undecidable.
Question 17 (3 marks)
Explain how to obtain, from any language that is recursively enumerable but not decidable, another closely related language that is not recursively enumerable. (Proof is not required.)
Official use only
Page 20 of 24
Question 18 (15 marks)
Consider the language 3-EDGE-COLOURABILITY, which consists of all graphs G such that we can assign colours to the edges of the graph so that (i) each edge is Red, White or Black, and (ii) any two edges that are incident at a common vertex must get different colours.
Let H be the following graph.
(a) Construct a Boolean expression EH in Conjunctive Normal Form such that the satisfy- ing truth assignments for EH correspond to solutions to the 3-EDGE-COLOURABILITY problem on the above graph H (i.e., they correspond to colourings of the edges of H, using at most three colours and which give different colours to incident edges).
To do this, use variable names aR,aW,aB,bR,bW,bB,cR,cW,cB,dR,dW,dB, where vari- able eX is True if and only if edge e gets colour X (where e ∈ {a,b,c,d} and X ∈ {R,W,B}).
Page 21 of 24
(b) Give a polynomial-time reduction from 3-EDGE-COLOURABILITY to SATISFIABIL- ITY.
Official use only
Page 22 of 24
Question 19 (8 marks)
Prove that the HAMILTONIAN CIRCUIT problem is NP-complete, by reduction from HAMILTONIAN PATH. You may assume that HAMILTONIAN PATH is NP-complete.
Definitions:
A Hamiltonian path in a graph G is a path that includes every vertex of G. All the vertices on the path must be distinct.
A Hamiltonian circuit in a graph G is a circuit that includes every vertex of G. All the vertices on the circuit must be distinct.
HAMILTONIAN PATH
Input: Graph G.
Question: Does G have a Hamiltonian path?
HAMILTONIAN CIRCUIT
Input: Graph G.
Question: Does G have a Hamiltonian circuit?
Official use only
Page 23 of 24
END OF EXAMINATION
Page 24 of 24