deterministic finite automaton

A deterministic finite automaton (DFA) is a kind of finite automata where there’s exact one transition for every state and input symbol. In other word, for a given input, the transition is deterministic.

Transition Function

The transition function take two arguments: a state and an input symbol.

For DFA, the transition function is a total function and there is always a next state for every input. The transition function is also deterministic (as the name DFA suggest), which means that there’s a unique transition for every state and input symbol.

To model a situation where a state has “no valid transitions,” we typically introduce a dead state: a non-accepting state that transitions to itself on every input. Once entered, the automaton cannot leave the dead state.

Formal Definition

A DFA is a tuple )

1. A finite set of states
2. An input alphabet
3. A transition function
4. A start state
5. A set of accepting (or final) states

Let be a string over alphabet . The automation accepts the string if there is a sequence of states exists in with the following properties:

• ( is the start state)
• , for
• ( is an accepting state)

See Also

• nondeterministic finite automaton
• equivalence of DFAs, NFAs, and regular expressions