0
$\begingroup$

So say I have a task like this:

Construct a Turing machine transforming the word u to the word v byt removing all the sequences of form "ba" from the word u. Input alphabet = {a,b,c}.

Example: for IN cabbaacba, OUT cac.

And my problem always is: can I leave blank characters in place of "ba" sequences in tasks like this so that in the end, I have something like $ca \Phi \Phi \Phi \Phi c \Phi \Phi$ on the tape or do I have to work on the tape in such a way that I end up with, for example "cac", written consecutively, without blanks?

$\endgroup$
5
  • 1
    $\begingroup$ The specification does not say that you can have spaces between the symbols in the output word. Is the blank character even in the output language? $\endgroup$ – Dave Clarke Jan 30 '13 at 13:49
  • $\begingroup$ I don't know, that's all the spec I have. If it doesn't explicitly state the output language, couldn't I just create my own by using the input one + blank symbol? $\endgroup$ – Straightfw Jan 30 '13 at 13:56
  • 1
    $\begingroup$ But that doesn't seem to answer the question. The question does not mention replacing "ba" by spaces. $\endgroup$ – Dave Clarke Jan 30 '13 at 14:04
  • $\begingroup$ I see. So it seems in such tasks I'd just have to find a way to leave only the desired characters. Thank you, then! :) $\endgroup$ – Straightfw Jan 30 '13 at 14:05
  • $\begingroup$ @Dave Write it as an answer? $\endgroup$ – Yuval Filmus Jan 30 '13 at 16:23
2
$\begingroup$

The question does not mention replacing "ba" by spaces. It does not say that you can have spaces between the symbols in the output word. Is the blank character even in the output language?

$\endgroup$
1
  • 1
    $\begingroup$ Also: how it output of a Turing machine defined here? Can make a difference. $\endgroup$ – Raphael Jan 30 '13 at 17:05

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.