Content deleted Content added
Line 5:
[[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.
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.
| |||