deterministic automaton


Also found in: Wikipedia.

deterministic automaton

(theory)
A finite-state automaton in which the overall course of the computation is completely determined by the program, the starting state, and the initial inputs. The class of problems solvable by such automata is the class P (see polynomial-time algorithm).

Deterministic Automaton

 

a mathematical model of a system whose states change discretely with time in such a way that every state of the system is completely defined by the previous state and the input signal. A deterministic automaton is formally described in the form of the function f(Si, aj) = ak, where si is the input signal and aj is the previous state. A typical example of a deterministic automation is a digital computer, in which the state of all registers and cells is determined by their previous state and by the input signals. Deterministic automatons are a natural form for describing the logical structure of discrete computing devices. Conversion to nondeterministic automatons is possible both by the introduction of the probabilities of a change of states and by the free selection of the next state.

References in periodicals archive ?
Some fact: For each automaton an equivalent deterministic automaton can be created.
For an assertion graph G, we construct a corresponding finite-state automaton [M.sub.G] such that [L.sup.*](G) = [[summation].sup.*] - [L.sup.*]([M.sub.G]) and [L.sup.[omega]](G) = [[summation].sup.[omega]] - [L.sup.[omega]]([M.sub.G]), the number of states in [M.sub.G] is only twice as many as that in G, and a deterministic assertion graph is transformed to a deterministic automaton. On the other hand, for an arbitrary finite-state automaton M, we construct a corresponding assertion graph [G.sub.M] such that [L.sup.*]([G.sub.M]) = [[summation].sup.*] - [L.sup.*](M) and [L.sup.[omega]]([G.sub.M]) = [[summation].sup.[omega]] - [L.sup.[omega]](M), the number of states in [G.sub.M] is the same as that in M, and a deterministic automaton is transformed to a deterministic assertion graph.
Hopcroft (1971) has given an algorithm that computes the minimal automaton of a given deterministic automaton. The running time of the algorithm is O([absolute value of A] x n log n) where [absolute value of A] is the cardinality of the alphabet and n is the number of states of the given automaton.
Given a deterministic automaton A, Hopcroft's algorithm computes the coarsest congruence which saturates the set F of final states.
Cal designed an essentially deterministic automaton (Figure 9).
It is shown that an elementary soliton graph defines a deterministic automaton iff it reduces to a graph not containing even-length cycles.
1985] built on a string S is a deterministic automaton able to recognize all the substrings of S.
In contrast, a deterministic automaton has a single run on w.
Proof: For each n [greater than or equal to] 0 we construct a deterministic automaton that accepts all words of length at most n in the complement of [Q.sub.k].
Let [T.sub.U] be the ordinary trie representing the set U, seen as a finite deterministic automaton (Q, [delta], [epsilon], T) where the set of states is Q = Pref (u) (prefixes of words in u), the initial state is [epsilon], the set of final states is T = [A.sup.*] [intersection] Pref (u) and the transition function [delta] is defined on Pref (U) x A by
Let D = (Q, [q.sub.0], [Delta], F) be a deterministic automaton. Let [f.sub.w] be the function induced by a word w on Q.
Because they are deterministic automatons, computers struggle to generate numbers that are truly random.

Full browser ?