autotransition

Autotransition (also known as a self‑loop or identity transition) refers to a transition in a state machine that returns the system to the same state that it originates from. In the formalism of finite automata, a transition is usually represented as a tuple (current state, input symbol, next state). An autotransition occurs when the current state and next state are identical. For example, in a deterministic finite automaton (DFA), a transition labeled 'a' from state q0 back to q0 is an autotransition triggered by the input symbol 'a'.

Autotransitions are useful for modeling situations where an event does not cause a change in the system’s observable condition but may still trigger internal processing, side effects, or the passage of time. In protocol design, they allow a participant to stay in a waiting state while listening for a specific message. In computational linguistics, autotransitions can represent repeated application of a rule without altering the syntactic category. Game design and behavioral modeling frequently use self‑loops to represent idle or looped actions that maintain the current state.

In nondeterministic finite automata (NFA), autotransitions can also be defined for the empty string (ε-transitions), allowing the machine to change internal configuration without consuming input. Such ε‑autotransitions are commonly employed in the construction of ε‑NFAs from regular expressions.

Autotransitions do not change the acceptance condition of a string: a string is accepted if there exists a computation that ends in an accepting state, regardless of whether intermediate self‑loops were taken. However, they can increase the total number of states visited and therefore affect the time complexity of simulation algorithms.

Typical applications include stateful parsers that need to consume multiple identical tokens while remaining in the same syntactic context, and finite state controllers in robotics that must repeatedly check a condition while maintaining the same action.

See also: finite automaton, epsilon transition, self‑loop, state machine, deterministic finite automaton.

References

- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison‑Wesley.

- Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.