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 I'm doing some exercises with Turing machine and quite often it happens that a given set of states can be achieved if and only if some character was met. Therefore, we may have some states q3-q7 which the machine may be pointed to if and only if we spotted a and (because of the task spec, for example), we know that we may find only some chars (say b, d but not c, e) from the input language there so there's no need to have a separate state for every symbol. Can I then just program the states I'll actually use there and have some void states or do I have to put something there (like just reprinting the found character) anyway, even though I'm 100% sure the machine will never go to the state for some symbols?

share|improve this question
5  
It is perfectly reasonable not to write down transitions you won't use. You should probably ask your instructor though (assuming you have one). I don't think there are strong conventions about this as it matters very little. – Karolis Juodelė Jan 30 at 17:32
I see. Thanks a lot :) And yeah, I do have an instructor but I'm afraid I won't be able to ask him before the exam so I'm just making sure ;) – Straightfw Jan 30 at 17:37
1  
@Straightfw, check the conventions used in your text's examples. – vonbrand Jan 30 at 18:06
Sure. Thanks :) – Straightfw Jan 30 at 19:20

1 Answer

up vote 2 down vote accepted

The output and transition functions have to be defined for all state and character combinations. But if you say you can't get into the state, it means that if you do get there, the input was invalid. Therefore simply append a definition like "and all transitions not mentioned so far are to a rejecting state" (which is an endless loop if you are doing a stop/don't stop machine).

share|improve this answer
I see. So I may as well put some "RS" in these states and then, when I'm defining the machine, state that F (final states) = {RS, AS} (Rejection State, Acceptance State), right? – Straightfw Feb 1 at 16:55
@Straightfw: Yes. And you can make all the uninteresting transitions point to RS with single sentence, so you won't have to list them and they will still be defined. – Jan Hudec Feb 1 at 20:04
You mean I could just leave the cells blank and state explicitly "All the empty cells point to RS" or is "statement" some TM-related keyword as well? Forgive me the foolish question, I'm a newbie and would like to refrain from stupid mistakes from the beginning :) – Straightfw Feb 2 at 18:48
@Straightfw: That's exactly what I mean. – Jan Hudec Feb 3 at 18:59
I see. Thank you a lot! :) – Straightfw Feb 4 at 17:45

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.