Editing Finite-state transducer (section)

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