Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

share|improve this question
1  
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? – Dave Clarke Jan 30 at 13:49
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? – Straightfw Jan 30 at 13:56
1  
But that doesn't seem to answer the question. The question does not mention replacing "ba" by spaces. – Dave Clarke Jan 30 at 14:04
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! :) – Straightfw Jan 30 at 14:05
@Dave Write it as an answer? – Yuval Filmus Jan 30 at 16:23

1 Answer

up vote 2 down vote accepted

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?

share|improve this answer
Also: how it output of a Turing machine defined here? Can make a difference. – Raphael♦ Jan 30 at 17:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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