http://wiki.karljones.com/index.php?action=history&feed=atom&title=Deterministic_finite_automaton 2026-10-23T14:27:41Z Revision history for this page on the wiki MediaWiki 1.24.2 http://wiki.karljones.com/index.php?title=Deterministic_finite_automaton&diff=17323&oldid=prev 2016-08-26T22:28:15Z

<p>Created page with &quot;In <a href="/index.php/Theory_of_computation" title="Theory of computation">theory of computation</a>, a branch of <a href="/index.php/Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, a &#039;&#039;&#039;deterministic finite automaton&#039;&#039;&#039; (&#039;&#039;&#039;DFA&#039;&#039;&#039;) — also known as &#039;&#039;&#039;deterministic finite accept...&quot;</p> <p><b>New page</b></p><div>In [[theory of computation]], a branch of [[theoretical computer science]], a '''deterministic finite automaton''' ('''DFA''') — also known as '''deterministic finite accepter''' (DFA) and '''deterministic finite state machine''' — is a [[finite-state machine]] that accepts/rejects finite strings of [[Symbol|symbols]] and only produces a unique computation (or run) of the automaton for each input string.<br /> <br /> 'Deterministic' refers to the uniqueness of the computation.<br /> <br /> == Description ==<br /> <br /> In search of simplest models to capture the finite state machines, McCulloch and Pitts were among the first researchers to introduce a concept similar to finite automaton in 1943.<br /> <br /> A DFA is defined as an abstract mathematical concept, but is often implemented in hardware and software for solving various specific problems. For example, a DFA can model software that decides whether or not online user-input such as email addresses are valid.<br /> <br /> DFAs recognize exactly the set of regular languages, which are, among other things, useful for doing lexical analysis and pattern matching.<br /> <br /> DFAs can be built from [[Nondeterministic finite automaton|nondeterministic finite automata]] (NFAs) using the powerset construction method.<br /> <br /> == See also ==<br /> <br /> * [[Acyclic deterministic finite automata]]<br /> * [[DFA minimization]]<br /> * [[Finite-state machine]]<br /> * [[Monadic second-order logic]]<br /> * [[NFA to DFA conversion]]<br /> * [[Nondeterministic finite automaton]]<br /> * [[Quantum finite automata]]<br /> * [[Read-only right moving Turing machines]]<br /> * [[Separating words problem]]<br /> * [[Turing machine]]<br /> * [[Two-way deterministic finite automaton]]<br /> <br /> == External links ==<br /> <br /> * [https://en.wikipedia.org/wiki/Deterministic_finite_automaton Deterministic finite automaton]<br /> <br /> [[Category:Computer science]]<br /> [[Category:Computing]]</div>

Karl Jones