Editing Deterministic finite automaton (section)

{{Short description|Finite-state machine}}
{{Use dmy dates|date=April 2020}}
{{Redirect-synonym|DFSA|[[drug-facilitated sexual assault]]}}
{{CS1 config|mode=cs1}}
[[File:DFA example multiplies of 3.svg|thumb|upright=1.1|An example of a deterministic finite automaton that accepts only binary numbers that are multiples of 3. The state S<sub>0</sub> is both the start state and an accept state. For example, the string "1001" leads to the state sequence S<sub>0</sub>, S<sub>1</sub>, S<sub>2</sub>, S<sub>1</sub>, S<sub>0</sub>, and is hence accepted.]]

In the [[theory of computation]], a branch of [[theoretical computer science]], a '''deterministic finite automaton''' ('''DFA''')—also known as '''[[Finite-state machine#Acceptors (recognizers)|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 (computer science)|string]] of symbols, by running through a state sequence uniquely determined by the string.{{sfn|Hopcroft|Motwani|Ullman|2006}} ''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.{{sfn|McCulloch| Pitts|1943}}{{sfn|Rabin| Scott|1959}}

The figure illustrates a deterministic finite automaton using a [[state diagram]]. In this example automaton, there are three states: S<sub>0</sub>, S<sub>1</sub>, and S<sub>2</sub> (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<sub>0</sub> and the current input symbol is 1, then it deterministically jumps to state S<sub>1</sub>. A DFA has a ''start state'' (denoted graphically by an arrow coming in from nowhere) where computations begin, and a [[set (mathematics)|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.<ref>{{citation
 | last1 = Bai | first1 = Gina R.
 | last2 = Clee | first2 = Brian
 | last3 = Shrestha | first3 = Nischal
 | last4 = Chapman | first4 = Carl
 | last5 = Wright | first5 = Cimone
 | last6 = Stolee | first6 = Kathryn T.
 | editor1-last = Guéhéneuc | editor1-first = Yann-Gaël
 | editor2-last = Khomh | editor2-first = Foutse
 | editor3-last = Sarro | editor3-first = Federica
 | contribution = Exploring tools and strategies used during regular expression composition tasks
 | contribution-url = https://par.nsf.gov/servlets/purl/10100320
 | doi = 10.1109/ICPC.2019.00039
 | pages = 197–208
 | publisher = IEEE / ACM
 | title = Proceedings of the 27th International Conference on Program Comprehension, ICPC 2019, Montreal, QC, Canada, May 25-31, 2019
 | year = 2019| isbn = 978-1-7281-1519-1
 }}</ref>

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 language]]s.{{sfn|Hopcroft|Motwani|Ullman|2006}}