A deterministic finite automaton (DFA) is defined as a 5-tuple , where

1. is a finite set called the states
2. is a finite set called the alphabet,
3. is the transition function
4. is the start state
5. is the set of accept/final states.

This formal description is not very restrictive and can allow for some uncommon DFAs.

States

The minimum number of states a DFA can have is 1. This is because the formal definition requires one state to be the start state and . If this state is also an accepting state, then the DFA will accept every string in .

If this state is not an accepting state, then the DFA doesn’t accept any string.



Alphabet

The formal definition of a DFA allows an empty alphabet set. Since the transition function has to be a total function, an empty alphabet will result in an empty transition function. This restricts the number of states of such a DFA to just 1 because there isn’t any alphabet to follow a transition. If this state is also an accepting state, then the DFA will accept the empty string .

If this state is not an accepting state, then the DFA doesn’t accept any string.

Transition Function

The formal definition also allows the transition function to be defined in such a way that some states are unreachable from the start state.

In the above DFA, the transition function is total. However, the states and are unreachable from the start state and thus do not contribute in deciding whether a string is accepted by the DFA. In fact, removing these two states and their transitions will not affect the language of the DFA.

Accepting States

The set of accepting states can be empty. Such a DFA will obviously will not accept any string which makes it pointless. However, the formal definition allows to define such DFAs. In the other extreme, if all the states of the DFA are accepting, then the DFA will accept every string in .