Scribd Logo
Upload

Welcome to Scribd!

  • 58 views

    Assignment 3

    Uploaded by

    William Porter
    This document provides instructions for Computing Theory Assignment 3. It is an individual assignment worth 100 marks due on Friday May 31st at 11:59pm. Students are expected to complete their own original work and not plagiarize. When asked to briefly explain something 1-3 sentences are expected, when asked to explain or justify something 1-2 paragraphs are expected, and when asked to prove or show something a formal proof is expected. Submissions must be a single PDF file called ct13ass3.pdf. No questions about the assignment will be answered within 24 hours of the deadline.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Assignment 3

    Uploaded by

    William Porter
    58 views2 pages
    This document provides instructions for Computing Theory Assignment 3. It is an individual assignment worth 100 marks due on Friday May 31st at 11:59pm. Students are expected to complete their own original work and not plagiarize. When asked to briefly explain something 1-3 sentences are expected, when asked to explain or justify something 1-2 paragraphs are expected, and when asked to prove or show something a formal proof is expected. Submissions must be a single PDF file called ct13ass3.pdf. No questions about the assignment will be answered within 24 hours of the deadline.

    Original Description:

    This is 2013 assignment details

    Original Title

    assignment3

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides instructions for Computing Theory Assignment 3. It is an individual assignment worth 100 marks due on Friday May 31st at 11:59pm. Students are expected to complete their own original work and not plagiarize. When asked to briefly explain something 1-3 sentences are expected, when asked to explain or justify something 1-2 paragraphs are expected, and when asked to prove or show something a formal proof is expected. Submissions must be a single PDF file called ct13ass3.pdf. No questions about the assignment will be answered within 24 hours of the deadline.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    58 views2 pages

    Assignment 3

    Uploaded by

    William Porter
    This document provides instructions for Computing Theory Assignment 3. It is an individual assignment worth 100 marks due on Friday May 31st at 11:59pm. Students are expected to complete their own original work and not plagiarize. When asked to briefly explain something 1-3 sentences are expected, when asked to explain or justify something 1-2 paragraphs are expected, and when asked to prove or show something a formal proof is expected. Submissions must be a single PDF file called ct13ass3.pdf. No questions about the assignment will be answered within 24 hours of the deadline.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    COSC1105/1107 - Computing Theory Assignment 3 (15%)

    Total marks: 100 Deadline: Friday 31st May, 11:59pm

    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 students work (even if the other student explains it to you rst.) and never give your written work to others. Never copy from the web or any other resource. Remember you are meant to generate the solution to the questions by yourself. Suspected collusion or plagiarism will be dealt with according to RMIT University policy. When asked to briey explain something, or to describe something informally, an answer of one to three English sentences is expected. When asked to explain or justify something, an answer of one or two English paragraphs is expected. When asked to prove or show something, a formal proof or argument is expected. Submission Instructions: You are required to submit via WebLearn one PDF le called ct13ass3.pdf. Such les must be typeset in a Word processor (for example, scanned les will not be marked). Submissions that are not PDF les will not be marked. Silent Policy: A silent policy will take effect 24 hours before this assignment is due. This means that no question about this assignment will be answered, whether it is asked on the newsgroup, by email, or in person.

    E XERCISE 1: T URING M ACHINES


    Q1. Consider the following Turing Machine M : a/a,R,b/b,R,Y/Y,R Y/Y,L B/B,R a/X,R a/X,R a/X,R c/c,L b/Y,L a/a,L X/X,R q9 b/b,L

    [35 marks]

    q0

    q1

    q2

    q3

    q4

    q5

    q6 X/X,R q7 c/c,R q8 c/c,R Y/Y,R

    a/a,L

    Here, a transition of the form a/X,R means that when the head is reading a, M can legally write X and move right. (a) Trace the computation of M on input string aaabbcc by completing the following derivation: q0 BaaabbccB Is the input string accepted? 1 q1 BaaabbccB

    (b) (c) (d) (e) (f)

    Explain informally, the working of the machine M . Give the language L(M ) over the alphabet = {a, b, c} accepted by M in set notation. Give a grammar that expresses the same language as M . Where does your grammar t in the Chomsky Hierarchy? Does there exist a PDA which accepts L(M )? Briey explain in one sentence. We obtain Turing Machine M by modifying M as follows: (a) add transition b/Y,R from state q7 to q7 ; and (b) replace loop transition c/c,R in state q8 by loop transition c/a,R. Give the language L(M ) in set notation. Explain your reasoning.

    Q2. Show formally, by resorting to problem reduction, that the problem of deciding if a Turing machine halts on some input of even length is undecidable.

    E XERCISE 2: AUTOMATA
    Q1. Consider the NFA M below over the alphabet = {a, b, c}. Note that stands for the empty string. a q b b c c a (a) (b) (c) (d) a s

    [30 marks]

    Show all the executions of M over the input bcb and cbc. Are the strings accepted or rejected? Give the -closure for the states p, q , r, and s. Give a regular expression R such that L(R) = L(M ). Use subset construction technique to convert M to a DFA.

    Q2. Let L2 = {ai b3j | i, j 0} be a language over the alphabet = {a, b}. Show that L2 is a regular language.

    E XERCISE 3: C OMPLEXITY

    [35 marks]

    Q1. Suppose you are studying the computational complexity of a given problem X . It is known that the boolean satisability problem can be reduced to X in polynomial time. In addition, it is known that problem X is in class PSPACE, as somebody have developed an algorithm for X that is guaranteed to consume no more than polynomial amount of space. How would you prove that: (a) X is NP-COMPLETE. (b) X is PSPACE-COMPLETE. Observe that you do not need to develop any proof, but just explain in one short sentence what task would you do. Q2. Let X1 and X2 be two decision problems. Suppose it is known that X1 is NP-COMPLETE. Suppose further that there exists an exponential reduction of problem X1 into problem X2 , that is, there exists a function f : X1 X2 , whose implementation runs in exponential time, such that for any given instance x1 of X1 the answer to x1 is Yes for problem X1 if and only if the answer to f (x1 ) is Yes for problem X2 . What can be said about the computation complexity of the problem X2 . Is X2 NP-HARD? Explain in one or two paragraphs. 2

    You might also like