Finite-state Automaton
   HOME
*



picture info

Finite-state Automaton
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of '' states'' at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a ''transition''. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types— deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one. The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines, which dispense p ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Model Of Computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology. Models Models of computation can be classified into three categories: sequential models, functional models, and concurrent models. Sequential models Sequential models include: * Finite state machines * Post machines (Post–Turing machines and tag machines). * Pushdown automata * Register machines ** Random-access machines * Turing machines * Decision tree model Functional models Functional models include: * Abstract re ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Moore Machine
In the theory of computation, a Moore machine is a finite-state machine whose current output values are determined only by its current state. This is in contrast to a Mealy machine, whose output values are determined both by its current state and by the values of its inputs. Like other finite state machines, in Moore machines, the input typicallinfluences the next state Thus the input may indirectly influence subsequent outputs, but not the current or immediate output. The Moore machine is named after Edward F. Moore, who presented the concept in a 1956 paper, “ Gedanken-experiments on Sequential Machines.” Formal definition A Moore machine can be defined as a 6-tuple (Q, q_0, \Sigma, O, \delta, G) consisting of the following: * A finite set of states Q * A start state (also called initial state) q_0 which is an element of Q * A finite set called the input alphabet \Sigma * A finite set called the output alphabet O * A transition function \delta : Q \times \Sigma \righ ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Mealy Machine
In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose output values are determined solely by its current state. A Mealy machine is a deterministic finite-state transducer: for each state and input, at most one transition is possible. History The Mealy machine is named after George H. Mealy, who presented the concept in a 1955 paper, "A Method for Synthesizing Sequential Circuits". Formal definition A Mealy machine is a 6-tuple (S, S_0, \Sigma, \Lambda, T, G) consisting of the following: * a finite set of states S * a start state (also called initial state) S_0 which is an element of S * a finite set called the input alphabet \Sigma * a finite set called the output alphabet \Lambda * a transition function T : S \times \Sigma \rightarrow S mapping pairs of a state and an input symbol to the corresponding next state. * an output functi ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


UML State Machine
UML state machine, also known as UML statechart, is an extension of the mathematical concept of a finite automaton in computer science applications as expressed in the Unified Modeling Language (UML) notation. The concepts behind it are about organizing the way a device, computer program, or other (often technical) process works such that an entity or each of its sub-entities is always in exactly one of a number of possible states and where there are well-defined conditional transitions between these states. UML state machine is an object-based variant of Harel statechart, adapted and extended by UML.D. Drusinsky''Modelling and verification using UML statecharts'' Elsevier, 2006 The goal of UML state machines is to overcome the main limitations of traditional finite-state machines while retaining their main benefits. UML statecharts introduce the new concepts of hierarchically nested states and orthogonal regions, while extending the notion of actions. UML state machines hav ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Unified Modeling Language
The Unified Modeling Language (UML) is a general-purpose, developmental modeling language in the field of software engineering that is intended to provide a standard way to visualize the design of a system. The creation of UML was originally motivated by the desire to standardize the disparate notational systems and approaches to software design. It was developed at Rational Software in 1994–1995, with further development led by them through 1996. In 1997, UML was adopted as a standard by the Object Management Group (OMG), and has been managed by this organization ever since. In 2005, UML was also published by the International Organization for Standardization (ISO) as an approved ISO standard. Since then the standard has been periodically revised to cover the latest revision of UML. In software engineering, most practitioners do not use UML, but instead produce informal hand drawn diagrams; these diagrams, however, often include elements from UML. History Before UML 1 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Virtual Finite-state Machine
A virtual finite-state machine (VFSM) is a finite-state machine (FSM) defined in a Virtual Environment. The VFSM concept provides a software specification method to describe the behaviour of a control system using assigned names of input control properties and output actions. The VFSM method introduces an execution model and facilitates the idea of an executable specification. This technology is mainly used in complex machine control, instrumentation, and telecommunication applications. Why Implementing a state machine necessitates the generation of logical conditions (state transition conditions and action conditions). In the hardware environment, where state machines found their original use, this is trivial: all signals are Boolean. In contrast state machines specified and implemented in software require logical conditions that are per se multivalued: * Temperature could be Low, OK, High * Commands may have several values: Init, Start, Stop, Break, Continue * In a hierarchic ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Virtual Finite State Machine
A virtual finite-state machine (VFSM) is a finite-state machine (FSM) defined in a Virtual Environment. The VFSM concept provides a software specification method to describe the behaviour of a control system using assigned names of input control properties and output actions. The VFSM method introduces an execution model and facilitates the idea of an executable specification. This technology is mainly used in complex machine control, instrumentation, and telecommunication applications. Why Implementing a state machine necessitates the generation of logical conditions (state transition conditions and action conditions). In the hardware environment, where state machines found their original use, this is trivial: all signals are Boolean. In contrast state machines specified and implemented in software require logical conditions that are per se multivalued: * Temperature could be Low, OK, High * Commands may have several values: Init, Start, Stop, Break, Continue * In a hierarchic ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

State Diagram
A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction. Many forms of state diagrams exist, which differ slightly and have different semantics. Overview State diagrams are used to give an abstract description of the behavior of a system. This behavior is analyzed and represented by a series of events that can occur in one or more possible states. Hereby "each diagram usually represents objects of a single class and track the different states of its objects through the system". State diagrams can be used to graphically represent finite-state machines (also called finite automata). This was introduced by Claude Shannon and Warren Weaver in their 1949 book ''The Mathematical Theory of Communication''. Another source is Taylor Booth in hi ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Finite State Machine Example With Comments
Finite is the opposite of infinite. It may refer to: * Finite number (other) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked for person and/or tense or aspect * "Finite", a song by Sara Groves from the album ''Invisible Empires'' See also * * Nonfinite (other) Nonfinite is the opposite of finite * a nonfinite verb A nonfinite verb is a derivative form of a verb unlike finite verbs. Accordingly, nonfinite verb forms are inflected for neither number nor person, and they cannot perform action as the root ... {{disambiguation fr:Fini it:Finito ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

UML State Machine Fig5
The Unified Modeling Language (UML) is a general-purpose, developmental modeling language in the field of software engineering that is intended to provide a standard way to visualize the design of a system. The creation of UML was originally motivated by the desire to standardize the disparate notational systems and approaches to software design. It was developed at Rational Software in 1994–1995, with further development led by them through 1996. In 1997, UML was adopted as a standard by the Object Management Group (OMG), and has been managed by this organization ever since. In 2005, UML was also published by the International Organization for Standardization (ISO) as an approved ISO standard. Since then the standard has been periodically revised to cover the latest revision of UML. In software engineering, most practitioners do not use UML, but instead produce informal hand drawn diagrams; these diagrams, however, often include elements from UML. History Before UML 1 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]