Deterministic Finite-State Automaton
Deterministic Finite-State Automaton (DFA) are a method of modelling computation, and are used in conjunction with regular languages. In a DFA from each pair of input symbol and state there is only one transition to a next state (so, from any state given an input symbol the next state can be readily determined).
As an input a DFA will expect a string of symbols, each input symbol will cause a transition to a next state, until there are no more input symbols. At this point the DFA will either be on an accept state, or a non accept state - and will return "accept" or "non accept" accordingley.
It follows that the DFA 
recognises the language 
if 
, and where any DFA accepts the langauge , must be a regular lanaguage.
The diagram above shows an example of a DFA, in this case the machine accepts any words ending in a '1'.
The formal definition of a DFA, , is 
such that
is a finite set of states (in the example 
)
is a finite alphabet (in the example 
)
is the transition function (a table showing the continuation paths from any given state)
is the start state, where 
( 
in the example )
is the set of accept states ( 
in the example )
DFAs can be constructed for numerous problems, and there is no fixed method for constructing one.
Minimisation of a DFA
Minimising a DFA can help reduce the overall number of states in the DFA but maintain the same pattern of input. The algorithm for reducing a DFA to its minimal form is generally:
- Remove all the states that are not reachable from the start state.
- Contract a set of states that are equivalent into a single state. (Two states are equivalent if there is no word that is accepted when starting from one of the states, but rejected when starting from the other). Formally two states s and t are equivalent if:
One model for minimising a DFA is the Team Splitting Algorithm which will always find the minimal DFA equivalent to the original.