Automaton consisting of a finite number of states and transitions that accepts exactly the regular languages. Every regular expression — including every Ruby Regexp — compiles to a finite-state machine under the hood. Used as the model for lexical analysis in compilers and interpreters.