Content deleted Content added
m Open access bot: doi updated in citation with #oabot. |
→Notes: improving some citations |
||
Line 4:
[[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.<ref name="Hopcroft 2001">[[Deterministic finite automaton#HMU|Hopcroft 2001]]
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.
Line 117:
* the DFA with a minimum number of states for a particular regular language (Minimization Problem)
DFAs are equivalent in computing power to [[nondeterministic finite automata]] (NFAs). This is because, firstly any DFA is also an NFA, so an NFA can do what a DFA can do. Also, given an NFA, using the [[powerset construction]] one can build a DFA that recognizes the same language as the NFA, although the DFA could have exponentially larger number of states than the NFA.<ref name=Sak105>Sakarovitch (2009) p.105</ref><ref name=Law63>Lawson (2004) p.63</ref> However, even though NFAs are computationally equivalent to DFAs, the above-mentioned problems are not necessarily solved efficiently also for NFAs. The non-universality problem for NFAs is [[PSPACE complete]] since there are small NFAs with shortest rejecting word in exponential size. A DFA is universal if and only if all states are final states, but this does not hold for NFAs. The Equality, Inclusion and Minimization Problems are also PSPACE complete since they require forming the complement of an NFA which results in an exponential blow up of size.<ref>{{Cite web |last=Esparza Estaun |first=Francisco Javier |last2=Sickert |first2=Salomon |last3=Blondin |first3=Michael |date=16 November 2016 |orig-date= |title=Operations and tests on sets: Implementation on DFAs |url=https://www7.in.tum.de/um/courses/auto/ws1718/slides1718/04-Implementations_sets.pdf
On the other hand, finite-state automata are of strictly limited power in the languages they can recognize; many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. The classic example of a simply described language that no DFA can recognize is bracket or [[Dyck language]], i.e., the language that consists of properly paired brackets such as word "(()())". Intuitively, no DFA can recognize the Dyck language because DFAs are not capable of counting: a DFA-like automaton needs to have a state to represent any possible number of "currently open" parentheses, meaning it would need an unbounded number of states. Another simpler example is the language consisting of strings of the form ''a<sup>n</sup>b<sup>n</sup>'' for some finite but arbitrary number of ''a'''s, followed by an equal number of ''b'''s.<ref name=Law46>Lawson (2004) p.46</ref>
Line 231:
==References==
* {{cite book |last1=Hopcroft |first1=John E. |author-link1=John Hopcroft |last2=Motwani |first2=Rajeev |author-link2=Rajeev Motwani |last3=Ullman |first3=Jeffrey D. |author-link3=Jeffrey Ullman |title=[[Introduction to Automata Theory, Languages, and Computation]] |edition=2 |publication-place=Boston |url= |access-date= |archive-url= |archive-date= |url-status=dead |publisher=[[Addison Wesley]] |year=2001 |isbn=0-201-44124-1 |ref=HMU |postscript=. [http://web.archive.org/web/20150924071109/http://www.pearsonhighered.com/educator/product/Introduction-to-Automata-Theory-Languages-and-Computation/9780201441246.page Archived] from the original on 24 September 2015.}}
* {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=1-58488-255-7 | zbl=1086.68074 }}
* {{cite journal
| |||