3. (The following TM R computes a function from { a, b }* to { c,...

 

Transcribed Image Text:

3. (The following TM R computes a function from { a, b }* to { c, d }*, where X/X R stands for X X, R. x/xR R: > % af B/#R BIBL d/d L c/c L 91 96 x/x R BIBL #IBR 92 BIBL 95 BIBL BIBL alc L bld L 93 BIBL X/XR 94 x/BR x = {a,b} (a) (7 points) What string of length n will cause R to use the greatest number of transitions? Why? (b) (7 points) Give the function tcr. (c) (6 points) Does the TM R reduce the language L = abb(a b)* to the language Q = (cd)*cdd*? If yes, prove that the function computed by R is a reduction. If no, give a string that demonstrates that the mapping is not a reduction. 3. (The following TM R computes a function from { a, b }* to { c, d }*, where X/X R stands for X X, R. x/xR R: > % af B/#R BIBL d/d L c/c L 91 96 x/x R BIBL #IBR 92 BIBL 95 BIBL BIBL alc L bld L 93 BIBL X/XR 94 x/BR x = {a,b} (a) (7 points) What string of length n will cause R to use the greatest number of transitions? Why? (b) (7 points) Give the function tcr. (c) (6 points) Does the TM R reduce the language L = abb(a b)* to the language Q = (cd)*cdd*? If yes, prove that the function computed by R is a reduction. If no, give a string that demonstrates that the mapping is not a reduction.