A Deterministic Finite Automaton (DFA) consists of a finite set of states and a set of transitions from one state to another state on input symbols selected from an alphabet S.
- The initial state is generally denoted by q0.
- For each input symbol there is one transition for each state.
- There are one or more “final” or “accepting” states.
The term “deterministic” says that for each input symbol, there is one and only one state to which the automaton can transit from its current state.
In case of “non-deterministic” FA the machine can make transit to zero or one or more states on the same input symbol.
A finite automaton is formally defined by a 5-tuple (Q, Σ, δ, q0, F),
where,
Reference: “Introduction to the Theory of Computation” by Michael Sipser
- Q → Finite set of states.
- Σ → Finite set of input symbols.
- δ → Transition function mapping Q × Σ to Q.
- q0 → Initial state and q0 ∈ Q.
- F → Set of final state/states. It is assumed that there may be more than one final state. F ⊆ Q.
An explanation of components of a DFA:
- States (Q): The states are the different possible configurations of the DFA. The DFA can be in one state at a time.
- Input symbols(Σ): The input symbols are the symbols that the DFA can read. The DFA can read one input symbol at a time.
- Transition function(δ): The transition function tells the DFA what to do when it reads an input symbol. For each state and input symbol, the transition function specifies the next state that the DFA should enter.
- Start state(q0): The start state is the state that the DFA is in when it starts processing a string.
- Accepting states(F): The accepting states are the states that the DFA can be in when it finishes processing a string. If the DFA is in an accepting state when it finishes processing a string, then the string is accepted.
The finite automation has a input tape divided into units, each containing one symbol of the input string which is built from symbols of alphabet Σ.
The start of tape is indicated by ‘#’ and end is indicated by ‘$’.
- The tape may be finite or infinite.
- In case of infinite tape, the tape end marker is absent.
- The input string to be processed is stored from left to right direction.
- The reading head examines one unit at a time and can move one unit in only one direction generally, left to right.
- The current state ‘q’ and input symbol read by reading head are given as input to the finite control unit.
- The machine may remain in the same state q or transit to a new state and the reading head moves one unit ahead to read the next input symbol.
- This transition is denoted as: δ(qi, a) → qj
References:
- Introduction to the Theory of Computation” by Michael Sipser.