Editing Finite-state machine (section)

=== 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.