Construct a Turing machine (Decision problems and Church-Turing Thesis)
Construct a one tape deterministic Turing machine R that reducesthe language L = x(xy)* to Q = (aa)*. Do notsolve the membership in L problem: do a reduction.
a) Write what it means for R to reduce L to Q. Use the” if, andonly, if” description of reduction employed in the text.
b) Briefly describe the strategy of your reduction machine.
c) What will be the result of your machine for the followinginputs.
Input
Resulting string
xxy
xxx
xxyxy
xxyx
yyy
d) Give the state diagram of R.
Answer