Editing Finite-state machine (section)

== Classification ==
Finite-state machines can be subdivided into acceptors, classifiers, transducers and sequencers.<ref name="Keller2001">{{cite book |last=Keller |first= Robert M. |title=Computer Science: Abstraction to Implementation |url=http://www.cs.hmc.edu/~keller/cs60book/%20%20%20All.pdf |year=2001 |publisher=Harvey Mudd College |page= 480| chapter=Classifiers, Acceptors, Transducers, and Sequencers| chapter-url =http://www.cs.hmc.edu/~keller/cs60book/12%20Finite-State%20Machines.pdf}}</ref>

=== Acceptors ===
[[File:Fsm parsing word nice.svg|thumb|Fig. 4: Acceptor FSM: parsing the string "nice".]]
[[File:DFAexample.svg|thumb|Fig. 5: Representation of an acceptor; this example shows one that determines whether a binary number has an even number of 0s, where ''S''<sub>1</sub> is an ''accepting state'' and ''S''<sub>2</sub> is a ''non accepting state''.]]

'''Acceptors''' (also called ''detectors'' or '''recognizers''') produce binary output, indicating whether or not the received input is accepted. Each state of an acceptor is either ''accepting'' or ''non accepting''. Once all input has been received, if the current state is an accepting state, the input is accepted; otherwise it is rejected. As a rule, input is a [[string (computer science)|sequence of symbols]] (characters); actions are not used. The start state can also be an accepting state, in which case the acceptor accepts the empty string. The example in figure 4 shows an acceptor that accepts the string "nice". In this acceptor, the only accepting state is state 7.

A (possibly infinite) set of symbol sequences, called a [[formal language]], is a [[regular language]] if there is some acceptor that accepts ''exactly'' that set.{{sfn|Hopcroft|Ullman|1979|pp=18}} For example, the set of binary strings with an even number of zeroes is a regular language (cf. Fig. 5), while the set of all strings whose length is a prime number is not.{{sfn|Hopcroft|Motwani|Ullman|2006|pp=130-1}}

An acceptor could also be described as defining a language that would contain every string accepted by the acceptor but none of the rejected ones; that language is ''accepted'' by the acceptor. By definition, the languages accepted by acceptors are the [[regular language]]s.

The problem of determining the language accepted by a given acceptor is an instance of the [[algebraic path problem]]—itself a generalization of the [[shortest path problem]] to graphs with edges weighted by the elements of an (arbitrary) [[semiring]].<ref name="PoulyKohlas2012">{{cite book|first1=Marc |last1=Pouly |first2=Jürg |last2=Kohlas |title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|at=Chapter 6. Valuation Algebras for Path Problems, p. 223 in particular}}</ref><ref>{{cite web |url=http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf |title=Algebraic path problems |author=Jacek Jonczy |date=Jun 2008 |access-date=20 August 2014 |url-status=dead |archive-url=https://web.archive.org/web/20140821054702/http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf |archive-date=21 August 2014 }}, p. 34</ref>{{Technical inline|date=January 2017}}

An example of an accepting state appears in Fig. 5: a [[deterministic finite automaton]] (DFA) that detects whether the [[Binary numeral system|binary]] input string contains an even number of 0s.

''S''<sub>1</sub> (which is also the start state) indicates the state at which an even number of 0s has been input. S<sub>1</sub> is therefore an accepting state. This acceptor will finish in an accept state, if the binary string contains an even number of 0s (including any binary string containing no 0s). Examples of strings accepted by this acceptor are [[ε]] (the [[empty string]]), 1, 11, 11..., 00, 010, 1010, 10110, etc.

=== Classifiers ===
'''Classifiers''' are a generalization of acceptors that produce ''n''-ary output where ''n'' is strictly greater than two.<ref>{{Cite book|last=Felkin|first=M.|title=Quality Measures in Data Mining - Studies in Computational Intelligence|publisher=Springer, Berlin, Heidelberg|year=2007|isbn=978-3-540-44911-9|editor-last=Guillet|editor-first=Fabrice|volume=43|pages=277–278|doi=10.1007/978-3-540-44918-8_12|editor-last2=Hamilton|editor-first2=Howard J.}}</ref>

=== Transducers ===
{{Main|Finite-state transducer}}
[[File:Fsm Moore model door control.svg|thumb|Fig. 6 Transducer FSM: Moore model example]]
[[File:Fsm mealy model door control.svg|thumb|Fig. 7 Transducer FSM: Mealy model example]]

''Transducers'' produce output based on a given input and/or a state using actions. They are used for control applications and in the field of [[computational linguistics]].

In control applications, two types are distinguished:

;[[Moore machine]]: The FSM uses only entry actions, i.e., output depends only on state. The advantage of the Moore model is a simplification of the behaviour. Consider an elevator door. The state machine recognizes two commands: "command_open" and "command_close", which trigger state changes. The entry action (E:) in state "Opening" starts a motor opening the door, the entry action in state "Closing" starts a motor in the other direction closing the door. States "Opened" and "Closed" stop the motor when fully opened or closed. They signal to the outside world (e.g., to other state machines) the situation: "door is open" or "door is closed".

;[[Mealy machine]]: The FSM also uses input actions, i.e., output depends on input and state. The use of a Mealy FSM leads often to a reduction of the number of states. The example in figure 7 shows a Mealy FSM implementing the same behaviour as in the Moore example (the behaviour depends on the implemented FSM execution model and will work, e.g., for [[Virtual finite-state machine|virtual FSM]] but not for [[event-driven finite-state machine|event-driven FSM]]). There are two input actions (I:): "start motor to close the door if command_close arrives" and "start motor in the other direction to open the door if command_open arrives". The "opening" and "closing" intermediate states are not shown.

=== Sequencers ===
''Sequencers'' (also called ''generators'') are a subclass of acceptors and transducers that have a single-letter input alphabet. They produce only one sequence, which can be seen as an output sequence of acceptor or transducer outputs.<ref name="Keller2001" />

=== Determinism ===
A further distinction is between ''deterministic'' ([[Deterministic finite automaton|DFA]]) and ''non-deterministic'' ([[Nondeterministic finite automaton|NFA]], [[Generalized nondeterministic finite automaton|GNFA]]) automata. In a deterministic automaton, every state has exactly one transition for each possible input. In a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state. The [[powerset construction]] algorithm can transform any nondeterministic automaton into a (usually more complex) deterministic automaton with identical functionality.

A finite-state machine with only one state is called a "combinatorial FSM". It only allows actions upon transition ''into'' a state. This concept is useful in cases where a number of finite-state machines are required to work together, and when it is convenient to consider a purely combinatorial part as a form of FSM to suit the design tools.<ref>Brutscheck, M., Berger, S., Franke, M., Schwarzbacher, A., Becker, S.: Structural Division Procedure for Efficient IC Analysis. IET Irish
Signals and Systems Conference, (ISSC 2008), pp.18–23. Galway, Ireland, 18–19 June 2008. [http://arrow.dit.ie/engschececon/2/]</ref>