Deterministic automaton
In computer science, a deterministic automaton is a concept of automata theory where the outcome of a transition from one state to another is determined by the input.[1]: 41
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.[1]: 52
A standard way to build a deterministic finite automaton from a nondeterministic finite automaton is the powerset construction.[1]: 44
References
- ^ a b c Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 0-521-61324-8. Zbl 1127.68049.
- v
- t
- e
Automata theory: formal languages and formal grammars
Chomsky hierarchy | Grammars | Languages | Abstract machines |
|
|
Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.
P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e