Faculty of Information Technology Monash University
FIT2014 Theory of Computation FINAL EXAM SAMPLE SOLUTIONS
2nd Semester 2017
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
Question 1 (4 marks)
Suppose we have propositions A, K and L, with the following meanings.
A: alphaGo is the equal-best Go player in the world.
K: K ̄e Ji ́e is the equal-best Go player in the world.
L: -dol is the equal-best Go player in the world.
Use A, K and L to write a proposition that is True if and only if exactly two of alphaGo, K ̄e Ji ́e and -dol are the equal-best Go players in the world.
For full marks, your proposition should be in Conjunctive Normal Form.
(A∨K)∧(A∨L)∧(K ∨L)∧(¬A∨¬K ∨¬L)
( computableByGoedel(F) ∧ ( computableByChurch(F) ∧ ( computableByTuring(F)
=⇒ ( computableByChurch(F) ∧ computableByTuring(F) ) ) =⇒ ( computableByTuring(F) ∧ computableByGoedel(F) ) ) =⇒ ( computableByGoedel(F) ∧ computableByChurch(F) ) )
Question 2 (3 marks)
Suppose you have predicates computableByGoedel, computableByChurch, and computableByTuring with the following meanings, where variable F : {a, b}∗ → N ∪ {0} represents an arbitrary function from finite strings over {a, b} to nonnegative integers:
computableByGoedel(F ): computableByChurch(F ): computableByTuring(F ):
the function F is a recursive function, according to ̈del’s definition.
the function F has a lambda expression, in the sense of ’s Lambda Calculus.
the function F is computable.
In the space below, write a statement in predicate logic with the meaning:
Every function that satisfies any one of the three definitions of computability — recursive functions (Go ̈del), lambda calculus (Church), or Turing computabil- ity — also satisfies each of the others.
To do this, you may only use: the above three predicates; quantifiers; logical connectives. (In particular, you may not use set theory symbols such as ⊆, ⊂, ∩, ∪, etc, and in fact they would not help.)
∀F : ( computableByGoedel(F) ∨ computableByChurch(F) ∨ computableByTuring(F) ) =⇒ ( computableByGoedel(F) ∧ computableByChurch(F) ∧ computableByTuring(F) )
Some alternatives:
∀F : ( computableByGoedel(F) =⇒ ∧ ( computableByChurch(F) =⇒ ∧ ( computableByTuring(F) =⇒
computableByChurch(F) ) computableByTuring(F) ) computableByGoedel(F) )
It’s ok if all the directions of implication are reversed here. An alternative, unnecessarily verbose but still correct:
Any or all of the second conjuncts, following the implications, can be omitted; if all are omitted, we have the second solution given above.
Another approach is to take at least two of the three pairs and link them by two-way implications (biconditionals). For example:
∀F : ( computableByGoedel(F) ⇐⇒ computableByChurch(F) )
∧ ( computableByChurch(F)
⇐⇒ computableByTuring(F) )
Official use only
Question 3 (6 marks)
Let En be the following Boolean expression in variables x1, x2, . . . , xn: ((···((((¬x1 ∨x2)∧¬x2)∨x3)∧¬x3)···)∨xn)∧¬xn
For example, E1 = ¬x1, and E2 = (¬x1 ∨ x2) ∧ ¬x2. In general, En = (En−1 ∨ xn) ∧ ¬xn.
Prove by induction on n that, for all n ≥ 1, the expression En is satisfiable. Inductive basis:
If n = 1, we have E1 = ¬x1, which is satisfiable because x1 = False satisfies it. Inductive step:
Suppose n ≥ 2. Assume En−1 is satisfiable (the Inductive Hypothesis). So it has a satisfying truth assignment to its variables, x1, x2, . . . , xn−1. Consider En = (En−1∨xn)∧¬xn. (Note, this uses n ≥ 2.) We have a satisfying truth assignment that makes En−1 true. Under this assignment, En−1 ∨ xn is also true, so in this case we have En = (En−1 ∨ xn) ∧ ¬xn = True ∧ ¬xn = ¬xn. This can be satisfied by putting xn = False. So En is satisfiable.
Therefore En is satisfiable for all n, by Mathematical Induction.
Official use only
Question 4 (4 marks)
Write down all strings of length ≤ 6 that match the following regular expression: ε ∪ (ab)∗b(aaa ∪ bb)∗
ε, b, abb, bbb, baaa, abbaaa, abbbb, ababb, bbbbb, baaabb, bbbaaa
Official use only
Question 5 (4 marks)
Let R be any regular expression.
(a) Give, in terms of R, a regular expression for the language of all strings that can be
divided into two substrings, each of which matches R. RR
(b) Prove that the language EVEN(R) of all strings that can be divided into any even number of substrings, each of which matches R, is regular.
For example, if R is a ∪ bb, then the string w = aabba can be divided into four substrings a,a,bb,a which each match R. So this w belongs to EVEN(R). The empty string is also in EVEN(R), noting that zero is an even number. But aabb and bbb do not belong to EVEN(R).
Suppose that a string s can be divided into an even number of substrings, each of which matches R. Let the number of such substrings be 2k. Then s can be divided into k pairs of substrings, with each pair consisting of two strings that match R. Each pair must therefore match RR, by (a). So s can be divided into k strings that match RR. Since k can be any number (including 0), our string s must match (RR)∗. Conversely, any string that matches (RR)∗ must consist of some number of substrings that each match RR, and therefore it must consist of an even number of substrings that each match R.
This shows that EVEN(R) is described by the regular expression (RR)∗, so it must be regular.
Official use only
Question 6 (8 marks)
(a) Convert the following Nondeterministic Finite Automaton (NFA) into an equivalent Deterministic Finite Automaton (FA).
Your FA must be presented by filling in some rows in the following table. You may not need all the rows available.
Start {1} {2,3} Final {2,3,4}
{2,3,4} ∅∅∅
It’s ok if the states are renumbered, as long as the FA is correct. For example:
state a b Start1 2 4
233 Final 3 3 3 444
(b) Give a regular expression for the language accepted by the above NFA.
(You should not need to apply a general automaton-to-regexp conversion algorithm.
Just think about what the automaton does. The equivalent FA should help.)
a(a ∪ b)(a ∪ b)∗ or, equivalently, a(a ∪ b)∗(a ∪ b)
Question 7 (5 marks)
Give an algorithm which takes, as input, a Finite Automaton represented as a table, and finds another Finite Automaton that accepts the same language as the first one and has the minimum number of states among all FAs that accept that language.
A pseudocode description is fine.
Do not try to write your algorithm as a Turing machine.
Input: FA represented as table.
Give all non-Final states the first colour.
Give all Final states the second colour.
Apply these colours throughout the table (i.e., not just in the states column).
While ( there exist two states of the same colour whose rows have different colour patterns ) {
Pick one of these states.
Identify all other states whose rows have the same colour pattern as it. Give each of these states the same new colour.
I.e., they each get a new colour, and they all get the same colour. Apply this new colour to that state throughout the table.
For each colour:
Output: the new FA, as described by the new table.
Merge all states of that colour into a single state.
Throughout table, replace the names of these states by the name of the merged state.
Official use only
Question 8 (12 marks)
Consider the following Pushdown Automaton (PDA), with input alphabet {a,b,c} and extra stack symbols S and $.
(T4): a,S → c (T1): ε,ε→$ (T2): ε,ε→S
(T5): ε,ε → S (T3): ε,$→ε
(T6): ε,S→b (T7): a,a→ε (T8): b,b→ε (T9): c,c→ε
(a) Show that the single-letter string b is accepted by this PDA, by giving the sequence of transitions that leads to acceptance of b.
Use the names of the transitions, i.e., T 1, T 2, . . ., etc. T1, T2, T6, T8, T3
Prove the following statement by induction on n:
For all n ≥ 0:
If the PDA is in State 3, the top symbol on the stack is S, and the remaining
input begins with anbcn, then after reading anbcn the PDA is again in State 3 and the stack is the same except that the S on the top has been removed.
Inductive basis: n = 0: the remaining input is b, and if S is on top of the stack, the transitions T6, T8 leave us still in state 3, having read the input, and S has been removed from the top of the stack. No other change has been made to the stack.
Inductive step:
Suppose the statement is true for n (the Inductive Hypothesis). Suppose the PDA is in state 3, the remaining input starts with an+1bcn+1, and that S is on top of the stack. Then the combined effect of transitions T4, T5 is to read the first a of input and replace the S on top of the stack by c and then S, i.e., the only change to the stack is that c is underneath S; the portion of the stack below this c is unchanged, and S is still on top of the stack.
So the situation is now that the input begins with anbcn+1, which is anbcnc, which begins with anbcn; also, we are again in state 3, and S is on top of the stack. This is the “if”-part of the given statement, for n. By the Inductive Hypothesis, after reading anbcn, the PDA is again in State 3 and the stack is the same except that the S on the top has been removed. The next thing on the stack is the c we put there before (using T4 and T5). The next unread letter is c. So we can apply T9, which reads that letter and pops the c off the stack. We are back at state 3 again, and the stack is the same as it was when we began the inductive step except that the S that was then on the top of it is not there any more. This is exactly our desired conclusion, so we have established the given statement for n + 1.
By the Principle of Mathematical Induction, the statement holds for all n ≥ 0.
(c) Hence prove that, for all n ≥ 0, the string anbcn is accepted by this PDA.
When this string is given as input to this PDA, before reading anything it pushes $ and then S onto the stack. We are then in state 3, with S on top of the stack, and the string to be read begins with (and in fact equals) anbcn. By part (b), the PDA reads this string and then is in state 3 with S removed from the top of the stack, and otherwise the stack is unchanged. So all that’s left on the stack is the single symbol $. The PDA now does transition T3. At this stage, the entire input has been read, and the PDA is in its Final state, so the input string is accepted.
Official use only
Question 9 (13 marks)
Let GOAL be the language generated by the following Context-Free Grammar:
S → gooXal (1) X → ooXa (2) X→ε (3)
GOAL consists of all strings of the form g(oo)nanl , where n ≥ 1.
The first few strings in this language, in order of increasing length, are:
gooal, gooooaal, gooooooaaal, . . .
(a) Give a derivation for the string gooooaal.
Each step in your derivation must be labelled, on its right, by the number of the rule used.
S ⇒ gooXal (1)
⇒ gooooX aal (2) ⇒ gooooεaal (3)
= gooooaal
(b) Give a parse tree for the same string, gooooaal.
(c) Use the Pumping Lemma for Regular Languages to prove that GOAL is not regular.
Assume, by way of contradiction, that GOAL is regular. Then, by Kleene’s Theorem, there is a Finite Automaton that accepts it. Let N be the number of states of this FA.
Let w be the string go2N aN l. This has length > N . Therefore, by the Pumping Lemma for Regular Languages, w can be divided into substrings x,y,z such that y ̸= ε, |xy| ≤ N, and for all i ≥ 0 the string xyiz ∈ GOAL.
The constraint |xy| ≤ N tells us that y is within the first N letters of w. This means that y either contains the g at the very start of w or lies within the substring o2N . If it contains g, then repeating it to form xyyz gives a string with more than one g, which therefore cannot belong to GOAL (since every string in GOAL just has one g, the one at the beginning). If y lies within the substring o2N, then repeating it to form xyyz increases the length of the o-substring: it now has length > 2N (using y ̸= ε). But the length of the a-substring has not changed: it’s still N. So the length of the o-substring is no longer exactly twice the length of the a-substring. This breaks the rules of the language GOAL, so xyyz cannot belong to GOAL. So, regardless of where y is located in w, the string xyyz ̸∈ GOAL.
This violates the conclusion of the Pumping Lemma. So we have a contradiction. There- fore our initial assumption, that GOAL is regular, was wrong. So GOAL is not regular.
Deletion of y works just as well as repeating it, since the Pumping Lemma says that xyiz ∈ GOAL for all i ≥ 0; the i = 0 case tells us that xz ̸∈ GOAL.
Official use only
Question 10 (2 marks)
The Cocke-Younger-Kasami (CYK) algorithm is less efficient than most commonly used parsing algorithms. What is one significant advantage it has over those algorithms?
It’s more general: it can parse any context-free language.
Question 11
Consider the following Turing machine.
a→b,R b→b,R
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).
You should not need all the lines provided.
To get you started, the first line has been filled in already.
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: 4 State: 1 State: 3 State: 4 State: 2 State: State:
Official use only
Question 12 (5 marks)
(a) Name three variations on Turing machines that give the same class of computable functions.
Any three of:
• two-way infinite tape (i.e., infinite on the left (negative) side, as well as on the right (positive) side);
• more than one tape;
• allowing the tape head to stay still, as well as to move left or right;
• allowing the tape head to move some number of steps to the left or right, instead of just one step, with a fixed bound on the number of steps;
• forcing the tape head to stay still, or move to the right, if ever it tries to move off the left end of the tape (instead of crashing in these circumstances);
• using a two-dimensional grid instead of a (one-dimensional) tape;
• allowing the actions to depend on the contents of the neighbouring tape cells as well
as the current tape cell;
• giving access to a source of random symbols (i.e., probabilistic Turing machine). [We haven’t studied this.]
(b) Give one way of modifying the definition of Turing machines so that they can still recognise all regular languages but can no longer recognise all decidable languages.
For full marks, your modification should be as simple as possible. It should involve altering just one part of the definition of Turing machines. Replacement of an entire machine by something else is not acceptable.
No proof is required for this question.
Any of the following is correct:
• restrict the tape head so that it only moves to the right;
• prevent the tape head from moving to the left;
• when the tape head moves to the left, the cell it was on becomes blank.
The following answers are incorrect:
• prevent the tape head from moving to the right;
• any of the modifications in part (a), which don’t change the class of languages recog- nised.
Official use only
Question 13 (4 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: two Turing machines M1 and M2.
Question: Does M1 eventually halt, when given M2 as input?
Input: two Turing machines M1 and M2.
Question: Does M1 have the same number of states as M2 ?
Input: two Turing machines M1 and M2.
Question: Is M1 equivalent to M2 (i.e., do M1 and M2 have the same sets of accepted strings and the same sets of rejected strings)?
Input: two Turing machines M1 and M2.
Question: If each machine is given itself as input, does M1 finish before M2?
your answer
(tick one box in each row)
Undecidable
Undecidable
Undecidable
Undecidable
Official use only
Question 14 (12 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, 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), with input alphabet {a,b} and tape alphabet {a,b,#,∆}.
(a) The set of all binary strings.
(b) The set of all strings in which every a occurs before every b.
(c) The set of all strings in which a occurs more times than b.
(d) The set of all strings in which every a occurs before every b and ALSO a occurs more
times than b.
The set of adjacency matrices of 2-colourable graphs.
The set of adjacency matrices of 4-colourable graphs.
The set of all Boolean expressions in Conjunctive Normal Form (CNF), whether satisfi-
able or unsatisfiable. (Assume the variables are x1, x2, . . . , xn, and variable xi is represented by its index i as a binary positive integer.)
The set of all encodings of Turing machines that accept regular languages.
The set of all encodings of Turing machines that accept non-context-free languages. The set of all encodings of Turing machines that loop forever for some input.
and addition, subtraction, multiplication and division, but with no parentheses.
The set of all arithmetic expressions involving positive integers, in decimal notation,
(l) The set of all arithmetic expressions involving positive integers, in decimal notation, and addition, subtraction and parentheses, but no multiplication or division.
recursively enumerable (r.e.)
Context-Free
Official use only
Working Space
Question 15 (8 marks)
Let L and K be languages. Suppose that K is finite.
Definition: The symmetric difference L∆K consists of all strings that belong to L or
K,butnotboth. Inotherwords,L∆K=(L∪K)\(L∩K).
(a) Prove that there exists a mapping reduction from L to L∆K.
Because K is finite, K ∩ L and K \ L are also finite, and hence both are decidable. Here is such a mapping reduction.
LetsbeastringinK∆Landlets′ beastringnotinK∆L.
Input: string x.
Use a K-decider to determine whether or not x ∈ K.
// … =⇒it’sinL,soitmustbemappedtoastringinK∆L. ButxitselfisnotinK∆L, // so we can’t just output x. Instead, output some fixed string known to be in K∆L.
output s }
elseif x∈K\L
// // // {
… =⇒ it’s not in L, so it must be mapped to a string outside K∆L. But x itself is in K∆L, so we can’t just output x. Instead, output some fixed string known not to be in K∆L.
output s′ }
else // x ̸∈ K, so x ∈ L ⇐⇒ x ∈ K∆L {
output x }
This algorithm, together with the decidability of K ∩ L and K \ L, implies that this function is computable.
If x ∈ L, then either x ∈ K, in which
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com