Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
A06472
Models of Computation [Answer all questions.] Turn Over No calculator 1. [29%] This question is about regular languages and finite-state automata. (a) Give a regular expression for the language over the alphabet {a, b} consisting of all words in which a occurs an even number of times. [7%] (b) Give a deterministic finite state automaton for this language. [7%] (c) Let L be the language over the alphabet {a, b} consisting of all words in which a and b occur an equal number of times. Using the pumping lemma, show that L is not regular. [8%] (d) Here are two deterministic finite state automata. 1 2 3 4 0 5 6 10 8 9 7 a b a,b a,b b a b a b a b a,b a a b a,b a,b Give a bisimulation to show that they recognize the same language. [7%] A06472 – 2 – Turn Over No calculator 2. [22%] This question is about decidability. You are an employee of Ellipse Ltd, which sells an integrated development environment (IDE) for Java programmers. The IDE is itself written in Java. A new version is being developed. (a) The manager says to you: “Create a button that determines whether, in the Java file selected by the user, there are two different declarations of variables with the same name.” (For example, if there are two different lines declaring int i, then the button will print Yes.) Can this be accomplished? Explain your answer. [7%] (b) The manager says to you: “Create a button that determines whether the Java method selected by the user may be called with some argument that will cause an exception to be thrown.” Can this be accomplished? Explain your answer. [7%] (c) The manager has decided that the new IDE will be written not in Java but in a different programming language. Does that make a difference to your answers? Explain. [8%] A06472 – 3 – Turn Over No calculator 3. [21%] This question is about two-tape Turing machines. Look at the two-tape machine below. a b a,b a b Right aux Right main Read main Write aux b Write aux a Left aux Read aux Right aux Stop Read aux Write main a Right main Write main b 0 1 2 3 4 5 6 7 8 9 10 11 12 ⎵ ⎵ ⎵ Initially, the main tape contains a nonempty block of a’s and b’s with the rest of the tape blank, and the head over the leftmost character. The auxiliary tape is initially blank. (a) If the initial block is ab, show the first five execution steps. (Altogether 25 steps are performed before the machine halts.) After each step, you should show the current state, the contents of each tape and the position of each head. [7%] (b) What does this machine do in general? [7%] (c) What is the complexity of this machine, in terms of the length n of the block that is initially on the main tape? Explain your answer briefly. [7%] A06472 – 4 – Turn Over No calculator 4. [14%] This question is about NP . In the popular puzzle Sudoku, a square grid of n2×n2 small squares is displayed, divided into n × n square subgrids each consisting of n × n small squares, and partially filled with numbers in the range 1 to n2 inclusive. The task is to fill all the remaining squares with numbers in the range 1 to n2 inclusive, in such a way that in each column, each row and each subgrid, every number appears precisely once. Here is an example with n = 3. Partially filled grid Solution 5 3 7 6 1 9 5 9 8 6 8 6 3 4 8 3 1 7 2 6 6 2 8 4 1 9 5 8 7 9 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 (a) Not every partially filled grid is solvable. Explain why solvability of a partially filled grid is in NP . [7%] (b) It has been shown that this problem is NP-complete. Explain what that means. [7%] A06472 – 5 – Turn Over No calculator 5. [14%] This is a question about λ-calculus with arithmetic. The syntax of terms is given by the following grammar. M ::= x |MM | λx.M | n |M +M where x ranges over variables and n over the integers. (a) Here is a term: (λx. λy. x y) (λx. x+ y) (3 + 1) By applying β-reductions and δ-reductions, reduce this term to normal form. [7%] (b) Let the syntax of types be given by A ::= int | A→ A where int is the type of integers. For each natural number n we define a type An as follows: A0 = int An+1 = An → int Define, for each natural number n, a closed term that has type An and no other type. [7%]