Deterministic Finite Automaton
A Deterministic Finite Automaton (DFA) is a type of finite automaton where, for each combination of a current state and an input symbol, there is exactly one next state. The transition from one state to another is uniquely determined by the current state and the input symbol. Here’s an example of a DFA:
Formal Definition.
Deterministic Finite automaton is formally defined by the quintuple (Q, ∑, δ, q0, F)
Where,
- Q is finite set called States.
- ∑ is finite set called the alphabet.
- δ : Q × ∑ = Q is the transition function.
- q0 is the start state or initial state and
- F ⊆ Q the set of final states or accept states.
Example DFA:
Consider a DFA that recognizes binary strings with an even number of 0s. The components are as follows:
- States (Q): {q0, q1}
- Alphabet (Σ): {0, 1}
- Transition Function (δ):
- δ(q0, 0) = q1
- δ(q0, 1) = q0
- δ(q1, 0) = q0
- δ(q1, 1) = q1
- Initial State (q0): The starting state is q0.
- Accepting States (F): {q0}
Description:
- States (Q): The automaton has two states, q0 and q1.
- Alphabet (Σ): The input alphabet consists of binary symbols 0 and 1.
- Transition Function (δ): Describes how the automaton transitions between states based on input symbols. For example, if the current state is q0 and the input symbol is 0, the next state is q1.
- Initial State (q0): The starting state is q0.
- Accepting States (F): The automaton accepts a string if it ends up in the accepting state q0 after processing the entire string.
Computation:
Let’s consider the input string “1100”:
- q0 (initial state) -> δ(q0, 1) = q0
- q0 -> δ(q0, 1) = q0
- q0 -> δ(q0, 0) = q1
- q1 -> δ(q1, 0) = q0 (final state)
Since the automaton ends up in the accepting state q0, the input string “1100” is accepted because it has an even number of 0s. If the number of 0s were odd, the string would not be accepted.
Points to remember:
- DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. The finite automata are called deterministic finite automata if the machine is read an input string one symbol at a time.
- In DFA, there is only one path for specific input from the current state to the next state.
- DFA does not accept the null move, i.e., the DFA cannot change state without any input character.
