请输入您要查询的字词:

 

单词 Automaton
释义

automaton


An automaton is a semiautomaton with two types of special states: starting states, and final states. Specifically, an automaton A is is a five-tuple (S,Σ,δ,I,F), where

  1. 1.

    (S,Σ,δ) is a semiautomaton,

  2. 2.

    a non-empty set IS of starting states, and

  3. 3.

    a set FS of final states or terminating states.

A triple (s,a,t) is called a transition if tδ(s,a), and is written sat. The set δ(s,a) may contain more than one element (or none at all), which is why an automaton is also said to be non-deterministic. If on the other hand δ(s,a) is a singleton for every (s,a), and I is a singleton, then A is said to be deterministicMathworldPlanetmath. In a deterministic automaton, δ can be viewed as a function from S×Σ to S.

If S and Σ are both finite, then A is called a finite-state automaton, or FSA for short.

The state diagramMathworldPlanetmath GA of a finite-state automaton A is constructed as if A is being treated as a semiautomaton. In additionPlanetmathPlanetmath, a vertex corresponding to a starting state has an incoming arrow without a source, and a vertex corresponding to a final state has an outgoing arrow without a destination (alternatively, it may be represented by a double circle). This is illustrated in the following example:

Let A be given by S={σ,s,t}, where σ is the starting state, and t the final state, Σ={a,b}, with the transition function given by the following table

Titleautomaton
Canonical nameAutomaton
Date of creation2013-03-22 12:26:34
Last modified on2013-03-22 12:26:34
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id42
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 03D05
Classificationmsc 68Q45
Synonymnext-state function
Synonymterminating state
SynonymFSA
Synonymstart state
Synonymrecognizer
Related topicDeterministicFiniteAutomaton
Related topicNonDeterministicFiniteAutomaton
Related topicPushdownAutomaton
Related topicSemiautomaton
Definesfinite-state automaton
Definestransition function
Definesstarting state
Definesfinal state
DefinesconfigurationMathworldPlanetmath
Definesacceptor
Definesautomata
Definesdeterministic automaton
\\@unrecurse
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 21:16:30