0
$\begingroup$

I'm trying to compute a language defined as { ww | w ∈ {0,1}* } in JFlap using a Multitape Turing Machine. It seems a hard problem because there is no delimiter to know when the word w is ended.

I already checked this and this question, but this didn't helped me at all. The answers from "Construct Turing Machine which accepts the language $ww$" talks about deterministic machines and one answer just cite non-deterministic, but dont give details on how this design can be achieved for the given problem.

I've found this algorithm, but this seems very confusing for me (I don't understand the first stage (for example), so I can't reproduce this answer at JFlap).

// Stage 1: Check length is even, change as / bs to As / Bs
while a or b {
    change a to A or b to B & move R
    while a or b move R
    move L
    change a to A or b to B & move L
    while a or b move L
    if A or B move R
}

// Stage 2: Change As and Bs in first half to as and bs
if Blank halt
if A or B move L
while A or B change to a or b & move L
if Blank move R

// Stage 3: Compare first and second halves
while true {
    if a {
        change a to A & move R
        while a or b or Blank move R
        change A to Blank & move L   // fail if B
        while a or b or Blank move L
        if A or B move R
    } else if b {
        ... similarly ...
    }
}
if Blank halt

Can someone clarify this question to me? How can I achieve the first stage in a multitape Turing machine? How can I proceed to solve the problem?

P.S: It must be a multitape Turing machine.

$\endgroup$
  • 3
    $\begingroup$ What do you mean by "model" a language? Why must it be a multitape machine? A single tape machine is just a multitape machine where the number of tapes is particularly small. In general, all you need to do is to come up with an algorithm and show how that can be implemented on a Turing machine. In general, dumb algorithms are easier to implement. For example, the typical nondeterministic solution involves guessing where the middle of the string is, so you can do that deterministically by just trying each option. Or computing it. $\endgroup$ – David Richerby Nov 1 '15 at 15:19
1
$\begingroup$

Regarding the 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. Here is a SIMILAR picture for you at JFLAP:

enter image description here

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: enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.