Editing Finite-state transducer

{{Short description|Finite state machine with two tapes (input, output)}}
{{Multiple issues|
{{more footnotes|date=August 2014}}
{{citation style|date=August 2014}}
}}

A '''finite-state transducer''' ('''FST''') is a [[finite-state machine]] with two memory ''tapes'', following the terminology for [[Turing machine]]s: 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.<ref>{{Cite book|title=Speech and Language Processing|last=Jurafsky|first=Daniel|publisher=Pearson|year=2009|isbn=9789332518414}}</ref>  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 [[Finitary relation|relation]] between sets of strings.

An FST will read a set of strings on the input tape and generate a set of relations on the output tape.  An FST can be thought of as a translator or relater between strings in a set.

In [[morphological parsing]], an example would be inputting a string of letters into the FST, the FST would then output a string of [[morphemes]].

==Overview==
{{external media
| float  = right
| video1 = [https://www.youtube.com/watch?v=F_dTuHS6Wbk Finite State Transducers] // [[Karlsruhe Institute of Technology]], YouTube video
}}

An [[automaton]] can be said to ''recognize'' a string if we view the content of its tape as input.  In other words, the automaton computes a function that maps strings into the set {0,1}.  Alternatively, we can say that an automaton ''generates'' strings, which means viewing its tape as an output tape.  On this view, the automaton generates a [[formal language]], which is a set of strings.  The two views of automata are equivalent: the function that the automaton computes is precisely the [[indicator function]] of the set of strings it generates.  The class of languages generated by finite automata is known as the class of [[regular language]]s.

The two tapes of a transducer are typically viewed as an input tape and an output tape.  On this view, a transducer is said to ''transduce'' (i.e., translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape.  It may do so [[Nondeterministic algorithm|nondeterministic]]ally and it may produce more than one output for each input string.  A transducer may also produce no output for a given input string, in which case it is said to ''reject'' the input.  In general, a transducer computes a [[relation (mathematics)|relation]] between two formal languages.

Each string-to-string finite-state transducer relates the input alphabet Σ to the output alphabet Γ. Relations ''R'' on Σ*×Γ* that can be implemented as finite-state transducers are called '''rational relations'''. Rational relations that are [[partial function]]s, i.e. that relate every input string from Σ* to at most one Γ*, are called '''rational functions'''.

Finite-state transducers are often used for [[phonology|phonological]] and [[morphology (linguistics)|morphological analysis]] in [[natural language processing]] research and applications. Pioneers in this field include [[Ronald Kaplan]], [[Lauri Karttunen]], [[Martin Kay]] and [[Kimmo Koskenniemi]].<ref>{{harvnb|Koskenniemi|1983}}</ref>{{primary source inline|date=August 2014}}
A common way of using transducers is in a so-called "cascade", where transducers for various operations are combined into a single transducer by repeated application of the composition operator (defined below).

==Formal construction==

Formally, a finite transducer ''T'' is a 6-tuple ({{math|''Q'', Σ, Γ, ''I'', ''F'', δ}}) such that:

* {{mvar|Q}} is a [[finite set]], the set of ''states'';
* {{math|Σ}} is a finite set, called the ''input alphabet'';
* {{math|Γ}} is a finite set, called the ''output alphabet'';
* {{mvar|I}} is a [[subset]] of {{mvar|Q}}, the set of ''initial states'';
* {{mvar|F}} is a subset of {{mvar|Q}}, the set of ''final states''; and
* <math>\delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q</math> (where ε is the [[empty string]]) is the ''transition relation''.

We can view (''Q'', ''δ'') as a labeled [[directed graph]], known as the ''transition graph'' of ''T'': the set of vertices is ''Q'', and  <math>(q,a,b,r)\in\delta</math> means that there is a labeled edge going from vertex ''q'' to vertex ''r''.  We also say that ''a'' is the ''input label'' and ''b'' the ''output label'' of that edge.

NOTE: This definition of finite transducer is also called ''letter transducer'' (Roche and Schabes 1997); alternative definitions are possible, but can all be converted into transducers following this one.

Define the ''extended transition relation'' <math>\delta^*</math> as the smallest set such that:

* <math>\delta\subseteq\delta^*</math>;
* <math>(q,\epsilon,\epsilon,q)\in\delta^*</math> for all <math>q\in Q</math>; and
* whenever <math>(q,x,y,r) \in \delta^*</math> and <math>(r,a,b,s) \in \delta</math> then <math>(q,xa,yb,s) \in \delta^*</math>.

The extended transition relation is essentially the reflexive [[transitive closure]] of the transition graph that has been augmented to take edge labels into account.  The elements of <math>\delta^*</math> are known as ''paths''.  The edge labels of a path are obtained by concatenating the edge labels of its constituent transitions in order.

The ''behavior'' of the transducer ''T'' is the rational relation [''T''] defined as follows: <math>x[T]y</math> [[if and only if]] there exists <math>i \in I</math> and <math>f \in F</math> such that <math>(i,x,y,f) \in \delta^*</math>.  This is to say that ''T'' transduces a string <math>x\in\Sigma^*</math> into a string <math>y\in\Gamma^*</math> if there exists a path from an initial state to a final state whose input label is ''x'' and whose output label is ''y''.

===Weighted automata===
{{see also|Rational series}}
Finite State Transducers can be weighted, where each transition is labelled with a weight in addition to the input and output labels. A Weighted Finite State Transducer (WFST) over a set ''K'' of weights can be defined similarly to an unweighted one as an 8-tuple {{math|1=''T''=(''Q'', Σ, Γ, ''I'', ''F'', ''E'', ''λ'', ''ρ'')}}, where:
* {{math|''Q'', Σ, Γ, ''I'', ''F''}} are defined as above;
* <math> E \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q \times K</math> (where ''ε'' is the [[empty string]]) is the finite set of transitions;
* <math>\lambda:  I \rightarrow K </math> maps initial states to weights;
* <math>\rho: F \rightarrow K </math> maps final states to weights.
In order to make certain operations on WFSTs well-defined, it is convenient to require the set of weights to form a [[semiring]].<ref name=BR16>{{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 | page=16 }}</ref> Two typical semirings used in practice are the [[log semiring]] and [[tropical semiring]]: [[Nondeterministic finite automaton|nondeterministic automata]] may be regarded as having weights in the [[Boolean semiring]].<ref name=Lot211>{{cite book | last=Lothaire | first=M. | author-link=M. Lothaire | title=Applied combinatorics on words | others=A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, [[Gesine Reinert]], [[Sophie Schbath]], Michael Waterman, Philippe Jacquet, [[Wojciech Szpankowski]], Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and [[Valérie Berthé]] | series=Encyclopedia of Mathematics and Its Applications | volume=105 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2005 | isbn=0-521-84802-4 | zbl=1133.68067 | page=[https://archive.org/details/appliedcombinato0000loth/page/211 211] | url=https://archive.org/details/appliedcombinato0000loth/page/211 }}</ref>

Two weighted FST can be composed.<ref>{{Cite journal |last=Pereira |first=Fernando |last2=Riley |first2=Michael |last3=Sproat |first3=Richard |date=1994-03-08 |title=Weighted rational transductions and their application to human language processing |url=https://dl.acm.org/doi/10.3115/1075812.1075870 |journal=Proceedings of the workshop on Human Language Technology |series=HLT '94 |location=USA |publisher=Association for Computational Linguistics |pages=262–267 |doi=10.3115/1075812.1075870 |isbn=978-1-55860-357-8}}</ref>

===Stochastic FST===
Stochastic FSTs (also known as probabilistic FSTs or statistical FSTs) are presumably a form of weighted FST.{{citation needed|date=April 2017}}

==Operations on finite-state transducers==

The following operations defined on finite automata also apply to finite transducers:

* [[Union (set theory)|Union]].  Given transducers {{mvar|T}} and {{mvar|S}}, there exists a transducer <math>T\cup S</math> such that <math>x[T\cup S]y</math> if and only if <math>x[T]y</math> or <math>x[S]y</math>.
* [[Concatenation]].  Given transducers {{mvar|T}} and {{mvar|S}}, there exists a transducer <math>T\cdot S</math> such that <math>x[T\cdot S]y</math> if and only if there exist <math>x_1, x_2, y_1, y_2</math> with <math>x=x_1x_2, y =y_1y_2, x_1[T]y_1</math> and <math>x_2[S]y_2.</math>
* [[Kleene closure]].  Given a transducer {{mvar|T}}, there might exist a transducer <math>T^*</math> with the following properties:<ref name="BoigelotLegayWolper2003">{{cite book | title = Computer Aided Verification | last1 = Boigelot | first1 = Bernard | last2 = Legay | first2 = Axel | last3 = Wolper | first3 = Pierre | chapter = Iterating Transducers in the Large | series = Lecture Notes in Computer Science | date = 2003 | volume = 2725 | pages = 223–235 | publisher = Springer Berlin Heidelberg | issn = 0302-9743 | eissn = 1611-3349 | doi = 10.1007/978-3-540-45069-6_24 | isbn = 978-3-540-40524-5 | url = }}</ref>
{{NumBlk|*::| <math>\epsilon[T^*]\epsilon</math>; |{{EquationRef|k1}}}}
{{NumBlk|*::| if <math>w[T^*]y</math> and <math>x[T]z</math>, then <math>wx[T^*]yz</math>; |{{EquationRef|k2}}}}
:: and <math>x[T^*]y</math> does not hold unless mandated by ({{EquationNote|k1}}) or ({{EquationNote|k2}}).
* [[Composition of relations|Composition]]. Given a transducer {{mvar|T}} on alphabets Σ and Γ and a transducer {{mvar|S}} on alphabets Γ and Δ, there exists a transducer <math>T \circ S</math> on Σ and Δ such that <math>x[T \circ S]z</math> if and only if there exists a string <math>y\in\Gamma^*</math> such that <math>x[T]y</math> and <math>y[S]z</math>. This operation extends to the weighted case.<ref>{{harvnb|Mohri|2004|pp=3–5}}</ref>

:This definition uses the same notation used in mathematics for [[Composition of relations|relation composition]]. However, the conventional reading for relation composition is the other way around: given two relations {{mvar|T}} and {{mvar|S}}, <math>(x,z)\in T\circ S</math> when there exist some {{mvar|y}} such that <math>(x,y)\in S</math> and <math>(y,z)\in T.</math>

* [[Projection (mathematics)|Projection]] to an automaton.  There are two projection functions: <math>\pi_1</math> preserves the input tape, and <math>\pi_2</math> preserves the output tape.  The first projection, <math>\pi_1</math> is defined as follows:

: Given a transducer {{mvar|T}}, there exists a finite automaton <math>\pi_1 T</math> such that <math>\pi_1 T</math> accepts ''x'' if and only if there exists a string ''y'' for which <math>x[T]y.</math>

:The second projection, <math>\pi_2</math> is defined similarly.

* [[Determinization]]. Given a transducer {{mvar|T}}, we want to build an equivalent transducer that has a unique initial state and such that no two transitions leaving any state share the same input label. The [[powerset construction]] can be extended to transducers, or even weighted transducers, but sometimes fails to halt; indeed, some non-deterministic transducers do not admit equivalent deterministic transducers.<ref>{{Cite web|url=http://www.let.rug.nl/~vannoord/papers/preds/node22.html|title = Determinization of Transducers}}</ref> [[Characterization (mathematics)|Characterizations]] of determinizable transducers have been proposed<ref>{{harvnb|Mohri|2004|pp=5–6}}</ref> along with efficient algorithms to test them:<ref>{{harvnb|Allauzen|Mohri|2003}}</ref> they rely on the [[semiring]] used in the weighted case as well as a general property on the structure of the transducer (the [[twins property]]).
* Weight pushing for the weighted case.<ref>{{harvnb|Mohri|2004|pp=7–9}}</ref>
* Minimization for the weighted case.<ref>{{harvnb|Mohri|2004|pp=9–11}}</ref>
* Removal of [[Nondeterministic finite automaton|epsilon-transitions]].

==Additional properties of finite-state transducers==

* It is [[Decidability (logic)|decidable]] whether the relation [''T''] of a transducer ''T'' is empty.
* It is decidable whether there exists a string ''y'' such that ''x''[''T'']''y'' for a given string ''x''.
* It is [[undecidable problem|undecidable]] whether two transducers are equivalent.<ref>{{harvnb|Griffiths|1968}}</ref> Equivalence is however decidable in the special case where the relation [''T''] of a transducer ''T'' is a (partial) function.
* If one defines the alphabet of labels <math>L=(\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\})</math>, finite-state transducers are isomorphic to [[nondeterministic finite automata|NDFA]] over the alphabet <math>L</math>, and may therefore be determinized (turned into [[deterministic finite automaton|deterministic finite automata]] over the alphabet <math>L=[(\Sigma\cup\{\epsilon\}) \times \Gamma] \cup [\Sigma \times (\Gamma\cup\{\epsilon\})]</math>) and subsequently minimized so that they have the minimum number of states.{{Citation needed|date=September 2008}}

==Applications==

FSTs are used in the [[lexical analysis]] phase of [[compilers]] to associate semantic value with the discovered tokens.<ref>{{cite book|author1=Charles N. Fischer|author2=Ron K. Cytron|author3=Richard J. LeBlanc, Jr.|title=Crafting a Compiler|publisher=Addison-Wesley|isbn=978-0-13-606705-4|chapter=Scanning - Theory and Practice|year=2010 }}</ref>

Context-sensitive rewriting rules of the form ''a'' → ''b'' / ''c'' _ ''d'', used in [[linguistics]] to model [[phonological rule]]s and [[sound change]], are computationally equivalent to finite-state transducers, provided that application is nonrecursive, i.e. the rule is not allowed to rewrite the same substring twice.<ref>{{cite web | url=http://acl.ldc.upenn.edu/J/J94/J94-3001.pdf | title=Regular Models of Phonological Rule Systems | access-date=August 25, 2012 | archive-url=https://web.archive.org/web/20101011225829/http://acl.ldc.upenn.edu/J/J94/J94-3001.pdf | archive-date=October 11, 2010 | url-status=dead }}</ref>

Weighted FSTs found applications in [[natural language processing]],<ref>{{Citation |last1=Knight |first1=Kevin |title=Applications of Weighted Automata in Natural Language Processing |date=2009 |work=Handbook of Weighted Automata |pages=571–596 |editor-last=Droste |editor-first=Manfred |url=https://link.springer.com/chapter/10.1007/978-3-642-01492-5_14 |access-date=2025-05-24 |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-642-01492-5_14 |isbn=978-3-642-01492-5 |last2=May |first2=Jonathan |editor2-last=Kuich |editor2-first=Werner |editor3-last=Vogler |editor3-first=Heiko}}</ref> including [[machine translation]],<ref>{{Cite journal |last1=Casacuberta |first1=Francisco |last2=Vidal |first2=Enrique |date=2007-01-01 |title=Learning finite-state models for machine translation |url=https://link.springer.com/article/10.1007/s10994-006-9612-9 |journal=Machine Learning |language=en |volume=66 |issue=1 |pages=69–91 |doi=10.1007/s10994-006-9612-9 |issn=1573-0565}}</ref> [[speech recognition]],<ref>{{Citation |last1=Mohri |first1=Mehryar |title=Speech Recognition with Weighted Finite-State Transducers |date=2008 |work=Springer Handbook of Speech Processing |pages=559–584 |editor-last=Benesty |editor-first=Jacob |url=https://link.springer.com/chapter/10.1007/978-3-540-49127-9_28 |access-date=2025-05-24 |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-540-49127-9_28 |isbn=978-3-540-49127-9 |last2=Pereira |first2=Fernando |last3=Riley |first3=Michael |editor2-last=Sondhi |editor2-first=M. Mohan |editor3-last=Huang |editor3-first=Yiteng Arden}}</ref><ref>{{Cite journal |last1=Mohri |first1=Mehryar |last2=Pereira |first2=Fernando |last3=Riley |first3=Michael |date=2002-01-01 |title=Weighted finite-state transducers in speech recognition |url=https://www.sciencedirect.com/science/article/abs/pii/S0885230801901846 |journal=Computer Speech & Language |volume=16 |issue=1 |pages=69–88 |doi=10.1006/csla.2001.0184 |issn=0885-2308}}</ref> [[speech synthesis]],<ref>{{Cite journal |last=Mohri |first=Mehryar |date=1997-06-01 |title=Finite-state transducers in language and speech processing |url=https://dl.acm.org/doi/abs/10.5555/972695.972698 |journal=Comput. Linguist. |volume=23 |issue=2 |pages=269–311 |issn=0891-2017}}</ref> and [[optical character recognition]].<ref>{{Cite journal |last=Breuel |first=Thomas M. |date=2008-01-27 |editor-last=Yanikoglu |editor-first=Berrin A. |editor2-last=Berkner |editor2-first=Kathrin |title=The OCRopus open source OCR system |url=https://www.spiedigitallibrary.org/redirect/proceedings/proceeding?articleid=812144 |pages=68150F–68150F–15 |doi=10.1117/12.783598}}</ref> Also in [[image compression]],<ref>{{Citation |last1=Albert |first1=Jürgen |title=Digital Image Compression |date=2009 |work=Handbook of Weighted Automata |pages=453–479 |editor-last=Droste |editor-first=Manfred |url=https://link.springer.com/chapter/10.1007/978-3-642-01492-5_11 |access-date=2025-05-24 |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-642-01492-5_11 |isbn=978-3-642-01492-5 |last2=Kari |first2=Jarkko |editor2-last=Kuich |editor2-first=Werner |editor3-last=Vogler |editor3-first=Heiko}}</ref> and [[machine learning]] in general.<ref>{{Citation |last1=Cortes Corinna |title=Learning with Weighted Transducers |date=2009 |url=https://www.medra.org/servlet/aliasResolver?alias=iospressISSNISBN&issn=0922-6389&volume=191&spage=14 |publisher=IOS Press |doi=10.3233/978-1-58603-975-2-14 |last2=Mohri Mehryar|series=Frontiers in Artificial Intelligence and Applications }}</ref> An implementation for [[part-of-speech tagging]] can be found as one component of the OpenGrm<ref>[http://opengrm.org/ OpenGrm]</ref> library.

==See also==

* [[Mealy machine]]
* [[Moore machine]]
* [[Morphological dictionary]]
* [[foma (software)]]
* [[Tree transducer]]
* [[Relational transducer]]

==Notes==
{{Reflist}}

== References ==
{{refbegin}}
*{{cite journal
  | last1 = Allauzen
  | first1 = Cyril
  | last2 = Mohri
  | first2 = Mehryar
  | title = Efficient Algorithms for Testing the Twins Property
  | journal = Journal of Automata, Languages and Combinatorics
  | year = 2003
  | volume = 8
  | issue = 2
  | pages = 117–144
  | url = http://www.cs.nyu.edu/~mohri/pub/twins.pdf
  }}
*{{citation
  | last = Koskenniemi
  | first = Kimmo
  | author-link = Kimmo Koskenniemi
  | title = Two-level morphology: A general computational model of word-form recognition and production
  | publisher = Department of General Linguistics, [[University of Helsinki]]
  | year = 1983
  | url = http://www.ling.helsinki.fi/~koskenni/doc/Two-LevelMorphology.pdf
  | access-date = 2010-01-10
  | archive-date = 2018-12-21
  | archive-url = https://web.archive.org/web/20181221032913/http://www.ling.helsinki.fi/~koskenni/doc/Two-LevelMorphology.pdf
  | url-status = dead
  }}
*{{cite book
  | last = Mohri
  | first = Mehryar
  | chapter = Weighted Finite-State Transducer Algorithms. An Overview
  | title = Formal Languages and Applications
  | series = Studies in Fuzziness and Soft Computing
  | year = 2004
  | volume = 148
  | issue = 620
  | pages = 551–564
  | chapter-url = http://www.cs.nyu.edu/~mohri/pub/fla.pdf
  | doi = 10.1007/978-3-540-39886-8_29
  | isbn = 978-3-642-53554-3
  }}
*{{cite journal
  | last = Griffiths
  | first = T. V.
  | title = The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
  | journal = Journal of the ACM
  | year = 1968
  | volume = 15
  | issue = 3
  | pages = 409–413
  | publisher = ACM
  | doi = 10.1145/321466.321473
}}
{{refend}}

==External links==
* [http://openfst.org/ OpenFst], an open-source library for FST operations.
* [https://web.stanford.edu/~laurik/fsmbook/home.html Finite State Morphology--The Book] {{Webarchive|url=https://web.archive.org/web/20220325205925/https://web.stanford.edu/~laurik/fsmbook/home.html |date=2022-03-25 }} XFST/ LEXC, a description of Xerox's implementation of finite-state transducers intended for linguistic applications.
* [http://hfst.github.io/ The Helsinki open source implementation and extension of the Xerox fst] 
* [https://code.google.com/archive/p/foma/ FOMA], an open-source implementation of most of the capabilities of the Xerox XFST/ LEXC implementation.
* [http://www.cis.uni-muenchen.de/~schmid/tools/SFST/ Stuttgart Finite State Transducer Tools], another open-source FST toolkit
* [http://jsalatas.ictpro.gr/java-fst-framework-api-review/ java FST Framework], an open-source java FST Framework capable of handling OpenFst text format.
* [http://vcsn.lrde.epita.fr/ Vcsn] {{Webarchive|url=https://web.archive.org/web/20200623094748/http://vcsn.lrde.epita.fr/ |date=2020-06-23 }}, an open-source platform (C++ & IPython) platform for weighted automata and rational expressions.

==Further reading==

* {{cite book |last= Jurafsky|first= Daniel |author2=James H. Martin|author-link=Daniel Jurafsky|title= Speech and Language Processing |url= https://archive.org/details/speechlanguagepr00jura|url-access= limited|publisher= Prentice Hall |year= 2000 |isbn= 0-13-095069-6 |pages=[https://archive.org/details/speechlanguagepr00jura/page/n206 71]–83}}
* {{cite book |last= Kornai|first= András|author-link=András Kornai|title=Extended Finite State Models of Language |publisher= Cambridge University Press |year=1999 |isbn= 0-521-63198-X}}
* {{cite book |last= Roche|first= Emmanuel |author2=Yves Schabes|title= Finite-state language processing |url= https://archive.org/details/finitestatelangu00roch|url-access= limited|publisher= MIT Press |year= 1997 |isbn= 0-262-18182-7|pages=[https://archive.org/details/finitestatelangu00roch/page/n15 1]–65}}
* {{cite book |last= Beesley|first= Kenneth R. |author2=Lauri Karttunen|title= Finite State Morphology |publisher= Center for the Study of Language and Information |year= 2003 |isbn= 1-57586-434-7}}
* {{cite book |last= Roark|first= Brian |author2=Richard Sproat |author2-link=Richard Sproat |title= Computational Approaches to Morphology and Syntax |publisher= Oxford University Press |year= 2007 |isbn= 978-0-19-927478-9}}
* {{cite book |last= Berstel|first= Jean |title= Transductions and Context-free Languages |publisher= Teubner Verlag |year= 1979 }}. [http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html Free PDF version]
{{Formal languages and grammars}}

{{Authority control}}

{{DEFAULTSORT:Finite State Transducer}}
[[Category:Finite-state machines]]