Deterministic finite automaton

From Wiki @ Karl Jones dot com
Jump to: navigation, search

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

External links