RGPV 2015 PYQ
Q. State and explain the properties of transition functions ?
Ans. A transition function is defined on every state for every input symbol.
Transition Function (δ) is defined as δ = Q X Σ –> Q.
Where,
- Q is set of all states.
- Σ is set of input symbols.
Properties of transition functions:
1. Domain and Range
- Domain: The transition function is a function that maps each state in the set Q and each input symbol in the set Σ to a state in the set Q. In other words, the domain of the transition function is Q x Σ.
- Range: The range of the transition function is Q.
2. Determinism
The transition function must be deterministic. This means that for each state and input symbol, the transition function must specify a unique next state. In other words, there cannot be two different next states for the same state and input symbol.
3. Totality
The transition function must be total. This means that for every state and every input symbol, the transition function must specify a next state. In other words, there cannot be any state and input symbol pairs that are not defined in the transition function.
4. Consistency with Accepting States
The transition function must be consistent with the set of accepting states. This means that if the DFA is in an accepting state and it reads an input symbol, then it must transition to another accepting state. In other words, it is not possible for the DFA to transition from an accepting state to a non-accepting state.
5. Unique Next State
The transition function must always lead to a unique next state for any given state and input symbol combination. This ensures that the behavior of the DFA is predictable and consistent.
Property 1: δ(q,Λ) = q. It means the state of a system can be changed by an input symbol.
Property 2: For all strings w and input symbol a,
δ(q, aw) = δ(δ(q,a),w)
δ(q, wa) = δ(δ(q,w), a)
It means the state after the automaton consumes or reads the first symbol of a string aw and the state after the automaton consumes a prefix of the string wa.
References:
- Introduction to the Theory of Computation” by Michael Sipser.