of Information Technology Faculty of Information Technology
Monash University
FIT2014 Theory of Computation SAMPLE EXAM
2nd semester, 2013
Copyright By PowCoder代写 加微信 powcoder
Instructions:
10 minutes reading time.
3 hours writing time.
No books, calculators or devices. Total marks on the exam = 120.
Sample answers in blue.
Comments in purple.
Question 1 (4 marks)
Annie, Henrietta, Radhanath and Williamina have been shortlisted for two jobs as comput- ers. Let A, H, R, W be propositions with the following meanings.
A: Annie gets one of the jobs.
H: Henrietta gets one of the jobs. R: Radhanath gets one of the jobs. W: Williamina gets one of the jobs.
Use A, H, R and W to write a proposition, in Conjunctive Normal Form, that is True precisely when exactly two of them get jobs.
(A ∨ H ∨ R) ∧ (A ∨ H ∨ W ) ∧ (A ∨ R ∨ W ) ∧ (H ∨ R ∨ W ) ∧
(¬A∨¬H ∨¬R)∧(¬A∨¬H ∨¬W)∧(¬A∨¬R∨¬W)∧(¬H ∨¬R∨¬W)
The first four clauses together ensure that at least two of them get jobs. The last four clauses together ensure that at most two of them get jobs.
These four names belong to four famous computers:
Annie Jump Cannon (1863–1941), Leavitt (1868–1921), (1813–1870), (1857–1911).
Look them up!
Question 2
Suppose you have the predicates prolog and elvish, with the following meanings: prolog(X): X knows the Prolog language.
elvish(X): X knows the Elvish language.
(a) Write a universal statement in predicate logic with the meaning:
“Nobody knows both Prolog and Elvish.”
Alternative answer:
∀X ¬(prolog(X) ∧ elvish(X)) ∀X(¬prolog(X) ∨ ¬elvish(X))
(b) Suppose that the statement in (a) is False. Starting with its negation, derive an existential statement meaning that someone knows both these languages.
If you start with the first answer given to (a) above:
Negate the answer to (a):
¬∀X ¬(prolog(X) ∧ elvish(X)) = ∃X¬¬(prolog(X) ∧ elvish(X))
Question 3
= ∃X(prolog(X) ∧ elvish(X))
Give a regular expression for the set of all real numbers, represented in binary, that are greater than 0, less than 1, and have a finite binary representation.
(Assume that such binary numbers always have a bit before the binary point (i.e., what we would normally call the “decimal point”), and at least one bit after it.)
0.(0 ∪ 1)∗1
Alternative way of writing this, using common shorthand for regexps: 0.[01]*1
The regular expression 0.(0 ∪ 1)∗ doesn’t quite do the job, on two counts: firstly, it does not guarantee that there is at least one bit after the point; and secondly, it allows zero, represented as 0.000…0 (with some number of zeros after the point), which the question forbids. The regular expression 0.(0 ∪ 1)(0 ∪ 1)∗ (which may be abbreviated as 0.[01]+) is better, as it ensures that there be something after the point, but it still allows zero, which it shouldn’t.
Question 4 (4 marks)
(a) Write down all strings of at most 8 letters, over alphabet {0,1}, that match the regular expression ((101)∗ ∪ (00))∗ .
ε, 101, 101101, 00, 10100, 00101, 00101101, 10100101, 10110100, 0000, 0000101, 0010100, 1010000, 000000, 00000000.
Observe that the Kleene star inside the parentheses is not needed. The given regular expression is equivalent to ((101) ∪ (00))∗ .
(b) Give an NFA that recognises the language described by this regular expression.
Any of the following is acceptable:
Question 5 (3 marks)
Prove that the class of regular languages is closed under complement.
We need to show that the complement of a regular language is also a regular language.
If L is a regular language, then by Kleene’s Theorem there is a finite automaton A that recognises L. Create a new finite automaton, B, which is identical to A except that the Final states in A are not Final in B, and the non-Final states in A are Final in B. Then B will accept exactly those strings that are not accepted by A. So the language accepted by B is the complement of L. Therefore the complement of L, being the language accepted by some FA, is also regular, by Kleene’s Theorem.
Question 6 (3 marks)
What kinds of regular languages can be described by regular expressions that do not use the Kleene star? Explain.
The Kleene star is the only regular expression operation which enables a regular expres- sion to match an infinite number of strings. Without the Kleene star, we just have ∪ and concatenation, and these only allow us to match a finite number of strings.
On the other hand, any finite language can be described by some regular expression that does not use the Kleene star. Just take all the strings in the language and combine them using the alternative construct, ∪.
Question 7 (3 marks)
Let L be the language of nonempty strings over {x,y} that must start and finish with the same letter, and in the middle have at least one of the other letter. Draw a FA to recognise L.
Question 8 (4 marks)
Given the Finite Automaton described by the following table, find an FA with fewest states that recognises the same language.
state a b Start 1 2 6 236 363 454 54 6 63 6
Write your new FA in the blank table below.
state a b Start 1 2 4 234 343 Final 4 3 4
Final Final
Question 9 (5 marks)
(a) Prove that the language of strings of even length is regular.
Assume alphabet {a,b}.
The language of strings of even length can be described by the regular expression ((a∪b)(a∪ b))∗. The expression within the outer parentheses, (a ∪ b)(a ∪ b), matches any string of two letters. Applying the Kleene star gives a string that matches any concatenation of any finite number of strings of two letters — in other words, any string of even length. So the language of such strings is regular.
Alternatively, you could give a FA which you can show matches all strings of even length. Then appeal to Kleene’s Theorem to conclude that the language of such strings is regular.
(b) Given the closure properties of regular languages, and the fact that the language of strings of even length that are not palindromes is not regular, prove that the language of palindromes is not regular.
We prove this by contradiction. Assume that the language of palindromes is regular. Then its complement, the language of non-palindromes, is also regular, since the regular languages are closed under complement. We know from part (a) that the language of even- length strings is regular. So the intersection of the non-palindromes with the even-length strings is also regular, since these languages are both regular and the regular languages are closed under intersection. But this is a contradiction, as we are given that the language of even-length non-palindromes is not regular. Therefore our assumption, that the language of palindromes is regular, is wrong. So the language of palindromes is not regular.
Question 10
Consider the following Regular grammar:
S → ε|aT|bU T → aT|bS
(a) Give (i) a derivation, and (ii) a parse tree, for the string baab .
S ⇒ bU ⇒ baS
⇒ baaT ⇒ baabS ⇒ baab
by(1c) by(3)
by(1b) by (2b)
(b) Find the Finite Automaton for the language defined by the above grammar. aa
(1) (2) (3)
The FA on the left is obtained by direct conversion of the regular grammar to a FA. Strictly speaking, it is not deterministic since state U does not have a transition for the letter b. This is easily fixed: see the FA on the right. (In a sense, omitting transitions is a less “serious” form of nondeterminism than empty transitions or multiple transitions for the same letter, since the former does not lead to ambiguity as to how to proceed, provided a missing transition is taken to give rejection if it is attempted. That’s not how we’ve defined rejection by FAs in this unit, though.)
(c) Give a regular expression for the language defined by the above grammar.
((aa∗b) ∪ (ba))∗ 8
Question 11 (3 marks)
A string over the alphabet {0,+,−} is said to be balanced if it satisfies both the following: • (i) for any i, the first i characters in the string contain at least as many + as −;
• (ii) the whole string has the same number of + as −. Give a Context-Free Grammar for the language.
S → +S− S→ε
This is a variation on the Dyck language, with left parenthesis replaced by +, right paren- thesis replaced by −, and 0s allowed to be inserted anywhere.
Question 12 (9 marks) The language Luke has the following Context-Free Grammar:
S→Z (1) S → Sooo (2) Z → nZ (3) Z→ε (4)
(a) Give a derivation of the string nnooooooooo, indicating which production rule is used at each step.
⇒ S oooooo
⇒ S ooooooooo
⇒ Z ooooooooo
⇒ nZ ooooooooo
⇒ nnZ ooooooooo
⇒ nnooooooooo
by (2) by (1)
by (3) by (3)
(b) Complete the following diagram to give a Pushdown Automaton for Luke.
n,n→ε isoptional o, o → ε
ε, ε → S pqrs
ε, $ → ε ε, S → o ε, ε → S
ε, ε → o ε, ε → o
(c) Is the above CFG a regular grammar? (Explain.)
No, because there is a production rule, namely S → Sooo, whose right-hand side does not consist of terminals followed by non-terminals.
(d) Is Luke a regular language? (Explain.)
Yes, because it is described by a regular expression: n∗(ooo)∗
Alternatively, you could give a FA, or a regular grammar, for the language.
(e) Convert the grammar into Chomsky Normal Form.
S → NS S → SO
N → NN N→n
O → O1O′ O′ → O2O3
O1 → o O2 → o O3 → o
Question 13 (5 marks)
Find a Context-Free Grammar for the language accepted by the following PDA.
a, ε → X 1234
Your CFG must use only the nonterminal symbols S, A11, A22, A33, A44, A14, A23.
Write the CFG in the space below. Five production rules have already been written in, to get you started.
d, Y → ε e, X → ε
S → A14 A11 → ε A22 → ε A33→ε A44→ε
A14 → aA23e A23 → A22A23 A23 → bA22d A22 → A22A22 A22 → bA22c
In this case, the symbols A11,A33,A44, and their associated production rules, are not used.
Question 14 (8 marks) (a) Prove that the language of strings representing powers of 2, in binary form, is regular.
This language is described by the regular expression 10∗, therefore is regular.
(b) Prove that the language of strings representing powers of 2, in unary form, is not
context-free.
We prove this by contradiction, using the Pumping Lemma for Context-Free Languages.
Assume that this language is context-free, with some context-free grammar. Let k be the number of non-terminal symbols in the grammar. Let w be any word in the language of length > 2k−1. Then, by the Pumping Lemma, w can be divided up into strings u, v, x, y, z such that v, y are not both empty, |vxy| ≤ 2k, and uvnxynz is in the language for every n.
Observe that w is a string of 2i ones, for some i (since w represents a power of 2, in unary). Suppose the combined length of v and y is j. Note that j ̸= 0, since v and y are not both empty. Now, uv2xy2z consists of |w| + j ones, since it is just w with an extra j ones (for the extra pair v,y). So its length is 2i +j (since |w| = 2i). If 2i > j, then 2i +j cannot be a power of 2, so uv2xy2z is not in the language, which is a contradiction with the conclusion of the Pumping Lemma. (Observe that we can ensure that 2i > j by just choosing w to be long enough, since the combined length j of v and y is bounded independently of the length of w (since |vxy| ≤ 2k). Also, in deducing that 2i + j cannot be a power of 2, we are using the fact that j ̸= 0.)
So the assumption that the language is context-free is incorrect. Therefore it is not context- free.
Question 15 (3 marks)
State two important results that can be proved using the Chomsky Normal Form for Context- Free Grammars.
The Cocke-Yonger-Kasami (CYK) Algorithm, which enables us to parse strings for any context-free language, uses Chomsky Normal Form.
The Pumping Lemma for CFLs (see above) also uses Chomsky Normal Form.
Question 16 (6 marks) Write a Turing machine that flips the middle bit (i.e., changes 0 to 1, and 1 to 0) of a binary string of odd length, and leaves a string of even length unchanged.
For example, if the input string is 0111110, then the output must be 0110110. If the input string is 011110, then the output is also 011110.
0®C,R 1®D,R
C®0,R D®1,R
0®A,L 1®B,L
A®0,R B®1,R
C®0,R D®1,R
A®B,L B®A,L
0®L 3 50®L 1®L
A®R B®R C®R D®R Δ®R
0®A,R 1®B,R
* Direction in this case could be L or R.
Outline of how this works:
In the above Turing machine: you start by replacing the first and last bits by letters, with 0 being replaced by A or C, and 1 being replaced by B or D. The positions of these bits are easy to recognise. The first bit is where you start (1 → 2), and you find the last bit by moving to the right (loop at State 3) until you reach a blank, then you go one step to the left (3 → 4) so you know you’re at the last bit, which you then change to a letter (4 → 5). Now that the first and last bits are letters, you go all the way back (loop at State 5) until you reach another letter, then go one step back from it (5 → 6). You are now at the leftmost bit; there was a bit further to the left but it has been replaced by a letter.
You keep going like this, shuttling back and forth along the tape, replacing each pair of outermost bits by letters, and passing over the bits between them, until all bits have been replaced by letters. We find ourselves repeatedly going around the circuit 6,3,4,5,6. The bits in the middle, between the letters, decrease in number. If the original bit-string is of even length, then we leave the circuit at 6. If it is of odd length, we leave it at 4. Then, using the loop at State 7, we move back (i.e., leftwards) to the start, and we can recognise when we’re at the start because in this position the bit was replaced by C or D, rather than A or
B. Then (State 8) we go all the way along the tape (rightwards), replacing every A or C by 0, and every B or D by 1. When we reach a blank, we stop.
In this TM, the flip of the middle bit (if such exists) is done in transition 4 → 7 (see green box), using the letter that (by then) represents that bit.
Strings consisting of just a single bit are a special case. They are the only input strings that use the transition 4 → 2. They cause the Turing machine to do the transi- tions 1 → 3 → 4 → 2, which together have the effect of flipping the bit.1
Question 17 (1 marks)
The characteristic function fL of a language L over some alphabet is defined by: 1, x∈L,
fL(w)= 0, x̸∈L,
for any string w over the alphabet.
State the property that fL must have, for the language L to be decidable. fL must be computable.
Question 18
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: Turing machines M and N.
Question: Are the encoded forms of M and N identical?
Input: Turing machines M and N.
Question: Do M and N have the same time complexity?
Input: a Turing machine M.
Question: Does M correctly determine whether or not its input string is a palindrome?
your answer
(tick one box
in each row)
Undecidable
Undecidable
Undecidable
Undecidable
Input: a Turing machine M, and a string w.
Question: Does M ever change any letter of w on the
tape? Decidable
1Thanks to FIT2014 tutor Rebecca Young for suggesting the modification to deal with this case. 14
Question 19 (9 marks)
The Venn diagram at the left 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.
The Dyck language.
The set of all even numbers, represented in binary.
The Code-Word Language (CWL).
The set of all encodings of Turing machines (encoded using strings from CWL). DOUBLEWORD, the set of all strings consisting of a string concatenated with itself. The set of all palindromes (i.e., strings that are the same forwards or backwards).
The set of all Turing machines that accept every binary string.
The set of all regular expressions.
The set of all polynomials (with any number of variables) with an integer root.
The set of all correctly formed arithmetic expressions, using integers and the symbols
+, −, ×, /, and parentheses.
most two literals in each clause.
The set of all satisfiable Boolean expressions in Conjunctive Normal Form with at
(l) The set of all satisfiable Boolean expressions in Conjunctive Normal Form with at most three literals in each clause.
Which, if any, of these languages are NP-complete?
The language l is NP-complete.
This is easy to show, by polynomial-time reduction from 3SAT.
recursively enumerable (r.e.)
Context-Free
Question 20 (7 marks)
Prove that the following problem is undecidable.
Input: a Turing machine M, and a positive integer t.
Question: Is there an input string x of length at least t such that, if M is run on x, it eventually halts?
You may use the fact that the halting problem is undecidable.
Let (T, w) be an input to the Halting Problem. So T is a Turing machine (appropriately encoded), and w is a string which can be treated as an input to T . For the Halting Problem, we want to know whether or not T eventually halts, when its input is w.
We construct from (T,w) a program M which runs as follows:
1. Input: a string x.
2. Simulate T on input w. (This is hardcoded. So we aren’t taking w as input to M, but rather, we have lines of code (or Turing machine instructions) that provide w as input to this simulation of T .)
3. Test if |x| is a multiple of 29. (The choice of 29 is arbitrary! All we want to ensure is that there is an infinite sequence of strings x that satisfy this test.)
If so, halt; otherwise, loop forever.
Observe that:
If T eventually halts, on input w, then the simulation in Step 2 of M will eventually stop. Then M goes on to Step 3. For any t, there will be some multiple of 29 that is greater than t (in fact, infinitely many, but we only need one). So, there is some x which, if given to M, causes it to halt eventually.
On the other hand, if T loops forever for input w, then M will be forever stuck in Step 2. Therefore, there is no input x which causes M to eventually halt, and therefore certainly no such input with length ≥ t.
So, T halts for input w if and only if there is some input x with |x| ≥ t such that M halts for input x.
This tells us that, if the problem stated in the question is decidable, then we could use a decider for it to construct a decider for the Halting Problem. To see this, suppose D is a decider for the problem stated in the question. Suppose we are given (T,w), as input to the Halting Problem. From (T,x), construct M as described above. This construction is computable. Then use D to determine whether or not M has an input x, with |x| ≥ t, for which it eventually halts. The answer D gives us becomes our answer to the Halting Problem regarding (T,x). So we are done.
Therefore the problem stated in the question is undecidable.
Question 21 (5 marks)
For this question, recall that the composition of two polynomial-time reductions is again a polynomial-time reduction, and that the notation ≤p indicates the existence of a polynomial- time reduction.
Prove by induction on n that, if L1, . . . , Ln are languages, and Li ≤p Li+1 for all i in the range1≤i≤n−1,thenL1 ≤p Ln.
Inductive hypothesis:
There is a polynomial-time reduction from L1 to Li. Base case:
If i = 1, then the identity map (i.e., the polynomial-time reduction that “does nothing”, just mapping everything to itself), establishes
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com