Finite Automata and Regular Expressions

Pattern recognition and generation is ubiquitous in computing:

• patterns of symbols in a program
• patterns of words in a document
• patterns of characters in a file
• patterns of bits in an image

Finite automata are formal (or abstract) machines for recognizing patterns. These machines are used extensively in compilers and text editors, which must recognize patterns in the input.

Regular expressions are a formal notation for generating patterns. This notation is used extensively in programming language manuals (used to describe legal patterns of input) and in command languages (such as the Unix shell, where it is used to describe patterns for naming files, etc.)

Lex is a Unix utility that accepts regular expressions as input, and produces a C program that simulates a finite automaton to recognize those regular expressions. Thus, lex combines both string pattern generation (regular expressions that define the strings of interest to lex) and string pattern recognition (a finite automaton that recognizes the strings of interest).