Deterministic automaton

From Wikipedia, the free encyclopedia

You have new messages (last change).
It has been suggested that this article or section be merged with Deterministic computation. (Discuss)

Deterministic automaton are 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 state machine (sometimes referred to as 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.

Automata theory: formal languages and formal grammars
Chomsky
hierarchy		 Grammars Languages Minimal
automaton
Type-0 Unrestricted Recursively enumerable Turing machine
n/a (no common name) Recursive Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
Type-2 Context-free Context-free Pushdown
Type-3 Regular Regular Finite
Each category of languages or grammars is a proper subset of the category directly above it.


Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../d/e/t/Deterministic_automaton.html"