Editing Finite-state machine (section)

== Mathematical model ==
In accordance with the general classification, the following formal definitions are found.

A ''deterministic finite-state machine'' or ''deterministic finite-state acceptor'' is a [[Tuple|quintuple]] <math>(\Sigma, S, s_0, \delta, F)</math>, where:
* <math>\Sigma</math> is the input [[Alphabet (computer science)|alphabet]] (a finite non-empty set of symbols);
* <math>S</math> is a finite non-empty set of states;
* <math>s_0</math> is an initial state, an element of <math>S</math>;
* <math>\delta</math> is the state-transition function: <math>\delta: S \times \Sigma \rightarrow S</math> (in a [[nondeterministic finite automaton]] it would be <math>\delta: S \times \Sigma \rightarrow \mathcal{P}(S)</math>, i.e. <math>\delta</math> would return a set of states);
* <math>F</math> is the set of final states, a (possibly empty) subset of <math>S</math>.

For both deterministic and non-deterministic FSMs, it is conventional to allow <math>\delta</math> to be a [[partial function]], i.e. <math>\delta(s, x)</math> does not have to be defined for every combination of <math>s \isin S</math> and <math>x \isin \Sigma</math>. If an FSM <math>M</math> is in a state <math>s</math>, the next symbol is <math>x</math> and <math>\delta(s, x)</math> is not defined, then <math>M</math> can announce an error (i.e. reject the input). This is useful in definitions of general state machines, but less useful when transforming the machine. Some algorithms in their default form may require total functions.

A finite-state machine has the same computational power as a [[Turing machine]] that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite-state machine is accepted by such a kind of restricted Turing machine, and vice versa.<ref>{{cite journal
 |last     = Black
 |first    = Paul E
 |date     = 12 May 2008
 |title    = Finite State Machine
 |journal   = Dictionary of Algorithms and Data Structures
 |publisher  = U.S. [[National Institute of Standards and Technology]]
 |url     = https://xlinux.nist.gov/dads/HTML/finiteStateMachine.html
 |access-date = 2 November 2016
 |archive-url = https://web.archive.org/web/20181013023517/https://xlinux.nist.gov/dads/HTML/finiteStateMachine.html
 |archive-date = 13 October 2018
 |url-status   = dead
 |df      = dmy-all
}}</ref>

A ''[[finite-state transducer]]'' is a [[sextuple]] <math>(\Sigma, \Gamma, S, s_0, \delta, \omega)</math>, where:
* <math>\Sigma</math> is the input [[Alphabet (computer science)|alphabet]] (a finite non-empty set of symbols);
* <math>\Gamma</math> is the output alphabet (a finite non-empty set of symbols);
* <math>S</math> is a finite non-empty set of states;
* <math>s_0</math> is the initial state, an element of <math>S</math>;
* <math>\delta</math> is the state-transition function: <math>\delta: S \times \Sigma \rightarrow S</math>;
* <math>\omega</math> is the output function.

If the output function depends on the state and input symbol (<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) that definition corresponds to the ''Mealy model'', and can be modelled as a [[Mealy machine]]. If the output function depends only on the state (<math>\omega: S \rightarrow \Gamma</math>) that definition corresponds to the ''Moore model'', and can be modelled as a [[Moore machine]]. A finite-state machine with no output function at all is known as a [[semiautomaton]] or [[transition system]].

If we disregard the first output symbol of a Moore machine, <math>\omega(s_0)</math>, then it can be readily converted to an output-equivalent Mealy machine by setting the output function of every Mealy transition (i.e. labeling every edge) with the output symbol given of the destination Moore state. The converse transformation is less straightforward because a Mealy machine state may have different output labels on its incoming transitions (edges). Every such state needs to be split in multiple Moore machine states, one for every incident output symbol.<ref name="AndersonHead2006">{{cite book |first1=James Andrew |last1=Anderson |first2=Thomas J. |last2=Head |title=Automata theory with modern applications |url=https://books.google.com/books?id=ikS8BLdLDxIC&pg=PA105 |year=2006 |publisher=Cambridge University Press |isbn=978-0-521-84887-9 |pages=105–108}}</ref>