Monash University Faculty of Information Technology
FIT2014 Theory of Computation FINAL EXAM SOLUTIONS
2nd semester, 2014
Instructions:
Copyright By PowCoder代写 加微信 powcoder
10 minutes reading time.
3 hours writing time.
No books, calculators or devices. Total marks on the exam = 120.
Answers in blue.
Comments in green.
Working Space
Page 2 of 34
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.
¬((P ∧Q)∧(¬P ∧¬Q))
= ¬(P ∧Q)∨¬(¬P ∧¬Q)
= (¬P∨¬Q)∨(¬¬P∨¬¬Q) = (¬P ∨¬Q)∨(P ∨Q)
= ¬P∨¬Q∨P∨Q
= ¬P∨P∨¬Q∨Q
= True ∨ True
Official use only
Page 3 of 34
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.”
Equivalent answer:
∀X : algorithm(X) ⇒ TuringMachine(X)
∀X : ¬algorithm(X) ∨ TuringMachine(X)
(b) By what name is this assertion usually known?
Church-Turing thesis
(c) What reasons are there for believing that this assertion is true?
• So far, algorithms that people try to program have turned out to be programmable. • No counterexample. (I.e., there is no algorithm which does not seem to be pro-
grammable in principle.)
• Different approaches to computability end up in agreement.
Recursive functions, and lambda calculus, both arrive at the same class of computable func- tions as those captured by Turing machines.
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.
(a(a∪b)*b)∪ (b(a∪b)*a)
It’s ok to use [ab] instead of (a∪b).
Official use only
Page 4 of 34
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
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?
Every state that is reachable from the starting state along a sequence of empty (i.e., ε) transitions.
No need to set it out as an algorithm; a clear description of which states are so combined is enough. But it’s also ok to set it out as an algorithm, in which case the solution would look something like this:
Mark the Start state.
While there is an empty transition from a marked state to an unmarked state:
Mark this unmarked state. Output: the set of marked states.
Official use only
Page 5 of 34
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:
Start 1,2 Final 3
1,2 3 1,2 1,2
state a b Start 1 2 3 213
The state here called “1,2”, formed from merging states 1 & 2 in the original table, could be called any other name so long as the name is used consistently throughout the table and is different to the name used for the Final state.
For example, the following is fine:
state a b Start 1 1 2 Final 2 1 1
Official use only
Page 6 of 34
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.
Any regular language has a regular expression (such that the strings in the language are precisely those matched by the regular expression). Interchanging a and b in the regular expression gives another regular expression, and this defines a new language obtained from the original one by interchanging a and b. So this new language must be regular.
Alternative answer, using finite automata instead of regular expressions:
Any regular language has a Finite Automaton that recognises it. Interchanging a and b thoughout such an FA gives a new FA that recognises the language formed from the original one by interchanging a and b. Since this language is recognised by an FA, it must be regular, by Kleene’s Theorem.
Official use only
Page 7 of 34
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,
your answers.
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
⇒ ahahaL ⇒ ahahaaL ⇒ ahahaah
Page 8 of 34
Official use only
Page 9 of 34
Working Space
Page 10 of 34
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.)
S → 1L L → 0L L → 1L L→ε
Page 11 of 34
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.
a,a→ε isoptional b, b → ε
ε, ε → S 1234
An alternative to the arc 2 → 4 labelled ε, ε → ε is to omit that arc and, instead, have
an extra label ε,S → ε on the loop at state 3.
An alternative to the 3-cycle underneath node 3 would be the following 2-cycle, which has the same effect and is also correct.
Page 12 of 34
Official use only
Page 13 of 34
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.
We prove this by induction on the length of the string, i.e., on m + n. Inductive Basis:
If the string has length 1, then it just consists of the string b, which is in L by the derivation S ⇒ T ⇒ b.
Inductive step:
Assume that any string of the form ambn with length < k, and m ≥ n−1 and n ≥ 1, belongs to L, where k ≥ 2. This is the Inductive Hypothesis.
Now suppose we have a string ambn of length k ≥ 2. FIrstly, observe that m ≥ 1, since if m = 0 then n = 1 (by m ≥ n − 1 and n ≥ 1) which implies the string length, k, is only 1 (whereas here we have k ≥ 2). So we know that the string starts with a and ends with b.
If the string has only one b (i.e., n = 1), then it has the form amb (where m ≥ 1, since the length k is ≥ 2). Consider the shorter string am−1b. Since its length is k − 1, the Induc- tive Hypothesis can be used. This tells us that this shorter string belongs to L. So there is a derivation
S ⇒ T ⇒ ··· ⇒ am−1b.
(Observe that the first step of any derivation of a nonempty string in this grammar must be
S ⇒ T.) Removing the first step, we have a derviation of am−1b from T, i.e., T ⇒···⇒am−1b.
Prefixing each string in this derivation gives a derivation of amb from aT: aT ⇒···⇒amb.
But we also have a derivation of aT from S, namely S ⇒ T ⇒ aT (using rule (2) then (4)). Putting these together gives a derivation of amb from S:
S ⇒ T ⇒ aT ⇒ ··· ⇒ amb. So our original string of length k does indeed belong to L.
It remains to deal with the case where our string has more than one b, i.e., n ≥ 2.
Page 14 of 34
Since m ≥ n−1 and n ≥ 2, we have m ≥ 1. The string am−1bn−1 has length k−2, which is < k. Also, m−1 ≥ (n−1)−1 and n−1 ≥ 1. So the Inductive Hypothesis applies. We deduce that this string belongs to L, so there must be some derivation
S ⇒ T ⇒ ··· ⇒ am−1bn−1. This includes a derivation from T:
T ⇒ ··· ⇒ am−1bn−1.
Adding a at the start, and b at the end, of each string in this derivation gives a new derivation,
aT b ⇒ ··· ⇒ ambn.
We also have the derviation S ⇒ T ⇒ a T b (using rule (2) then (3)). Putting these derviations together gives a derivation of ambn from S:
S⇒T ⇒aTb⇒···⇒ambn. So the string ambn belongs to L.
We have now established this conclusion for any string of the form ambn of length k, with m ≥ n − 1 and n ≥ 1, belongs to L.
By the Principle of Mathematical Induction, it follows that any string of this form, of any length, 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.
This is not true. At any stage of any derivation in this grammar, there is only one non-terminal. So there is no choice of which nonterminal in the string is to be used for the next production rule. In particular, whichever production rule we use, we will always be applying it to the leftmost nonterminal (since it is the only nonterminal) — and, also to the rightmost nonterminal. So, in fact, every derivation is a leftmost derivation, and also a rightmost derivation.
(There might sometimes be a choice of which production rule to use for L, since there are several different production rules for L. But this is not relevant to the issue at hand.)
Official use only
Page 15 of 34
Working Space
Page 16 of 34
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.
Fn − Fn−1 = Fn−2, and the Fibonacci numbers are increasing, so their differences are in-
creasing too.
(b) Using (a), prove that the language FIBONACCI is not context-free.
Suppose (by way of contradiction) that FIBONACCI is context-free.
Then it has a CFG, in Chomsky Normal Form, with some number k of nonterminal symbols.
Let w be any word in the language FIBONACCI that has length > 2k−1. Observe that it must be of the form aFn for some Fn > 2k−1.
By the Pumping Lemma for CFLs, the word w can be partitioned into strings u,v,x,y,z (i.e., w = uvxyz) such that:
• v, y are not both empty,
• |vxy| ≤ 2k …which we won’t need …, and • uvixyiz is in FIBONACCI for all i ≥ 0.
For convenience, write p for the combined length of v and y. So p = |v| + |y|. The first and second points above tell us that 1 ≤ p≤ 2k.
Since w = uvxyz is just a string of Fn a’s, the string uv2xy2z is just a string of Fn + p Page 17 of 34
a’s (since we have just taken w and repeated both v and y). More generally, the string uvixyiz is just a string of Fn + (i − 1)p a’s. The third point above means that a string of Fn + (i − 1)p a’s must belong to the language FIBONACCI, for all i. So we have an infinite sequence of strings in FIBONACCI in which each string is exactly p letters longer than its predecessor, and this difference is positive since p ≥ 1.
But we saw in part (a) that the difference between successive Fibonacci numbers is increas- ing. So, whatever p is, we see that for sufficiently large m, the difference Fm − Fm−1 > p. This means that some of the numbers Fn + (i − 1)p cannot be Fibonacci numbers after all, since some of them must fall in the ever-increasing gaps between consecutive Fibonacci numbers. This means that (for large enough i) some of the strings of Fn + (i − 1)p a’s cannot be in FIBONACCI after all. This is a contradiction.
So our original assumption, that FIBONACCI is context free, must be false. Hence FI- BONACCI is not context-free.
Official use only
Page 18 of 34
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 19 of 34
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:
State: 1 State: 3 State: 3 State: 4 State: 1 State: 3 State: 4 State: 1 State: 3
State: 4 State: 2 State:
Page 20 of 34
Official use only
Page 21 of 34
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 22 of 34
Working Space
Page 23 of 34
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 24 of 34
recursively enumerable (r.e.)
Context-Free
Official use only
Page 25 of 34
Question 16 (7 marks)
Prove that the following problem is undecidable.
Input: a Turing machine M.
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.
Suppose (by way of contradiction) that this problem is decidable. Then there exists a de- cider, D, for it.
Now, take any input M to the Diagonal Halting Problem. Construct a new Turing machine M′ from M as follows.
1. Input: x
2. Mark the first tape cell, then move the tape head to just past the end of x, i.e., to the first Blank cell.
3. Simulate the running of M on input M. This simulation treats the first Blank cell after x as the start of its tape, just for the simulation. So the simulation does not interfere with x. (The code for doing this simulation of M is hardcoded into M′. Note that M′ only does this for the one specific machine M that it was constructed from.)
4. Go back to the start of the tape (i.e., to the very first letter of x, which was specially marked).
5. Move along the tape to the right, one cell at a time, overwriting each cell with Blank. (It doesn’t matter if this goes on forever.)
Now, if M halts on input M, then the simulation step in M′ (Step 3) will eventually finish. Then M′ goes on to Step 4, so it then erases the tape. This happens regardless of what the input x was, i.e., for any x.
On the other hand, if M does not halt on input M, then M′ is stuck in Step 3 forever. This simulation does not erase the tape, since x is still sitting unaltered at the start of the tape. We conclude that M halts on input M if and only if M′ eventually erases the entire tape, for some input.
We can therefore use a decider for the given problem to decide the Diagonal Halting Prob- lem. Given M, we construct M′ and let x be any nonempty string. We use D to decide whether or not M′ permanently erases the tape, and the answer from D immediately tells us whether M halts on input M.
So we have a decider for the Diagonal Halting Problem. But that problem is known to be undecidable. So we have a contradiction. So the assumption that the given problem is decidable must be incorrect. Therefore it is undecidable.
Page 26 of 34
Page 27 of 34
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.)
Take the complement of the language.
Official use only
Page 28 of 34
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}).
The solution needs to describe the conjunction of all clauses eR ∨ eW ∨ eB
over all edges e (thes
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com