State-transition table
In Automata Theory, a state transition table is a table describing the transtition function, T of a finite automaton. This function governs what state (or states in the case of a non-deterministic finite automaton) the automaton will move to, given an input to the machine. Given a state diagram of a finite automaton, a state transition table can be derived from it.
An example of a state transition table of machine, M is given below <div="float:right">[[Image::FSM.png]] State Diagram of machine M
| 1 | 0 | |
| S1 | S1 | S2 |
| S2 | S2 | S1 |
All the possible inputs to the machine are enumerated across the columns of the table. All the possible states are enumerated across the rows. From the state transition table given above, it is easy to see that if the machine is in S1 (the first row), and the next input is character 1, the machine will stay in S1. If a character 0 arrives, the machine will transition to S2 as denoted by the arrow from S1 to S2 in the diagram.
For a non-deterministic finite automaton(NFA), a new input may cause the machine to be in more than one state, hence its non-determinism. This is denoted in a state transition table by a set of parentheses, { } with the list of all legal states in the brackets. An example is given below,
| 1 | ε | ||
| S1 | S1 | { S2, S3 } | Φ |
| S2 | S2 | Φ | |
| S3 | S2 | S1 |
Here, a non-deterministic machine in the state S1 reading an input of 0 will cause it to be in two states at one instant, the state S2 and S3. The last column defines the legal transition of states of the special character, ε. This special character allows the NFA to move to a different state when given no input. In state S3, the NFA may move to S1 without consuming an input character. The two cases above makes the finite automaton described by this finite automaton non-deterministic.
It is possible to draw a state diagram from the table. An easy to follow steps is given below:
- Draw the circles to represent the states given.
- For each of the states, scan across the corresponding row and draw an arrow to the destination state(s). There can be multiple arrows for an input character if the automaton is an NFA.
- Designate a state as the start state. The start state is given in the formal definition of the automata.
- Designate one ot more state as the accept state. This is also given in the formal definition.
References
- Sipser, M., Introduction to the Theory of Computation, PWS Publishing Co., 1997