Deterministic automaton

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[Anderson-1] 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.

[1]