Precisely, there is a string-matching automaton for every pattern P that you search for in a given text string T. However, the time to build the automaton can be large. The matching time used (after the automaton is built) is therefore Θ(n). Just as the name implies, a string-matching automaton is a FSA that is used for string matching and is very efficient: they examine each character exactly once, taking constant time per text character. When the automaton reaches the end of the input, if the current state belongs to F, the string consisting sequentially of the symbols read by the automaton is declared accepted, otherwise it is declared rejected. To be specific, let s be the current state and w the symbol just read, the automaton moves to the state given by δ(s, w). The automaton continuously reads symbols from its input, one symbol at a time, and transits between states according to the transition function δ. Δ is a function δ: S × Σ → S known as the transition function.į is a (possibly empty) subset of S whose elements are designated as the final states.Īn FSA with the above description operates as follows:Īt the beginning, the automaton starts in the initial state s0. S0 is an element in S designated as the initial state. Σ is the input alphabet (a finite nonempty set of symbols). A FSA can be typically modeled as a string pattern recognizer described by a quintuple, where: The finite state automaton (FSA) is an important model of behavioral investigations in computer science, linguistics and many other areas.