CODEWITHSUNDEEP
grammarautomataturing-machinesautomata-theory
Secret society
Secret society

Reputation: 47

Building decider and not a decider Turing machines

How to make a Turing machine graph which recognizes all words with an even number of a's but which is not a decider and nothing else. Also, how to make a decider Turing machine graph for the same language.

Upvotes: 1

Views: 334

Answers (1)

Patrick87
Patrick87

Reputation: 28312

The language of all words with an even number of a's is a regular language, so a simple two-state DFA will accept the language. The same machine is a two-state decider TM that happens not to use the tape for anything except reading input.

To turn such a decider into a recognizer-non-decider (since all deciders are recognizers, too) we must make the TM explicitly recognize strings with an odd number of a's and, rather than simply halt-reject, go into an infinite loop. This can easily be done with a single state.

Upvotes: 2

Related Questions