# Deterministic finite automaton

## Finite-state machine / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short, summarize this topic like I'm... Ten years old or a College student

In the theory of computation, a branch of theoretical computer science, a **deterministic finite automaton** (**DFA**)—also known as **deterministic finite acceptor** (**DFA**), **deterministic finite-state machine** (**DFSM**), or **deterministic finite-state automaton** (**DFSA**)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string.[1] *Deterministic* refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.[2][3]

The figure illustrates a deterministic finite automaton using a state diagram. In this example automaton, there are three states: S_{0}, S_{1}, and S_{2} (denoted graphically by circles). The automaton takes a finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading out to a next state for both 0 and 1. Upon reading a symbol, a DFA jumps *deterministically* from one state to another by following the transition arrow. For example, if the automaton is currently in state S_{0} and the current input symbol is 1, then it deterministically jumps to state S_{1}. A DFA has a *start state* (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of *accept states* (denoted graphically by a double circle) which help define when a computation is successful.

A DFA is defined as an abstract mathematical concept, but is often implemented in hardware and software for solving various specific problems such as lexical analysis and pattern matching. For example, a DFA can model software that decides whether or not online user input such as email addresses are syntactically valid.[4]

DFAs have been generalized to *nondeterministic finite automata (NFA)* which may have several arrows of the same label starting from a state. Using the powerset construction method, every NFA can be translated to a DFA that recognizes the same language. DFAs, and NFAs as well, recognize exactly the set of regular languages.[1]