Write a two-tape deterministic Turing machine to sort an input string w of the form (a+b)*....

 

Transcribed Image Text:

Write a two-tape deterministic Turing machine to sort an input string w of the form (a+b)*. The input will be given on the first tape, and the second tape will be initially empty. When the computation halts, the contents of the first tape should contain the input string in "sorted order" (i.e., all a's appear to the left of all b's). What is the big-Oh worst-case running time of your algorithm, if the length of the input string w is n? Write a two-tape deterministic Turing machine to sort an input string w of the form (a+b)*. The input will be given on the first tape, and the second tape will be initially empty. When the computation halts, the contents of the first tape should contain the input string in "sorted order" (i.e., all a's appear to the left of all b's). What is the big-Oh worst-case running time of your algorithm, if the length of the input string w is n?