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).

last modified Jan 16 1996 / Tom LeBlanc / leblanc@cs.rochester.edu