Deterministic finite automaton: Difference between revisions

Revision as of 02:32, 29 November 2024

Revision as of 02:34, 29 November 2024

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₀ is both the start state and an accept state. For example, the string "1001" leads to the state sequence S₀, S₁, S₂, S₁, S₀, 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.<ref name="Hopcroft 2001">[[Deterministic finite automaton#HMU{{sfn|Hopcroft 2001]]</ref>|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.<ref>[[Deterministic finite automaton#MP43|McCulloch and Pitts (1943)]]</ref><ref>[[Deterministic finite automaton#RS59|Rabin and Scott (1959)]]</ref>

The figure illustrates a deterministic finite automaton using a [[state diagram]]. In this example automaton, there are three states: S₀, S₁, and S₂ (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₀ and the current input symbol is 1, then it deterministically jumps to state S₁. 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.

Line 27:

| year = 2019}}</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.<ref name="{{sfn|Hopcroft 2001"/>|Motwani|Ullman|2006}}

==Formal definition==