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,
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.
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
Q1: What is a DFA?
Ans: DFA stands for Deterministic Finite Automaton. It is a mathematical model used to recognize patterns in input sequences.
Q2: What are the components of a DFA?
Ans: A DFA has five components:
- A finite set of states.
- A finite set of input symbols.
- A transition function that maps each state and input symbol pair to a new state.
- A start state, which is the initial state of the DFA.
- A set of accept states, which are the states that indicate the input sequence is recognized.