Lexical analysis involves searching input data for lexemes that match tokens specified as regular expressions. This is enabled by building a state machine for each token, and then running each input character through the state machines looking for matches.