Definition
Deterministic Finite Automaton
A deterministic finite automaton (DFA) is a automaton that has a finite number of states and the transition function
is deterministic. where:
is a finite set of states, is the input alphabet, is the total transition function is the initial state, and is the set of accepting (final) states (subset of ). It processes input symbols (or strings) by transitioning between states according to
and determines acceptance based on whether the final state is in . All deterministic finite automata are nondeterministic finite automaton.
Examples
A deterministic finite automaton
The following automaton is defined by the following quintuple:
The transition function
can be described using an operation table:
State Symbol Next State
Trap state
Let
be a deterministic finite automaton and let satisfy Then
is called a trap state. For example, consider the following DFA:
This automaton accepts exactly
After any further symbol, the automaton enters the trap state
and remains there.