Types of Finite Automata
Finite automata can be classified into two main types: deterministic finite automaton (DFA) and nondeterministic finite automaton (NFA). These types of automata have different characteristics in terms of how they process input and make state transitions.
Deterministic Finite Automaton (DFA):
A 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. In other words, the transition from one state to another is uniquely determined by the current state and the input symbol.
Components of DFA:
- States (Q): A finite set of states.
- Alphabet (Σ): A finite set of input symbols.
- Transition Function (δ): Describes the unique transition for each state and input symbol.
- Initial State (q0): The starting state.
- Accepting States (F): A set of states where the automaton accepts the input.
Example DFA: Consider a DFA that recognizes binary strings with an even number of 0s. The components are:
- 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}
The DFA processes input symbols one by one and moves between states according to the transition function. It accepts a string if it ends up in an accepting state after processing the entire string.
Nondeterministic Finite Automaton (NFA):
An NFA is a type of finite automaton where, for a given current state and input symbol, there can be multiple possible next states. In other words, the transition from one state to another is not uniquely determined; the automaton can have choices at each step.
Components of NFA:
- States (Q): A finite set of states.
- Alphabet (Σ): A finite set of input symbols.
- Transition Function (δ): Describes the possible transitions for each state and input symbol. Multiple next states are allowed.
- Initial State (q0): The starting state.
- Accepting States (F): A set of states where the automaton accepts the input.
Example NFA: Consider an NFA that recognizes strings over the alphabet {0, 1} where every string ends with 1. The components are:
- States (Q): {q0, q1}
- Alphabet (Σ): {0, 1}
- Transition Function (δ):
- δ(q0, 0) = {q0}
- δ(q0, 1) = {q0, q1}
- δ(q1, 0) = { }
- δ(q1, 1) = { }
- Initial State (q0): The starting state is q0.
- Accepting States (F): {q1}
The NFA can have multiple choices at each transition, making it more flexible in its acceptance of strings. It accepts a string if there exists at least one path through the transitions that leads to an accepting state.
