FSA (Finite State Automata)

A Finite State Automaton (FSA) is a mathematical model of computation consisting of a finite set of states, a designated start state, one or more accepting states, and a transition function that maps each state-input pair to a subsequent state. FSAs process input sequences symbol by symbol, moving between states according to these transition rules, and accept or reject an input based on whether the automaton ends in an accepting state. They come in two primary flavors: Deterministic Finite Automata (DFA), where each state has exactly one transition per input symbol, and Non-deterministic Finite Automata (NFA), where multiple transitions or epsilon transitions are permitted. Despite their apparent difference in power, DFAs and NFAs recognize exactly the same class of languages — the regular languages.

In machine learning and NLP, FSAs serve as lightweight, interpretable models for sequence processing tasks. They underpin tokenization pipelines, regular-expression-based feature extraction, and morphological analyzers that parse word forms in languages with rich inflection. Weighted FSAs, which assign probabilities or costs to transitions, extend the framework to probabilistic modeling and are closely related to Hidden Markov Models — a foundational tool in speech recognition and sequence labeling. Finite-state transducers, a generalization that produces output alongside reading input, are widely used in text normalization, grapheme-to-phoneme conversion, and machine translation preprocessing.

FSAs matter to modern AI practitioners for several reasons. First, they offer guaranteed linear-time processing and constant memory usage relative to the automaton size, making them highly efficient for production text pipelines. Second, their explicit state structure makes them fully interpretable — a property increasingly valued as neural models face scrutiny over transparency. Third, FSAs can be composed, minimized, and intersected algorithmically, enabling modular construction of complex linguistic processors from simpler components. Researchers also use FSAs as theoretical benchmarks to probe what recurrent neural networks and transformers implicitly learn, since recognizing regular and context-free languages represents a well-defined hierarchy of computational difficulty. This interplay between classical automata theory and deep learning continues to generate productive research into the expressive power and limitations of neural sequence models.