RGPV PYQ 2010
A trap state, which may also be called non-halting or absorbing state, is a state from which a finite automaton (FA) or pushdown automaton (PDA) cannot transit. In the event that an FA or PDA goes to a trap state, it stays there forever and hence making the machine halt. Error conditions or simplifying the automaton design are some of the reasons why trap states are often used.
If a transition leads to a state from which it can never escape. such a state is called a trap state. Trap state is also known as Dead state.
- In DFA below, state C is a trap state.
- From C no input is going to another state.
Some properties of trap states include:
1. Trap states are non-halting: Once an FA or PDA enters a trap state, it remains in that state indefinitely.
2. Trap states are absorbing: Once an FA or PDA enters a trap state, it cannot transition to any other state.
3. Trap states can represent error conditions: Trap states can be used to represent error conditions, such as encountering an invalid input symbol or reaching a contradictory state.
4. Trap states can simplify the design of automata: Trap states can be used to simplify the design of automata by eliminating transitions that would lead to error conditions or complex behavior.
- Introduction to the Theory of Computation” by Michael Sipser.