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
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.