Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / COMP 330 - Fall 2020 - Assignment 4   Due: 11:59pm Nov 7 th

COMP 330 - Fall 2020 - Assignment 4   Due: 11:59pm Nov 7 th

Computer Science

COMP 330 - Fall 2020 - Assignment 4

 

Due: 11:59pm Nov 7 th.

 

General rules: In solving these questions you may consult books or other available notes, but you need to provide citations in that case. You can discuss high level ideas with each other, but each student must find and write her/his own solution. Copying solutions from any source, com-

 

pletely or partially, allowing others to copy your work, will not be tolerated, and will be reported to the disciplinary office.

You should upload the pdf file (either typed, or a clear and readable scan) of your solution to mycourses.

 

  1. (10 Points) Let M1 and M2 be two Turing machines. Consider the following Turing machine:

On input w:

    • Step 1: Run M1 on w. If M1 accepts w, then accept.
    • Step 2: Run M2 on w. If M2 accepts w, then accept.

What is the language of this Turing Machine? Explain.

  1. (15 Points) Let E be an enumerator for a language L with the extra property that it will print the words in an increasing order of lengths. That is it will never print a word w before a shorter word u.

Prove that L is decidable.

  1. (15 Points) Is the following language decidable[1]?

L = {hMi | M = ({1,2,...,100},{0,1},{0,1,t},δ,1,2,3) is a decider}.

1

  1. (20 Points) In the class we showed that the following language is Turing Recognizable. Prove that it is in fact decidable.

L = {hp(x)i | p(x) is a polynomial with integer coefficeints that has an integer root}.

  1. (20 Points) Without using Rice’s theorem (See Problem 28 of the textbook) prove that the following language is not decidable

L = {hMi | L(M) is finite}.

  1. (20 Points) You are allowed to use Rice’s theorem (See Problem 5.28 of the textbook) to answer this question. For each one of the following three languages, either prove that they are decidable, or prove that they are undecidable.

( a )

Lr = {hMi | L(M) is a regular language}.

( b )

LTR = {hMi | L(M) is a Turing recognizable language}.

( c )

Ld = {hMi | L(M) is a decidable language}.

2

 

[1] Recall that a TM is formally defined as (Q,Σ,Γ,δ,qstart,qaccept,qreject). A Turing Machine is called a decider if it halts on every input.

Option 1

Low Cost Option
Download this past answer in few clicks

19.99 USD

PURCHASE SOLUTION

Already member?


Option 2

Custom new solution created by our subject matter experts

GET A QUOTE