theory of computing.

Cancelled Posted 2 years ago Paid on delivery
Cancelled

i need soomebody who can solve these problems

1. (35 points) Prove that L ∉ D using a reduction from H. Your proof must use a mapping

reduction function R, which defines a TM M#(x). Remember that since R transforms a

membership question in H into a membership question in L, the input to R has the syntactic form

of an element in H, and what R returns has the syntactic form of an element in L.

2. (40 points) Answer 2a or 2b, but not both.

2.a Prove that L ∉ SD using a reduction from ¬H. Your proof must use a mapping reduction

function R in the manner of question 1.

2.b Write a Python script that implements TM M#(x) in question 1, allowing the user to play

Oracle by saying whether or not M halts on w. You are free to use any and all of these Python

statements in your script:

def M(w):

if w == 'Y':

print(f'M("{w}") halts')

return #halt on w

else:

print(f'M("{w}") loops …')

while True: pass # loop on w

w = input('All-knowing Oracle, does M halt on w [Y/N]: ')

x = input('Enter a string in {a,b}*: ')

3. (10 points) ∑ = {y,n}, L = { w : w = y if after 2020, the average Earth temperature rises at

least 2° Celsius above the pre-industrial level; and w = n otherwise}. Choose the best answer

from the following possibilities, and justify your choice convincingly: L ∈ RLs; L ∈ CFLs/RLs; L ∈

D/CFLs: L ∈ SD/D; L ∉ SD.

4. (40 points) ∑={a,b}, L = { w : #ab(w) % 3 = #b(w) % 2, where #ab(w) means the number of

occurrences of the substring ab in w. For example ℇ ∈ L because #ab(ℇ) % 3 = 0 = #b(ℇ) % 2; w

= bbab ∈ L because #ab(w) % 3 = 1 = #b(w) % 3; and w = bbabbab ∉ L because #ab(w) % 3

= 2 ≠ #b(w) % 2 = 1. Use JFLAP to create a TM that accepts L. Do not use transitions from final

states.

Algorithm Computer Science Tutoring Python Automation

Project ID: #30989380

About the project

9 proposals Remote project Active 2 years ago

9 freelancers are bidding on average $26/hour for this job

umg536

Hi there, I'm bidding on your project "theory of computing. " Being an expert in Python and matlab programming I can do this project for you. please leave a message on my chat so we can discuss the budget and deadline More

$50 USD / hour
(15 Reviews)
6.4
mirzaahamza

Heyy i am expert in theory of computation and I can help you..................................................

$20 USD / hour
(25 Reviews)
4.3
hubamykytafree

Dear Client I have read your project requirements carefully. I have rich experience in Django framework. Django rest framework is powerful backend and I am sure powerful security with JWT -authentication and can combi More

$20 USD / hour
(9 Reviews)
4.0
andriimalyshenko

Hi, I'd be glad to help you. As I am an Algorithm and Python expert, I can surely complete your task,Please contact me. Thank you..

$35 USD / hour
(4 Reviews)
4.0
normanburtonfree

Hello client, I wish you the best of luck in everything with you. As a professional developer, I have many years experiences of this field. Please feel free to contact me and let’s discuss about your job in detail t More

$20 USD / hour
(9 Reviews)
4.0
shovakvv911

Hi there. How are you? I've checked your job and I am eager to work with you. First of all, my principle is to be proactive and self-motivative for clients. Second, you can have friendly conversation or chat. That's be More

$20 USD / hour
(0 Reviews)
0.0
Vadim113

:) Dear Client. :) Python and Django are my main skills. As a Python developer, I have 3+ years of good experience, So I will give you the perfect results whatever you want. I can start immediately and I will finish More

$20 USD / hour
(0 Reviews)
0.0