Content deleted Content added
m Dating maintenance tags: {{Full citation needed}} |
→top: swap out dubious source |
||
Line 8:
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>{{
| last1 = Bai |
| 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}}</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="Hopcroft 2001"/>
| |||