Deterministic automaton
From Wikipedia, the free encyclopedia
(Redirected from Deterministic computation)
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009) |
Deterministic automaton is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence.
A common deterministic automaton is a deterministic finite automaton (DFA)) which is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. DFAs recognize the set of regular languages and no other languages.
The standard way to build a deterministic finite automaton from a nondeterministic finite automaton is the powerset construction.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| P ≟ NP | This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it. |
