开发者

Turing Machine with non trivial states and transitions

Please give me some idea as to how to go about this

Draw a Turing machine (using 开发者_JAVA百科Sipser notation) having at least 4 nontrivial (i.e., nonrejecting) states and at least six nontrivial (i.e., not to the rejecting state) transitions.


A Turing machine has:

  • A finite number of states, of which one is accepting and one is rejecting. The task apparently requires five states (four nonrejecting (of which one must be accepting) and one rejecting). The states are usually drawn as circles, with a label (the state name) inside each. One of the states is the starting state; it is marked with an arrow pointing at it.
  • A finite input alphabet. {0, 1} or {a, b} are typical choices.
  • A finite tape alphabet, which includes a special blank symbol, all symbols from the input alphabet, and possibly more symbols (but this is not required).
  • A transition function which assigns a state, a tape symbol and a direction to each combination of a state and a tape symbol. The direction can be L (left) or R (right). A transition is drawn as an arrow from one state to another (or possibly a circular arrow from a state back to itself), and the arrow is labelled with two tape symbols and either L or R. Apparently, you need six such arrows.

The machine also has an infinite tape that is divided into cells. In each cell, there can be a symbol from the tape alphabet. The symbols that initially are on the tape are called the input to the machine. The machine has a read head that is always located over one of the cells. Let's say you have a transition arrow from state A to state B, with the symbols a, b, and R on it. That means: "If the machine is in state A and the symbol under the tape head is a, then we should replace that symbol with b, go to state B, and move the read head one cell to the right."

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜