Deterministic finite automaton
In theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA) — also known as deterministic finite accepter (DFA) and deterministic finite state machine — is a finite-state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string.
'Deterministic' refers to the uniqueness of the computation.
Description
In search of simplest models to capture the finite state machines, McCulloch and Pitts were among the first researchers to introduce a concept similar to finite automaton in 1943.
A DFA is defined as an abstract mathematical concept, but is often implemented in hardware and software for solving various specific problems. For example, a DFA can model software that decides whether or not online user-input such as email addresses are valid.
DFAs recognize exactly the set of regular languages, which are, among other things, useful for doing lexical analysis and pattern matching.
DFAs can be built from nondeterministic finite automata (NFAs) using the powerset construction method.
See also
- Acyclic deterministic finite automata
- DFA minimization
- Finite-state machine
- Monadic second-order logic
- NFA to DFA conversion
- Nondeterministic finite automaton
- Quantum finite automata
- Read-only right moving Turing machines
- Separating words problem
- Turing machine
- Two-way deterministic finite automaton
