# CS代考 FIT2014 Theory of Computation FINAL EXAM – cscodehelp代写

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