Deterministic Finite Automata
A Deterministic Finite Automaton (DFA) is a computational model where each state of the system has a precisely defined transition for every possible input.
Simply put, given a specific state and an input symbol, there is always a unique next state to which the system can transition.
The transition function maps each pair of state and input symbol to a single subsequent state.
Each state and input symbol pair has one clearly defined transition to a single next state.
Like any finite state automaton, a DFA is characterized by an initial starting state and one or more acceptance (final) states.
Practical Example
Consider an automaton that recognizes strings of '0' and '1' ending in '01'.
- Initial state: \( q_0 \)
- States: \( q_0, q_1, q_2 \)
- Alphabet: \( \{0, 1 \} \)
- Transitions:
- From \( q_0 \) with '1' stays at \( q_0 \)
- From \( q_0 \) with '0' goes to \( q_1 \)
- From \( q_1 \) with '0' stays at \( q_1 \)
- From \( q_1 \) with '1' goes to \( q_2 \)
- From \( q_2 \) with '0' goes to \( q_1 \)
- From \( q_2 \) with '1' goes to \( q_0 \) - Final state: \( q_2 \)
In each state, the automaton performs a specific action for each symbol of the alphabet.
Moreover, processing the same string results in the automaton performing the same sequence of actions.
Example. The string w="001" results in these state transitions (q0, q1, q1, q2) and the string is accepted. Conversely, the string w="010" results in these transitions (q0, q1, q2, q1) and the string is rejected.
This makes it possible to predict the automaton's behavior deterministically.
