Article · Wikipedia archive · Last revised May 30, 2026

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.

Last revised
May 30, 2026
Read time
≈ 1 min
Length
119 w
Citations
6
Source
Wikipedia ↗

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

References

  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.