Cheap and Secure Web Hosting Provider : See Now

[Answers] Are you allowed to have empty states on Turing machine?

, , No Comments
Problem Detail: 

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?

Asked By : Straightfw

Answered By : Jan Hudec

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9318

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback