Real world applications of FSAs
11 April 2025
In computational theory, finite state automata (FSA) are “abstract machines used to recognise patterns in input sequences” (GeeksforGeeks, 2026). They are powerful abstractions which allows us to control and model the behaviour of computers machines with a finite number of states. Through this essay, I will explore several real-world applications of FSAs.
An FSA works by starting at the initial state (often with notation q0), reading a word (a set of input characters) and passing through states, where there is a possible transition given the word. Once all words have been read, if the current state is an accepting state (often with notation qFinal), then the word is accepted by the automata. They come in the form of deterministic (DFA), where for any given state and word there is only one possible transition, and non-deterministic (NFA), where there are different transitions possible. In addition to this, finite state automata can be minimised, enabling us to determine a smaller, equivalent automaton which accepts the same language. There are many different applications to finite state automata, including lexical analysis during compilation, network protocols and spell checkers.
One application of finite state automata is through lexical analysis, during compilation of programs. When a program compiles, a simple structure follows, beginning with lexical analysis. “The role of a lexical analyser is to read a bit of the input and return a lexeme (or token)” (University of Edinburgh, 2023, p. 15). Each token pattern produces a class, which is represented by a regular expression. These regular expressions are then converted into DFAs (Kulkarni, 2025). During lexical analysis, the DFA recognises each word, transitioning through states as appropriate. If the final state is reached, the token is then recognised and then later passed to syntax analysis. If the final state is not reached, the word is therefore not accepted. This is one example of how FSAs are used to facilitate a real-world application, in the case of compilation.
In addition to this, a finite state automaton can be used to model network protocols. “Network protocols are defined as the rules and conventions that govern communication between peers in a network” (Ivanova & Jurczyk, 2003). In the case of a protocol, a “generator creates an automaton that accepts all and only the packets that respect the protocol format” (Rolando, et al., n.d.). Similar to the process during lexical analysis, an FSA is ideal because it can filter an incoming word, in this case a packet, and deem it matching of the format intended, if and only if the word ends at an accepting state. That way, the FSA verifies and filters incoming packets to check if they meet a certain protocol. In this regard, it is clear how finite state automata can be used to model network protocols and communication between devices.
Furthermore, spell checkers heavily utilise finite state automata to verify the spelling of a given word. In a similar light, FSAs are used in spell checkers, as an automaton is “designed to accept only those words that are valid in a given language” (Kambarami, n.d.). This suits the role of a spell checker, which also checks if a word is valid in a language. However, a spell checker’s job is not only to check if spellings are correct, but also to suggest any corrected spellings. This is where the Levenshtein automaton comes in useful. A “possible measure for the proximity of two strings is the so-called Levenshtein distance”. This distance between two words is the “minimal number of primitive edit operations” transforming one word into the other. (Mitankin, 2005) This may include, for example, substitution of a letter, or deletion, whereby a typo may have occurred. Given this, a Levenshtein automaton can be constructed, which “recognize the set of all strings whose Levenshtein distance from w is at most n” (Wikipedia, 2026), used for efficient string correction algorithms, “computed in time linear to the length of the input”. (Schulz & Mihov, 2002). This way, FSA become incredibly valuable in the determination of text correctness and calculation of appropriate suggestions.
In conclusion, it is clear that there are many real-world applications of finite state automaton, which may not be obvious to a user. However, applications of FSAs can be found hidden in everyday tools and algorithms which have become a part of everyday life. The use of FSAs intertwined with other theories and algorithms allow for FSAs, as powerful abstractions, to provide powerful software and hardware. The development of modern technology, to some extent, is reliant on the validation provided by FSAs.