see
COSC1107/1105 Computing Theory - Assignment 2 - Deadline: Sunday October 13th 2019, 11:59 PM - Computing Theory Total marks: 90 (15% whole course) Please read all the following information before attempting your assignment. This is an individual assignment. You may not collude with any other individual, or plagiarise their work. Students are expected to present the results of their own thinking and writing. Never copy another student’s work (even if they “explain it to you first”) and never give your written work to others. Keep any conversation high-level and never show your solution to others. Never copy from the web or any other resource. ( You are to submit a PDF file and one zip file named with your student number (e.g., 3451234.zip) containing (in its root folder) your three .jff files for exercise 1 via the following Google Form: The PDF file can have any name as long its extension is .pdf, but it must must be typeset in a word processor (scanned files will not be marked) and have your student name and number on it. Python validator scripts for the zip file can be obtained here . The three JFLAP files must follow the exact name conventions as specified below in each question, and must load & run in JFLAP 7.0 with no errors whatsoever in reasonable amount of time (see below). )Submission Instructions Corrections: From time to time, students or staff find errors (e.g., typos, wrong/missing symbols, ambiguous text) in the assignment specification. In that case, a corrected version will be uploaded to the course web page as quickly as possible, an announcement will be made on the course web page as well as in the forum. Check the version on the bottom left. 1 Exercise 1: Turing Machine Design20 marks In this exercise you will build a few Turing Machines in JFLAP. Your machines will be fully automarked, so you must follow the following conventions (please read them carefully and ask if in doubt1): ( • )Your Turing machine will always start with the head in the first symbol of the input on the tape. For example, if your initial state is q0 and the input string is abcd#cba, then the initial configuration would be q0, Babcd#cbaB, where B is the blank symbol (in red for better legibility), and the underlined symbol is where the head is reading. Note this is a different convention to that used in many machines done in tutorials where the head was assumed to begin reading the blank symbol on the left of the input, and so one must do a B/B, R initial transition. ( • )The acceptance condition to be used will be halting in a final state, as in the Sudkamp’s book. – JFLAP has two acceptance conditions under Preferences, one can make JFLAP “Accept by final state” or “Accept by halting”, or by either of them (if both selected). We recommend to work with only “Accept by final state” selected, but remember that by itself “Accept by Final State” does not require halting, so think how to build your machine to capture the halting in final state acceptance condition that shall be used. ( • )The output of a Turing machine (when it accepts) consists of the character directly under the tape head until the first blank to the right consists of the symbol underneath the tape head and all symbols to the right of the tape head until the blank is encountered. In the event that the tape head is on a blank, the output is the empty string. For example, if the Turing Machine accepts with the tape left as Baaaaabcd#cbaB, then the output of the Turing Machine is the string abcd#cba. When a Turing Machine rejects, what is left in the tape is irrelevant—there is no output. ( • )Your machines must be syntactically error-free, and load and terminate always within a reasonable amount of time using JFLAP version 7: at most 5 secs. per run. These two are minimal standards that must be met. Machines with syntactic errors or requiring more than 5 seconds on any input will be awarded zero marks. ( • )No manual changes or repairs will be done to any of the submitted files. It is your responsibility to test your files in JFLAP 7 before submitting (you have the tool!). ( • )Your TM has to be one-tape standard “Turing Machine” in JFLAP (no multi-tape machine or block machine); refer to post @151. You are free however to use any advanced features provided by JFLAP for standard Turing Machines, as long as the machine submitted solves the problem. Please refer to some information and tips on JFLAP at the end of the document. ( • )You can assume that any input given to your machine will have the correct shape, so you do not need to check for the input having a valid form. ( . )(8 marks) [E1-Qa1.jff] Build a deterministic Turing machine that takes two words w1, w2 ∈ {a, b, c, d}* (a) separated by a # symbol in the form Bw1#w2B and determines (by accepting/rejecting) whether string w2 is a substring of w1. (b) (8 marks) [E1-Qb1.jff] Build a deterministic Turing machine that takes an input string w ∈ {a, b, c, d}* , and replaces it with wr, the reverse of w. After reversing the string, the machine must accept. For example: · When run on input BabcdabcdB, it should leave BdcbadcbaB on the tape. · When run on input BaaaaaaaaB, it should output BaaaaaaaaB. · When run on input BabccdabcddacB, it should output BcaddcbadccbaB. Remember the output starts on the symbol the head is left until the first blank on the right. Also recall the machine must always accept (after producing the output, of course!). (c) ( 1 )(4 marks) [E1-Qc1.jff] Combine your machines to produce a single deterministic machine that takes an input of the form Bw1#w2B and if if w2 is a substring of w1, it replaces w1 with wr and accepts; otherwise (if w2 is not a substring of w1), the machine rejects. When rejecting, it does not matter what is left on the tape (i.e., the tape can be left in any way). For example: Exercise 2: Undecidability20 marks Let L = {M | M is a TM that halts leaving exactly two words on its tape in the form Bw1Bw2B}. (a) (15 marks) You have seen the proof in class that AT M , the problem of deciding whether an arbitrary Turing machine will accept an arbitrary input, is undecidable. Use this result to prove, formally using problem reduction, that given an arbitrary Turing machine M , the problem of deciding if M ∈ L is undecidable. (b) (5 marks) Is L1 recursive, recursively enumerable, non-recursively enumerable, uncomputable? Justify your answer. Exercise 3: Complexity25 marks (a) (6 marks) Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time O(h(g(n)) + c), for any constant c ≥ 0 and any non-decreasing functions g(n) and h(n). (b) ( R ELEMENTARY . . . 2EXPTIME EXPSPACE EXPTIME PSPACE NPC PTIME LOG Space LOG Time )(14 marks) A cutting-edge publisher based in Melbourne is publishing a book on complexity theory. They learnt that you are taking Computing Theory at RMIT, so they offered you a very well paid job! For the job, you are asked to write the part of the book that explains the following picture: \ Some tips for JFLAP: ( • )JFLAP has a number of shortcuts that you can use to avoid having to use too many transitions. For instance, the ! ( Page 2 of 7 ) symbol can be used to indicate “anything but”. So if you wanted to move the head right on the string until it reaches th ( Version: September 15, 2019 ) ( Exercise 1 continues on the next page. . . ) character a, you can use the transition (!a/ ∼, R). Here, ∼ tells JFLAP to use the last character read. In order to move until the next blank use the transition (!/ ∼, R) — JFLAP inserts the blank symbol automatically. ( { } ∪ { }∪{ } ) ( ∼ ∼ { } { } ) ( • )Keep in mind though, that you cannot combine these transitions to say “anything but a or b” by having the transitions (qi, !a) = (qi, , R) and (qi, !b) = (qi, , R). This is because if the input alphabet is Σ = a, b, c, d , L1 = a and L2 = b , then L1 L2 = b, c, d a, c, d = Σ, the entire input alphabet! If you need to do this with two characters, you have to put them all in manually, I’m afraid.. ( • )As the ! symbol is now reserved for “anything but”, you can no longer use it to mean λ or “blank”, as you could with regular expressions! The symbol that JFLAP uses for blank symbol is Q. Never copy-and-paste these symbols from PDF documents like this one, as you will get a wrong encoding and symbol in JFLAP. ( • )There is a way to save yourself from clicking “Step” a million times when testing your machine if you only want to see the final tape output. Go to “Input/Multiple Run” (or Multiple Run (Transducer), it does not matter which) and put your inputs in.Click “Run Inputs” and once it has finished running them, select the input you want to check the output for and click “View Trace”. That should give you a pop-up window with the state that it ended up in and the tape output when the machine halted. ( • )When combining your machines, with both of the files open, go to Convert/Combine Automata and then select the other file. JFLAP will put both of your machines in a new window. You will still have to make some modifications to make them play nicely together, but it will save you having to re-create everything from scratch! ( • )There are a number of other shortcuts that JFLAP uses, although they are reasonably fiddly and might not work under every circumstance