2IT70 2013-2014 Programming Assignment (updated July 6) The classical Turing machine assignment consists of two deliverables: deliverable 1 ask to complete two Java classes, deliverable 2 requires the writing of three Turing machine programs. Deliverable 1: completing the cTM simulator The NetBeans project ClassicalTuringMachine provides a simulator, written in Java, for classical Turing machine programs. The project consists of a GUI and an execution engine. Via the GUI Turing machine programs can be loaded, initial tape content can be set, and by calling the execution engine the loaded program can be run, either in step-by-step mode or in run-to-completion mode. The Java source code contains a number of classes, including a Java class classicaltm.model.Tape and a Java class classicaltm.model.TuringMachine. You are asked to add code to these classes to complete the functioning of the simulator. The JavaDoc in the respective classes explain what is expected. Look for the TODO's. We abbreviated classical Turing machine by cTM. The cTM programs that the simulator is supposed to process are defined as follows: * a cTM program are composed of a number of lines * each line is either a comment line, starting with the percentage symbol "%" and following by an arbitrary text string, or a line containing a transition * a tape symbol in the extended tape alphabet is any non-blank symbol, not equal to the percentage sign "%", or the blank symbol denoted by the hash "#" * a state name is any sequence of uppercase letters "A" to "Z$, lowercase letters "a" to "z", and digits "0" to "9" * a transition consists solely of the following sequence: a state name, followed by one or more spaces, followed by a tape symbol, followed by a slash "/", followed by a tape symbol, followed by a comma "," followed by either the symbol "L" or the symbol "R", followed by one or more spaces, followed by a state name * the state "q0" is always assumed to be the initial state of the cTM program * cTM programs may assumed to be deterministic, i.e. for every configuration of the cTM at most one transition can be executed The deliverable is to be submitted by June 1, 2014 by means of a NetBeans project and with the two complete Java classes separately, i.e. three items in total: a file Tape.java, a file TuringMachine.java and your project. Deliverable 2: writing your cTM programs Your are asked to write three cTM programs that compute the following functions: * f: {0,1,2}* -> {0,1}* such that f(w) equals the binary sum x1+x2 of the binary numbers x1 and x2, if w = x1 2 x2, f(w)=0 otherwise. For example, f(101211) = 1000 since 101211 decomposes in a string 101 (which is the decimal number 5) and a string 11 (which is the decimal number 3) while 1000 (which is the decimal number 8) is the binary sum of 101 and 11. * g: {0,1}* -> {0,1}* such g(w) = 0^n 1^m 0^n if #_0(w) = 2n, #_1(w) = m for n,m >= 0 and g(w) = 0^n 1^m+1 0^n if #_0(w) = 2n+1, #_1(w) = m for n,m >= 0. For example, g(01101001) = 00111100 and g(10010) = 01110. * h: {0,1}* -> {0,1}* such that h(w) is the binary representation of the n-th Fibonacci number if w is the binary representation of the number n. Here, the first Fibonacci number is 0. For example, h(111) = 1000 since the 7-th Fibonacci number is 8, and h(1000) = 1101 since the 8-th Fibonacci number is 13. Because of the tape management involved, the programming of the function h is challenging. It is not obligatory to hand a program for it. This deliverable is to be submitted as three (or two, if you skip the Fibonacci program) separate text files named ctmf.txt, ctmg.txt and ctmh.txt containing the classical Turing programs of the functions f, g and h, respectively. Course of affairs The assignment can be done in teams of preferably two students, but teams consisting of one student are allowed. The two deliverables are to be submitted via Peach. Deadline for the first deliverable is Sunday June 1, 2014, 23:59 hours CET, for the second deliverable is Sunday June 15, 2014, 23:59 hours CET. The Java language to be used is Java 7 (Java 8 is not supported by Peach and will therefore not be accepted.) The two teaching assistants, Ziad Ben Snaiba and Willem Sonke, can be consulted for advice. They are having office hours on Tuesdays 16:00-17:00 hours and on Fridays 11:00-12:00 hours, respectively, in room MF 7.113. As it looks now, submissions will be tested manually. Your NetBeans project and cTM programs will be loaded and run against a number of inputs. Your Java and cTM code will be inspected on readability and structuring. You are not allowed to change other classes in the package than the two classes mentioned (classicaltm.model.Tape and classicaltm.model.TuringMachine). Some example programs are provided that you may use for you own testing.