<PERSON>, <PERSON> is posting a question here just because his Computer Theory Teacher <PERSON> send to him a work that worth 20% his semester Grade. His has to deliver this at 4th November. But his already has 14 days before today to come here and start asking questions, but he could not because he took one of most difficult subjects that exists at his Computer Science course, beyond himself take all subjects that any sanity human could complete at the same time.
Now to <PERSON>, that first part:
// Stage 1: Check length is even, change as / bs to As / Bs
and
// Stage 2: Change As and Bs in first half to as and bs
Are to find the word middle, then just compare the first half against the second half. 674
Here is a SIMILAR picture for you at JFLAP:
As you can see, at state "q2", I came back to the tape's beginning, to really starts the computation at the state "q3".
After got at the state "q3" you can jump straight to you algorithm part:
"// Stage 3: Compare first and second halves"
And complete your Turing Machine. But this was your question 1.a) and now you want to solve the question 2.a)
To do it, you will only need to use the step "// Stage 3: Compare first and second halves", from you algorithm.
To do it using a Multi-Tape Turing Machine, you are going to need 4 tapes, the word is to be placed at the tape 1 and the others tapes must to be clean, i.e., contain only blank symbols:
First step, if the tape 1 has only the blank symbol, accept the language.
Second step, if the only symbol not marked at tape 1 is the blank symbol, reject the language.
Third step, is to copy the first symbol not marked from the tape 1 to the tape's 2 end. Then mark it at the tape 1.
Fourth step, is to copy the whole tape 1 to the tape's 3, and the tape 2 to the tape 4.
Fifth step, is to compare both tapes 3 and 4 are equal using yours algorithm step "// Stage 3: Compare first and second halves", but instead of failing to accept the language, go to the step Sixth.
Sixth step, if they are equal accept the language. If they are not, go to the Second step. 242