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 (q₀, q₁, q₁, q₂) and the string is accepted. Conversely, the string w="010" results in these transitions (q₀, q₁, q₂, q₁) and the string is rejected. 

This makes it possible to predict the automaton's behavior deterministically.