In computation, a finite-state machine (FSM) is event driven if the transition from one state to another is triggered by an event or a message. This is in contrast to the parsing-theory origins of the term finite-state machine where the machine is described as consuming characters or tokens.
Often these machines are implemented as threads or processes communicating with one another as part of a larger application. For example, a telecommunication protocol is most of the time implemented as an event-driven finite-state machine.
This code describes the state machine for a very basic car radio system. It is basically an infinite loop that reads incoming events. The state machine is only 2 states: radio mode, or CD mode. The event is either a mode change from radio to cd back and forth, or a go to next (next preset for radio or next track for CD).
/********************************************************************/#include<stdio.h>/********************************************************************/typedefenum{ST_RADIO,ST_CD}STATES;typedefenum{EVT_MODE,EVT_NEXT}EVENTS;EVENTSreadEventFromMessageQueue(void);/********************************************************************/intmain(void){/* Default state is radio */STATESstate=ST_RADIO;intstationNumber=0;inttrackNumber=0;/* Infinite loop */while(1){/* Read the next incoming event. Usually this is a blocking function. */EVENTSevent=readEventFromMessageQueue();/* Switch the state and the event to execute the right transition. */switch(state){caseST_RADIO:switch(event){caseEVT_MODE:/* Change the state */state=ST_CD;break;caseEVT_NEXT:/* Increase the station number */stationNumber++;break;}break;caseST_CD:switch(event){caseEVT_MODE:/* Change the state */state=ST_RADIO;break;caseEVT_NEXT:/* Go to the next track */trackNumber++;break;}break;}}}
Ginr is an industrial-strength compiler producing multitape finite state automata from rational patterns, functions and relations expressed in semiring algebraic terms. The example below shows a binary rational function equivalent to the above example, with an additional transition (nil, radio) to set the system into its initial state. Here the input symbols nil, mode, next denote events that drive a transducer with output effectors cd, nextTrack, radio, nextStation. Expressions like this are generally much easier to express and maintain than explicit listings of transitions.
StateMachine = ( (nil, radio) ( (mode, cd) (next, nextTrack)* (mode, radio) (next, nextStation)* )* ( (mode, cd) (next, nextTrack)* )? );
Compilation produces a subsequential (single-valued) binary transducer mapping sequences of events to sequences of effectors that actuate features of the CD/radio device.
StateMachine:prsseq; (START) nil [ radio ] 1 1 mode [ cd ] 2 2 mode [ radio ] 3 2 next [ nextTrack ] 2 3 mode [ cd ] 2 3 next [ nextStation ] 3
Modelling discrete systems in this manner obtains a clean separation of syntax (acceptable ordering of events) and semantics (effector implementation). The syntactic order of events and their extension into the semantic domain is expressed in a symbolic (semiring) domain where they can be manipulated algebraically while semantics are expressed in a procedural programming language as simple effector functions, free from syntactic concerns. The rational expressions provide concise holistic maps of the protocols that effect system governance. The compiled automata are post-processed to obtain efficient controllers for run-time deployment.
A finite-state machine (FSM) or finite-state automaton, 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. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines.
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to mathematical logic. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.
In mathematics, a Kleene algebra is an idempotent semiring endowed with a closure operator. It generalizes the operations known from regular expressions.
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.
In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use. It can be thought of as a type that has several "cases", each of which should be handled correctly when that type is manipulated. This is critical in defining recursive datatypes, in which some component of a value may have the same type as that value, for example in defining a type for representing trees, where it is necessary to distinguish multi-node subtrees and leaves. Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.
The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines a relation between sets of strings.
Automata-based programming is a programming paradigm in which the program or part of it is thought of as a model of a finite-state machine (FSM) or any other formal automaton. Sometimes a potentially infinite set of possible states is introduced, and such a set can have a complicated structure, not just an enumeration.
In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
In computer programming, an enumerated type is a data type consisting of a set of named values called elements, members, enumeral, or enumerators of the type. The enumerator names are usually identifiers that behave as constants in the language. An enumerated type can be seen as a degenerate tagged union of unit type. A variable that has been declared as having an enumerated type can be assigned any of the enumerators as a value. In other words, an enumerated type has values that are different from each other, and that can be compared and assigned, but are not specified by the programmer as having any particular concrete representation in the computer's memory; compilers and interpreters can represent them arbitrarily.
Haxe is a high-level cross-platform programming language and compiler that can produce applications and source code for many different computing platforms from one code-base. It is free and open-source software, released under the MIT License. The compiler, written in OCaml, is released under the GNU General Public License (GPL) version 2.
In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.
Automata-based programming is a programming technology. Its defining characteristic is the use of finite state machines to describe program behavior. The transition graphs of state machines are used in all stages of software development. Automata-based programming technology was introduced by Anatoly Shalyto in 1991. Switch-technology was developed to support automata-based programming. Automata-based programming is considered to be rather general purpose program development methodology than just another one finite state machine implementation.
In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words, so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area.
Input/output automata provide a formal model, applicable in describing most types of an asynchronous concurrent system. On its own, the I/O automaton model contains a very basic structure that enables it to model various types of distributed systems. To describe specific types of asynchronous systems, additional structure must be added to this basic model. The model presents an explicit method for describing and reasoning about system components such as processes and message channels that interact with one another, operating at arbitrary relative speeds. The I/O automata were first introduced by Nancy A. Lynch and Mark R. Tuttle in "Hierarchical correctness proofs for distributed algorithms", 1987.
In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata.