Computer Science > QUESTIONS & ANSWERS > SUNY Buffalo State College-CSE396_ps10key (All)

SUNY Buffalo State College-CSE396_ps10key

Document Content and Description Below

CSE396 Problem Set 10 Answer Key Spring 2017 The Final Exam is set for Tuesday, May 16 in the lecture room, Cooke 121, 11:45am{ 2:45pm. We have decided to repeat the terms used for last year’s exa... m in the identical room: one notes binder is allowed. The textbook is not allowed, and all electronic devices are forbidden. If you must bring a backpack or other bulky bag into the room at all, it must be stowed along the side of the room. [Plus note the Review Session on Monday 5/15 from 12:00{1:50pm in NSC 228; graded PS10s will be returned there and in my 2{4pm office hours back in Davis afterward.] (1) Consider the following decision problem: Exception Throw Instance: A Java program P and an input stream x 2 ASCII ∗. Question: Does running P on x throw an ArrayIndexOutOfBoundsException? Show that this decision problem is undecidable|by arguing concretely that if it were decidable, then the Acceptance Problem for Turing machines would be decidable, which it isn’t. (It may help you to know that the Turing Kit program, though it has other bugs, never throws this exception. 18 pts.) Answer: Given a TM M and an argument w to M, define a Java program P as follows: P is the \Turing Kit" program (or JFLAP or some other Turing machine simulator) with two modifications: • It has M and w embedded in its code, so that when P starts up on any input x (which is ignored) it begins a simulation of M on input w. • Right after the line that displays the \String accepted" dialog, it has a line that throws the exception|which importantly is the only way that exception can be thrown when running P [Show More]

Last updated: 2 years ago

Preview 1 out of 2 pages

Buy Now

Instant download

We Accept: