Grafstate state-to-state notation
State-to-state notation is a Grafstate notation for describing a transition in GNFAs , PDAs , and Turing machines . A transition in state-to-state notation is composed of two parts∶
|
|
Parts 1 and 2 are separated by a colon (
: ).The state-to-state part
The state-to-state part defines the current state qc and the destination state qd. If a transition goes from state qc to sate qd, then the state-to-state part of the transition is∶
qc->qd: A self-loop on state qc could be written as qc->qc: , or it could be abbreviated as qc: . |
The instruction part
The instruction part of the transition describes how input is read and how memory is used. The description of the instruction part of a transition is printed as a label on the edge representing the transition in the state diagram.
Machine type | Instruction part | Grafstate code for a transition |
|---|---|---|
A regular expression | q1->q2:(a\ub)* | |
The instruction has 3 components∶ 1 read from input 2 pop from the stack 3 push to the stack | q1->q2:a,\e->a | |
The instruction has 3 components∶ 1 read from the tape 2 write to the tape 3 move the tape head | q1->q2:a->\_,R |
 | Elements appearing to the left of a right arrow are input parameters to the transition function δ, and elements to the right of a right arrow are output parameters from δ. |
| In other words, elements appearing to the left of a right arrow are conditions that must be met for a transition to be executed. Elements to the right of a right arrow represent actions that occur after a transition has been chosen. |
 | For the transition qi⟶qj in a Turing machine to be executed, the computation must be in state qi and the tape head must be pointing to a sector containing the symbol a. Once this transition is selected as the next step, the tape head writes b and moves one sector to the right; then, the computation enters state qj. |
| For details of a particular type of transition, see the specific page for that machine type. |