Thompson's construction algorithm
Algoritmo de Thompson
- Date
- 1968 · confidence medium
- Place
- Murray Hill, New Jersey, United States
- Credited to
- Ken Thompson
- Field
- Knowledge & symbols
What it is
An algorithm, also called the McNaughton-Yamada-Thompson construction, that converts a regular expression into an equivalent nondeterministic finite automaton (NFA), letting text search patterns be compiled into executable machines.
What it led to
- basis of regular expression engines in text editors and compilers
- the grep tool developed by Thompson himself
- standard in formal language theory and compiler design
- influence on the design of Unix and its text tools