# theory of computing.

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

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.

( 3 reviews ) Alameda, United States

Project ID: #30989380

## 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
rohitangira

hello , i just read task discription and it really jumped out on me , this is an easy task for me and i can deliver it perfectly . ********* freelance profile : https://www.freelancer.com/u/rohitangira ************ cod More

\$25 USD / hour
(66 Reviews)
5.8
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

\$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

-Greetings of the day! I have made a complete look at your requirements and would like to put forth our candidature to assist you in creating a website. I'm a professional Web Developer. Having your design ideas can he More

\$20 USD / hour
(0 Reviews)
0.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