Jump to content

Deterministic automaton

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Yuriz (talk | contribs) at 12:20, 1 May 2020 (Reference correctly). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a deterministic automaton is a concept of automata theory in which 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

  1. ^ 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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Deterministic_automaton&oldid=954247226"