P y F oma: a Python finite-state compiler module (2024)

Abstract: We describe PyFoma, an open-source Python module for constructing weighted and unweighted finite-state transducers and automata from regular expressions, string rewriting rules, right-linear grammars, or low-level state/transition manipulation. A large variety of standard algorithms for working with finite-state machines is included, with a particular focus on the needs of linguistic and NLP applications. The data structures and code in the module are designed for legibility to allow for potential use in teaching the theory and algorithms associated with finite-state machines.

## introduction finite-state technology is well established in the nlp community and is widely used for various lower-level tasks such as tokenization, morphology, phonology, spell checking, spelling correction, grapheme-to-phoneme (g2p) mapping, various speech applications, and general string processing @xcite @xcite . in tandem with neural models, finite-state models can also be used to constrain the output of a neural network to prevent generation of text that fails to adhere to a specific format @xcite . furthermore, finitestate methods may be effective in low-resource scenarios, allowing the incorporation of expert knowledge @xcite @xcite . several tools exist for constructing and manipulating finite-state automata (fsas) and transducers (fsts), together finite-state machines (fsms). 1 some, such as openfst @xcite , carmel @xcite , foma @xcite , and xfst @xcite are stand-alone tools, implemented in c or c++ for 1 as every fsa can be expressed as an fst and vice-versa, we often use these terms roughly interchangeably. efficiency reasons, while others, such as pynini @xcite , @xcite , and kleene @xcite rely on the existing algorithms and apis of openfst or foma to allow for fst manipulation in higher-level languages. pyfoma is a complete finite-state toolkit written in pure python. it is available on github at https://github.com/mhulden/pyfoma , and easily installable via the pypi package repository at https://pypi.org/project/pyfoma/ . the project has the following overall aims: ## implementation the core functionality-apart from visualizationof pyfoma is implemented entirely in python, foot_1 relying only on the python standard library for its dependencies, and exposing a pythonic api. py-foma provides a class fst with methods to construct (w)fsas/(w)fsts out of either regular expressions or algebraic manipulation. ## a morphological analyzer example figure 7 shows a mini-grammar built with the same principles as larger grammars. first, a lexicon component is constructed as a transducer (the concatenation @xmath0infl). following this, a sequence of rewrite-rule transducers are composed with the lexicon. in our case we have two rules: the first inserts e between a sibilant consonant on the left and +s on the right (e.g. bus+@xmath1; the second removes all +-symbols which are used temporarily to denote morpheme boundaries. the composite transducer represents a minimal example of an analyzer/generator. ## conclusion we introduce pyfoma, an open-source python module to facilitate the construction of weighted and unweighted fsms, with specific support for nlp applications. we hope to provide a stable module that features a broad set of tools for use in teaching, research, and development of applications using finite-state technology and includes detailed documentation, example code, tutorials, and exercises.